转载请注明作者：Edison丶梦楠
如有错误之处，还请您务必在留言区留下您的宝贵经验。或发送邮箱：mvpxiaonan@foxmail.com 告知。
本人非常感谢！希望能和您共同学习，共同进步！
下面介绍链表的两种结构：
单向链表：只能从头遍历到尾，或者从尾遍历到头。
图例：
next：获取下一个节点。
ele：每个节点中的元素。
first：指头部，链表中第一个元素。
我们可以理解为，当拿到链表对象，调用first()就可以得到第一个元素。
size：指元素的个数。（或链表的长度-1，索引从0开始），在集合中没有length一说。数组中的length相当于集合框架中的size
模拟代码为：
//单向链表 class Node{ Node next: //下一个节点 声明方法 Object ele： //节点中的数据 声明方法 public static void main(String [] Nodetest){ Node cnode = new Node(); cnode.next(); //获取下一个元素 cnode.ele(); //获取当前节点元素。 cnode.next().ele(); //获取下一个节点中的元素 } }
双向链表：可以从头遍历到尾，也可以从尾遍历到头。
我们可以理解为，双向链表其实就是两个单向链表的合成。只不过是一个从头到尾，一个从尾到头。
图例：
prev：表示上一个节点
Node first：拿到第一个节点
Node last：拿到最后一个节点。
模拟代码：
//模拟双向链表代码 class Node{ Node first: //第一个节点 声明方法 Node last: //最后一个节点 声明方法 Node prev: //上一个节点 Node next: //下一个节点 声明方法 Object ele： //节点中的数据 声明方法 public static void main(String [] Nodetest){ Node cnode = new Node(); cnode.next(); //获取下一个节点 cnode.ele(); //获取当前节点元素。 cnode.next().ele(); //获取下一个节点中的元素 cnode.first(); //获取第一个节点 cnode.last(); //获取最后一个节点 cnode.prev(); //获取上一个节点 } }
基于链表的实现代码：
//基于双向链表的集合 /** *具体操作代码请参见LinkedList源码 *这里不作具体实现 */ pub11c class MyLinkedL1st { private Node first;//链表的第一个节点 private Hode last;//链表的最后一个节点 private int s1ze;//节点的数量 //链表中的每一个节点 class Node { Node prev;//上一个节点对象 Node Next;//下一个节点对象 Object ele;//当前节点中存储的元素 } }
总结：对于链表操作，无疑是双向链表功能更强大。而双向链表在取头和尾的时候速度更快。
对于链表LinkedList的具体实现，我们仔细读源码可以得出：
在删除操作上，链表结构相对于数组结构要更快。
为什么呢？
数组每次进行删除操作都要进行移位与遍历。当某个元素被删除时，后面的元素要向前补位。最后一个元素设为null，
然后再删除最后一个元素所占的内存空间。
链表的删除操作算法分析：
删除（first也可当做current）即第一个节点时，把下一个节点的next赋给第一个节点的next。把第一个节点的prev设为null;
删除最后一个节点时，把最后一个节点的prev赋给当前对象的last，再把current节点的上一个（prev）节点的next设为null；
删除中间（此处中间节点指将要被删除的节点current）节点时，把current节点的next赋给current节点的上一个节点的next。
再把current节点的prev赋给current节点的下一个节点的prev。
下面给出具体实现代码：
前文说过，LinkedList在向头和尾添加元素时，性能更优。下面给出具体实现代码及代码分析：
在向头部添加元素时算法实现：
把新增之前第一个节点设为新增节点的next节点，然后把新增节点作为之前第一个节点的上一个节点。（或换种说法：把之前第一个节点的上一个节点作为新增节点），再把新增节点作为第一个节点。而新增节点的prev最好设置为null
向尾部添加元素算法实现：
把新增节点作为之前最后一个节点的next节点，再把之前最后一个节点作为新增节点的上一个节点。
再把对象的last属性设置为新增节点即可。
1):增操作:
双向链表可以直接获取自己的第一个和最后一一个节点，
如果新增的元素在第一个或最后一 个位置,那么操作只有1次.
2):删除操作(removeFisrt,removelast):
如果删除第一个元素:操作一一次.如果操作最后一个元素:操作一次如果删除中间的元素:
找到元素节点平均操作:(1+N)/2次.找到节点之后做删除操作: 1次
3):查询操作:
平均:(N+1)/2次
4):修改操作:
平均:(N+1)/2+1次
基于前文（ArrayList性能分析），我们可以得出ArrayList和LinkedList的各自优异之处。基于数组的列表和基于链表的列表的性能对比: Arraylist:查询，更改较快，新增和刪除较慢 Linkeduist查询更改较慢,新增和删除较快
