Java集合之LinkedList源码解析

时间:2021-11-17 14:08:46

下面我们来看看LinkedList的底层实现,

它继承抽象方法AbstractSequentialList<E>,实现List<E>, Deque<E>, Cloneable, java.io.Serializable接口

它的成员属性有,

 1     transient int size = 0;
 2     transient Node<E> first;
 3     transient Node<E> last;

 

size表示该集合的元素个数,初始值为0,first指向第一个Node,last指向最后一个Node,

Node<E>是一个静态内部类,

 1 private static class Node<E> {
 2         E item;
 3         Node<E> next;
 4         Node<E> prev;
 5 
 6         Node(Node<E> prev, E element, Node<E> next) {
 7             this.item = element;
 8             this.next = next;
 9             this.prev = prev;
10         }
11 }

 

item指当前元素,next是下一个元素的引用,prev是前一个元素的引用,

 

LinkedList是一个双向链表,

百科中对于链表的定义是

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。

所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

 

新增元素

 假如我们有如下的代码,

1 public static void main(String[] args) {
2         LinkedList list  = new LinkedList<String>();
3         list.add("ABC");
4 }

 我们进到add(E e),

1 public boolean add(E e) {
2         linkLast(e);
3         return true;
4 }

 第2行,进到linkLast(E e),

 1 void linkLast(E e) {
 2         final Node<E> l = last;
 3         final Node<E> newNode = new Node<>(l, e, null);
 4         last = newNode;
 5         if (l == null)
 6             first = newNode;
 7         else
 8             l.next = newNode;
 9         size++;
10         modCount++;
11 }

第2行,将队列的尾节点赋值给 l

第3行,构建一个Node,

第4行,新构建的Node追加到队尾,

第5-8行,判断原始为节点是否为空,如果为空,当前Node是首次新增,

第9行,size自增,

 

查找元素

 假如我们有如下一段代码

1 public static void main(String[] args) {
2         LinkedList list  = new LinkedList<String>();
3         list.add("ABC");
4         list.add("DEF");
5         
6         list.get(0);
7 }

 进到get(int index)方法,

1 public E get(int index) {
2         checkElementIndex(index);
3         return node(index).item;
4 }

第2行,检验index是否是在链表内

第3行,根据index得到node,该node的item就是要的值,下面进到node(int index)

 1 Node<E> node(int index) {
 2         // assert isElementIndex(index);
 3 
 4         if (index < (size >> 1)) {
 5             Node<E> x = first;
 6             for (int i = 0; i < index; i++)
 7                 x = x.next;
 8             return x;
 9         } else {
10             Node<E> x = last;
11             for (int i = size - 1; i > index; i--)
12                 x = x.prev;
13             return x;
14         }
15 }

 第4~14行,说的如果index比 size/2 小,则从前往后搜索,否则,从后往前搜索 

 

插入元素

假如我们我如下这段代码,

1 public static void main(String[] args) {
2         LinkedList<String> list  = new LinkedList<String>();
3         list.add("ABC");
4         list.add("DEF");
5         
6         list.add(1, "XYZ");
7         System.out.print(list);   //[ABC, XYZ, DEF]
8 }

 在index个元素后面,插入element,我们进到add(int index, E element),

1 public void add(int index, E element) {
2         checkPositionIndex(index);
3 
4         if (index == size)
5             linkLast(element);
6         else
7             linkBefore(element, node(index));
8 }

第2行,index校验,必须大于等于0,且小于等于size,

第4~7行,如果是在size个元素后插入,直接在链表尾部追加,和上面的新增方式一样,

否则,先检索到index的元素,把待插入的元素放在node(index)之前即可,

 

 

删除元素

删除元素有两种,第一按照索引删除(从0开始),第二种是根据值来删除,因为LinkedList中元素可重复,在源码中从头开始遍历直到找到一个为止,

两种方式分两步

1.找到对应的Node<E>,

2.调用unlink(Node<E> x)

下面来看一下unlink(Node<E> x),

 1 E unlink(Node<E> x) {
 2         // assert x != null;
 3         final E element = x.item;
 4         final Node<E> next = x.next;
 5         final Node<E> prev = x.prev;
 6 
 7         if (prev == null) {
 8             first = next;
 9         } else {
10             prev.next = next;
11             x.prev = null;
12         }
13 
14         if (next == null) {
15             last = prev;
16         } else {
17             next.prev = prev;
18             x.next = null;
19         }
20 
21         x.item = null;
22         size--;
23         modCount++;
24         return element;
25 }

 

这里我就不再逐行解释了,比较简单。