说明：JS数据结构与算法 系列文章的代码和示例均可在此找到
上一篇博客发布以后，仅几天的时间竟然成为了我写博客以来点赞数最多的一篇博客。欢喜之余，不由得思考背后的原因，前端er离数据结构与算法太遥远了，论坛里也少有人去专门为数据结构与算法撰文，才使得这看似平平的文章收获如此。不过，这样也更加坚定了我继续学习数据结构与算法的决心（虽然只是入门级的）
相较于之前学习的 栈/队列 只关心 栈顶/首尾 的模式，链表更加像是数组。链表和数组都是用于存储有序元素的集合，但有几点大不相同
下面是单链表的基本结构
- 长度为3的单链表
- 每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成
- 尾节点的引用指向为
类比：寻宝游戏，你有一条线索，这条线索是指向寻找下一条线索的地点的指针。你顺着这条链接去下一个地点，得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法，就是从起点(第一条线索)顺着列表寻找
链表的实现不像之前介绍的栈和队列一般依赖于数组（至少我们目前是这样实现的），它必须自己构建类并组织逻辑实现。我们先创建一个类
一般单链表有以下几种方法：
- 在链表尾部添加一个元素
- 在指定位置插入元素
- 在指定位置删除元素
- 获取指定位置的元素
- 打印整个链表
- 查找链表中是否有某个元素，有则返回索引，没有则返回-1
- 获取链表头部
- 获取链表尾部（有些并未实现尾部）
- 返回链表包含的元素个数
- 清空链表
下面我们来实现几个重要的方法
在链表尾部添加一个新的元素可分为两种情况：
- 原链表中无元素，添加元素后，和均指向新元素
- 原链表中有元素，更新元素（如下）
代码实现
为方便验证，我们先实现方法。方法虽简单，这里却涉及到链表遍历精髓
获取指定索引位置的节点，依次遍历链表，直到指定位置返回
插入元素，需要考虑三种情况
- 插入尾部，相当于
- 插入首部，替代并指向原有头部元素
- 中间，需要断开原有链接并重新组合（如下）
代码实现
在指定位置删除元素同添加元素类似
- 首部：重新定义
- 其他：找到目标位置的前后元素，重塑连接，如果目标位置为尾部，则重新定义
代码实现
完整的链表代码，可点此获取
基于链表实现栈
基于链表实现队列
（1）迭代法
迭代法的核心就是，然后从头部一次向后轮询
代码实现
（2）递归法
递归的本质就是执行到当前位置时，自己并不去解决，而是等下一阶段执行。直到递归终止条件，然后再依次向上执行
利用递归，反向输出
双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素，如下图
正是因为这种变化，使得链表相邻节点之间不仅只有单向关系，可以通过来访问当前节点的上一节点。相应的，双向循环链表的基类也有变化
继承单向链表后，最终的双向循环链表如下【对应的更改为】
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链 表之间唯一的区别在于，单向循环链表最后一个节点指向下一个节点的指针不是引用， 而是指向第一个节点，双向循环链表的第一个节点指向上一节点的指针不是引用，而是指向最后一个节点
链表的实现较于栈和队列的实现复杂许多，同样的，链表的功能更加强大
我们可以通过链表实现栈和队列，同样也可以通过链表来实现栈和队列的问题
链表更像是数组一样的基础数据结构，同时也避免了数组操作中删除或插入元素对其他元素的影响
到此这篇逆向单向链表（逆向建立单链表算法）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/56381.html