LinkedList详解

一.关于 LinkedList 常见内容

　　描述:实现 List<E> 接口;元素可排序,可重复,可为 null ,不是线程安全的.

　　继承以及实现关系:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

　　描述: List<E> 接口定义了列表的方法和默认实现, AbstractSequentialList<E> 继承自 AbstractList<E> ,在其基础上又添加了迭代查询的实现. Deque<E> 接口表示含有队列、双端队列的API,是队列的一种实现, Cloneable 接口表示可以克隆, Serializable 接口表示可以序列化,用于数据传输

二. LinkedList 的实现原理

　　 LinkedList 是通过链表实现的,每一个元素都存放在一个链表的节点中,对列表的操作就是对链表的操作,由于不支持随机访问,所以 LinkedList 只能通过顺序访问(是链表结构导致的),但由于添加或者删除元素时只是修改相关节点中对应的引用变量,所以单纯的增删操作比数组和 ArrayList 更快

三.定义的属性和节点

　　属性:

    // 大小
    transient int size = 0;
    // 头结点
    transient Node<E> first;
    // 尾节点
    transient Node<E> last;

　　　　大小:表示列表当前存放的元素数量

　　　　头结点:表示列表的第一个节点(引用)

　　　　尾节点:表示列表的最后一个节点(引用)

　　　　由节点的内容可以看出 LinkedList 维护的是一个双向链表

　　节点:

 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     }

View Code

　　　　描述:每一个节点中都包含了元素和前后节点的引用变量

三.一些重要的方法

　　1.构造方法

1     public LinkedList() {
2     }
3 
4     public LinkedList(Collection<? extends E> c) {
5         this();
6         addAll(c);
7     }

　　　　描述: LinkedList 在创建是都是空的,没有任何节点

　　2.node

 1     // 查找指定位置的节点
 2     Node<E> node(int index) {
 3         // assert isElementIndex(index);
 4         // index 近头
 5         if (index < (size >> 1)) {
 6             Node<E> x = first;
 7             for (int i = 0; i < index; i++)
 8                 x = x.next;
 9             return x;
10         }
11         // index 近尾
12         else {
13             Node<E> x = last;
14             for (int i = size - 1; i > index; i--)
15                 x = x.prev;
16             return x;
17         }
18     }

　　　　描述:为了提高效率,node方法在进行节点查找时,会先判断index是近头还是近尾,近头就从头结点开始查找,近尾就从尾节点开始查找;相似的,在进行元素查找时(即indexOf和lastIndexOf方法),也是使用的近头和近尾再查找

　　3.linkFirst

 1     // e 作为头元素，头插
 2     private void linkFirst(E e) {
 3         final Node<E> f = first;
 4         // 新建一个节点，内容为 e 无前节点，后节点为原来的头节点
 5         final Node<E> newNode = new Node<>(null, e, f);
 6         first = newNode;
 7         if (f == null)
 8             // 如果原头节点不存在，即为空链表，则头尾节点是同一个节点
 9             last = newNode;
10         else
11             // 如果原头节点存在，则将原头节点的前一节点置为新建节点
12             f.prev = newNode;
13         size++;
14         modCount++;
15     }

　　　　描述:在列表头添加一个新元素,新元素的节点作为列表的新的头节点,应用有双端队列中头部添加元素,压栈操作

　　4.linkLast

 1     // e 作为尾节点，尾插
 2     void linkLast(E e) {
 3         final Node<E> l = last;
 4         // 新建一个节点，前一节点为原尾节点，无后一节点
 5         final Node<E> newNode = new Node<>(l, e, null);
 6         // 更新尾节点
 7         last = newNode;
 8         if (l == null)
 9             // 若原尾节点为 null ，则为空链表，头尾节点是同一节点
10             first = newNode;
11         else
12             // 否则原尾节点的下一个节点是新的尾节点
13             l.next = newNode;
14         size++;
15         modCount++;
16     }

　　　　描述:在列表尾部添加一个元素,应用有想队列(单端)中添加元素

　　5.linkBefore

 1     // e 元素插入某一元素之前，该元素不为 null
 2     void linkBefore(E e, Node<E> succ) {
 3         // assert succ != null;
 4         // 定位目标节点的前一节点
 5         final Node<E> pred = succ.prev;
 6         // 新建节点的前一节点为目标节点的前一节点，后一节点为目标节点
 7         final Node<E> newNode = new Node<>(pred, e, succ);
 8         // 修改目标节点的前一节点为新节点
 9         succ.prev = newNode;
10         if (pred == null)
11             // 如果目标节点的原前一节点为 null，则表示该节点为头节点，需将新节点置为头节点
12             first = newNode;
13         else
14             // 否则需将目标节点的原前一节点的下一节点置为新节点
15             pred.next = newNode;
16         size++;
17         modCount++;
18     }

　　6.unlink

 1     // 删除某一不为空的节点
 2     E unlink(Node<E> x) {
 3         // assert x != null;
 4         // 取节点的内容和前后节点
 5         final E element = x.item;
 6         final Node<E> next = x.next;
 7         final Node<E> prev = x.prev;
 8 
 9         if (prev == null) {
10             // 前一节点为 null ，则该节点为头节点，将头节点置为其后一节点
11             first = next;
12         } else {
13             // 否则前一节点的后一节点置为该节点的后一节点，该节点的前一节点置为 null
14             prev.next = next;
15             x.prev = null;
16         }
17 
18         if (next == null) {
19             // 如果该节点的后一节点为 null ，即该节点为尾节点，则将尾节点置为该节点的前一节点
20             last = prev;
21         } else {
22             // 否则该节点的后一节点的前一节点置为该节点的前一节点，该节点的后一节点置为 nulll
23             next.prev = prev;
24             x.next = null;
25         }
26 
27         x.item = null;
28         size--;
29         modCount++;
30         return element;
31     }

　　7.unlinkFirst

 1     // 头删
 2     private E unlinkFirst(Node<E> f) {
 3         // assert f == first && f != null;
 4         // 取头节点内容和后一节点
 5         final E element = f.item;
 6         final Node<E> next = f.next;
 7         f.item = null;
 8         f.next = null; // help GC
 9         // 将头节点置为原头节点的后一节点
10         first = next;
11         if (next == null)
12             // 如果没有后一个节点，即只有一个节点，则尾节点也置为 null
13             last = null;
14         else
15             // 否则后一个节点的前一节点置为 null
16             next.prev = null;
17         size--;
18         modCount++;
19         return element;
20     }

　　　　描述:从列表头部删除一个元素,应用有从队列中取元素,应用有出栈

　　8.unlinkLast

 1     // 尾删
 2     private E unlinkLast(Node<E> l) {
 3         // assert l == last && l != null;
 4         // 取尾节点的内容和其前一节点
 5         final E element = l.item;
 6         final Node<E> prev = l.prev;
 7         l.item = null;
 8         l.prev = null; // help GC
 9         // 新的尾节点是原尾节点的前一节点
10         last = prev;
11         if (prev == null)
12             // 如果原尾节点没有前一节点，即只有一个节点，则头节点置为 null
13             first = null;
14         else
15             // 否则原尾结点的前一节点的下一节点置为 null
16             prev.next = null;
17         size--;
18         modCount++;
19         return element;
20     }

　　　　描述:从列表尾部删除一个元素

　　9.定位方法

1     // 已存在的元素的 index
2     private boolean isElementIndex(int index) {
3         return index >= 0 && index < size;
4     }
5 
6     // 迭代或者添加操作的有效位置的 index
7     private boolean isPositionIndex(int index) {
8         return index >= 0 && index <= size;
9     }

五.常用的API

　　1.get

1     public E get(int index) {
2         checkElementIndex(index);
3         // 查询指定位置的节点
4         return node(index).item;
5     }

　　2.set

1     public E set(int index, E element) {
2         checkElementIndex(index);
3         Node<E> x = node(index);
4         E oldVal = x.item;
5         x.item = element;
6         return oldVal;
7     }

　　3.indexOf

 1     public int indexOf(Object o) {
 2         int index = 0;
 3         // null 和非 null 的判断方式不一样
 4         if (o == null) {
 5             for (Node<E> x = first; x != null; x = x.next) {
 6                 if (x.item == null)
 7                     return index;
 8                 index++;
 9             }
10         } else {
11             for (Node<E> x = first; x != null; x = x.next) {
12                 if (o.equals(x.item))
13                     return index;
14                 index++;
15             }
16         }
17         return -1;
18     }

　　　　描述:lastIndexOf也相似,只是开始的位置的尾节点,一次向前查找

　　4.add

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

　　　　描述:add方法是直接调用尾插方法,强制返回true

　　5.remove

1     public E remove(int index) {
2         checkElementIndex(index);
3         return unlink(node(index));
4     }

　　6.toArray

1     public Object[] toArray() {
2         Object[] result = new Object[size];
3         int i = 0;
4         for (Node<E> x = first; x != null; x = x.next)
5             result[i++] = x.item;
6         return result;
7     }

　　　　描述:新建一个等长数组,遍历集合挨个放入

　　6.队列中定义的方法如:peek,poll,offer;以及栈定义的方法:push,pop

受限于个人水平,如有错误或者补充望请告知(博客园:xiao_lin_unit)