4-LinkedList底层布局和源码分析

4-LinkedList底层布局和源码分析

介绍汇总：

• LinkedList的全面说明
  
• LinkedList的底层操作机制
  
• LinkedList的运行重要步骤
  
• ArrayList 和 LinkedList 比较
  

1-LinkedList的全面说明

• LinkedList 底层实现了双向链表和双端队列特点
  
• 可以添加任意元素（元素可以重复），包罗 null
  
• 线程不安全，没有实现同步
  

2-LinkedList的底层操作机制

• LinkedList 底层维护了一个双向链表。
  
• LinkedList 中维护了两个属性 first 和 last 分别指向 首节点和尾节点。
  
• 每个节点（Node 对象），里面又维护了 prev、next、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点，终极实现双向链表。
  
• 所以 linkedList 的元素的添加和删除，不是通过数组完成，相对来说效率较高（仅需改变几个指针，无需移动数据）。
  
• 模仿一个简单的双向链表
  

1. // 节点代码
2. class Node<E> {
3.         E item;
4.         Node<E> next;
5.         Node<E> prev;
7.         Node(Node<E> prev, E element, Node<E> next) {
8.             this.item = element;
9.             this.next = next;
10.             this.prev = prev;
11.         }
12. }
14. // 简单双向列表
15. class LinkedList {
16.     int size = 0;
18.     Node<E> first;
20.     Node<E> last;
21. }

复制代码

3-LinkedList的运行重要步骤

• 构造器
  

​                因为双向链表是通过指针指向内存中的数据节点，形成一个链的聚集，所以为啥叫双向链表。所以存储的东西只有指针、巨细，也并没有扩容机制，只要不超出规定的内存，理论上可以无穷添加数据。

• 这里主要 debug 看源码就可以搞清晰了，关键是每个方法的详细使用的算法，比较故意思。
  
• 详细算法介绍
  

1. // 添加数据为链表第一个，也就是 first 指向的
2. // 具体流程：
3. // 1. 根据 first 指针获取当前第一个数据结点
4. // 2. 创建一个参数为 first 指向为空（第一个结点）,数据值，
5. //                 last 指向当前链表中第一个数据结点的新结点
6. // 3. 将 first 指向新结点
7. // 4. 判断加入之前 first 指向是否为空，若为空说明链表为空，则把 last 也指向新结点
8. //                 反之，说明链表中有数据，而之前 first 指向的数据节点 prev 为 null 所以把之前的
9. //                 第一个结点的 prev 指向当前的新结点
10. // 5. 记得一定要将数据个数或长度 + 1 以及链表修改记录
11. private void linkFirst(E e) {
12.         final Node<E> f = first;
13.         final Node<E> newNode = new Node<>(null, e, f);
14.         first = newNode;
15.         if (f == null)
16.             last = newNode;
17.         else
18.             f.prev = newNode;
19.         size++;
20.         modCount++;
21. }
23. // 添加数据为链表最后一个，也就是 last 指向的
24. // 具体流程：
25. // 1. 根据 last 指针获取当前最后一个数据结点
26. // 2. 创建一个参数为 first 指向为当前链表中最后一个数据节点,数据值，
27. //                 last 指向为空（最后一个结点）的新结点
28. // 3. 将 last 指向新结点
29. // 4. 判断加入之前 last 指向是否为空，若为空说明链表为空，则把 first 也指向新结点
30. //                 反之，说明链表中有数据，而之前 last 指向的数据节点 next 为 null 所以把之前的
31. //                 最后一个结点的 next 指向当前的新结点
32. // 5. 记得一定要将数据个数或长度 + 1 以及链表修改记录
33. void linkLast(E e) {
34.         final Node<E> l = last;
35.         final Node<E> newNode = new Node<>(l, e, null);
36.         last = newNode;
37.         if (l == null)
38.             first = newNode;
39.         else
40.             l.next = newNode;
41.         size++;
42.         modCount++;
43. }
45. // 根据索引寻找数据值
46. // 将链表长度除以 2 ,然后根据该结果与索引的大小比较
47. // 大的话，说明数据节点离最后一个节点近
48. // 小的话，说明数据节点离第一个节点近
49. // 然后开始进行遍历循环匹配索引值的数据节点
50. Node<E> node(int index) {
51.         // assert isElementIndex(index);
53.         if (index < (size >> 1)) {
54.             Node<E> x = first;
55.             for (int i = 0; i < index; i++)
56.                 x = x.next;
57.             return x;
58.         } else {
59.             Node<E> x = last;
60.             for (int i = size - 1; i > index; i--)
61.                 x = x.prev;
62.             return x;
63.         }
64. }

复制代码

4-ArrayList 和 LinkedList 比较

• ArrayList 和 LinkedList 区别
  

聚集底层布局增删的效率改查的效率ArrayList可变数组较低数组扩容较高LinkedList双向链表较高，通过链表追加较低

• 如何选择 ArrayList 和 LinkedList
  
  
  • 若改查的操作多，选择 ArrayList
    
  • 若增删的操作多，选择 LinkedList
    
  • 通例来说，程序中，80% - 90% 都是查询，因此大部分情况下选择 ArrayList
    
  • 在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是 ArrayList ，另外一个模块是 LinkedList 。也就是说，要根据业务进行选择
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。