下面我们来看看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 }
这里我就不再逐行解释了,比较简单。