LinkedList详解

查找

ArrayList两种查找 get(index) get(Object)（内部还是get(index)去遍历的） 因为是连续的存储单元。所以遍历很快。

基本属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * LinkedList实现list和Deque,实现所有list可选操作，并且可以包含null.
 * 
 * 并且LinkedList是双向链表，操作索引可以从开始或者结尾或者指定位置进行遍历
 * 
 * linkedList不是线程安全的
 * 如果多线程同时操作修改操作是不安全的
 * 
 * 迭代器快速报错	。在迭代器开始后的任何修改都会报错
 */
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{	
transient int size = 0;
   /**
    * Pointer to first node.
    * Invariant: (first == null && last == null) ||
    *            (first.prev == null && first.item != null)
    */
   transient Node<E> first;
   /**
    * Pointer to last node.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
   transient Node<E> last;
//内部类
private static class Node<E> {
       E item;
       Node<E> next;
       Node<E> prev;
       Node(Node<E> prev, E element, Node<E> next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
   }

通过数据结构和实现类能够分析出来linkedList是双向链表。一个内部类是基本数据结构

默认构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

构造方法同ArrayList传入一个集合转化成LinkedList
新增方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 把新加的结点放到最后
    * Appends the specified element to the end of this list.
    *
    * <p>This method is equivalent to {@link #addLast}.
    *
    * @param e element to be appended to this list
    * @return {@code true} (as specified by {@link Collection#add})
    */
   public boolean add(E e) {
       linkLast(e);
       return true;
   }
/**
    * Links e as last element.
    */
   void linkLast(E e) {
	//这种赋值操作目的主要是都想使用最后一个进行判断，并且l不可变
       final Node<E> l = last;
	//生成新节点
       final Node<E> newNode = new Node<>(l, e, null);
	//赋值尾部结点
       last = newNode;
	//维护双向关系
       if (l == null)
           first = newNode;
       else
           l.next = newNode;
       size++;
       modCount++;
   }

图解add()方法

addAll()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public boolean addAll(int index, Collection<? extends E> c) {
       checkPositionIndex(index);
       Object[] a = c.toArray();
       int numNew = a.length;
       if (numNew == 0)
           return false;
       Node<E> pred, succ;
	//末尾插入
       if (index == size) {
           succ = null;
           pred = last;
       } else {
		//插入位置的前置结点后继结点
           succ = node(index);
           pred = succ.prev;
       }
       for (Object o : a) {
           @SuppressWarnings("unchecked") E e = (E) o;
           Node<E> newNode = new Node<>(pred, e, null);
           if (pred == null)
               first = newNode;
           else
               pred.next = newNode;
           pred = newNode;
       }
       if (succ == null) {
           last = pred;
       } else {
           pred.next = succ;
           succ.prev = pred;
       }
       size += numNew;
       modCount++;
       return true;
   }

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public boolean remove(Object o) {
       if (o == null) {
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
   }
	/**
    * Unlinks non-null node x.
    */
   E unlink(Node<E> x) {
       // assert x != null;
       final E element = x.item;
	
	//当前移除元素的后一个
       final Node<E> next = x.next;
	//当前移除元素的前一个
       final Node<E> prev = x.prev;
	//移除的第一个元素
       if (prev == null) {
           first = next;
       } else {
		//前一个的后一个变成当前移除 元素的后一个
           prev.next = next;
           x.prev = null;
       }
	//当前是最后一个元素
       if (next == null) {
		//移除元素的前一个变成最后一个
           last = prev;
       } else {
           next.prev = prev;
           x.next = null;
       }
       x.item = null;
       size--;
       modCount++;
       return element;
   }

先得到要移除元素的前置节点。后置节点。判断前置节点和头结点的关系。
后置节点和最后节点的关系。可以得出结论链表的移除和新增很简单只需要做简单的节点移动。