Java 集合框架系列五：JDK 1.8 LinkedList 详解

电玩女神 2022-12-05 00:59 254阅读 0赞

## LinkedList 继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]  
LinkedList 也是 JDK 1.2 就提供的集合类，它继承了 AbstractSequentialList 抽象类，并实现了 Deque、List、Cloneable、Serializable 接口。

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

## 类文档解读 ##

老规矩，先通过 LinkedList 的类文档了解一下能得到哪些信息。

*  LinkedList 是 List 和 Deque 接口的双端链表实现，LinkedList 没有实现 RandomAccess 表示元素是不允许随机访问的，比如 ArrayList 直接指定索引进行访问。LinkedList 内部数据结构是一个双向链表，就是扩充单链表的指针域，增加一个指向前一个元素的指针 previous。
 *  LinkedList 是有序集合，允许元素为 null，允许元素重复。
 *  LinkedList 由于增删操作不需要像 ArrayList 一样移动底层数组数据，只需要修改链表节点指针，所以效率较高。而改和查，都需要先定位到目标节点，所以效率较低，但是也要注意如果是在指定的位置增删操作，也是需要先查的，所以效率也低。LinkedList 弥补了 ArrayList 增删较慢的问题，但在查找方面又逊色于 ArrayList，所以在使用时需要根据场景灵活选择。
 *  LinkedList 是非线程安全的。可以通过`List list = Collections.synchronizedList(new LinkedList(...));`将 LinkedList 包装为一个线程安全的 List。
 *  LinkedList 的迭代器是 fail-fast 策略的。

## LinkedList API ##

### 成员变量 ###

// LinkedList 中的元素数量 链表的长度
    	transient int size = 0;
    
        // 双向链表的头结点
        transient Node<E> first;
    
        // 双向链表的尾结点
        transient Node<E> last;

### 数据结构 ###

Node 代表一个双端链表中的节点，是 LinkedList 定义的一个内部类。每个节点包含一个指向前节点和后节点的指针。

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 中的数据存储结构以简图的方式表达大概如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]

### 构造方法 ###

因为链表没有长度方面的问题，所以也不会涉及到扩容等问题，其构造函数也十分简洁了。

public LinkedList() { 
        }
    
        public LinkedList(Collection<? extends E> c) { 
            this();
            // 将集合c所有元素插入链表中
            addAll(c);
        }

### LinkedList\#add(E) ###

public boolean add(E e) { 
            linkLast(e);
            return true;
        }
        // 将新元素插入到链表的末尾
        void linkLast(E e) { 
            // 当前链表最后一个节点
            final Node<E> l = last;
            // 新建一个节点作为最后一个节点，前节点是 l
            final Node<E> newNode = new Node<>(l, e, null);
            // 将 last 引用指向新的最后一个节点
            last = newNode;
            // 如果是链表的第一个节点，那么 first 也指向当前节点
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            // 链表长度 + 1
            size++;
            // modCount + 1
            modCount++;
        }

### LinkedList\#addAll(java.util.Collection<? extends E>) ###

按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此 LinkedList 的末尾。指定的集合 c 如果是 null 会抛出 NullPointerException。

**链表批量增加，是靠 for 循环遍历指定集合转换的数组，依次执行插入节点操作。对比 ArrayList 是通过 System.arraycopy 完成批量增加的。**

**通过下标获取某个 Node 的时候，会根据 index 处于前半段还是后半段进行一个折半，以提升查询效率。**

public boolean addAll(Collection<? extends E> c) { 
            // 从末尾添加
            return addAll(size, c);
        }
    
    	public boolean addAll(int index, Collection<? extends E> c) { 
            // 检查 index 是否越界
            checkPositionIndex(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            // c 是空集合返回 false
            if (numNew == 0)
                return false;
    
            Node<E> pred, succ;
            // 在末尾插入节点
            if (index == size) { 
                // 当前节点是 null
                succ = null;
                // 当前最后节点作为前节点
                pred = last;
            } else { 
                // 在中间位置插入节点，找到指定索引的节点
                succ = node(index);
                // 找到指定节点的前一个节点
                pred = succ.prev;
            }
    		// 遍历数组 a
            for (Object o : a) { 
                @SuppressWarnings("unchecked") E e = (E) o;
                // 创建要插入的新节点，指定前节点
                Node<E> newNode = new Node<>(pred, e, null);
                if (pred == null)
                    // 如果 pred 是 null 说明是从 0 位置开始插入
                    first = newNode;
                else
                    // 更新前一个节点的 next 节点
                    pred.next = newNode;
                // pred 指向新插入的节点
                pred = newNode;
            }
    		// 如果是在末尾插入，更新最后一个插入的节点是 last
            if (succ == null) { 
                last = pred;
            } else { 
                pred.next = succ;
                succ.prev = pred;
            }
    		// 链表长度 + numNew
            size += numNew;
            // modCount + 1
            modCount++;
            return true;
        }
    	// 因为对链表的遍历是比较慢的所以这里做了优化
    	Node<E> node(int index) { 
    		// 如果 index 小于链表长度的一半则从首节点开始遍历
            if (index < (size >> 1)) { 
                // 通过 first.next 找
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else { 
                // 如果 index 大于等于链表长度的一半则从尾节点开始遍历
                Node<E> x = last;
                // 通过 last.prev 找
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
    	private void checkPositionIndex(int index) { 
            if (!isPositionIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    	// index 不在 0 ~ size 之间则抛出 IndexOutOfBoundsException
    	private boolean isPositionIndex(int index) { 
            return index >= 0 && index <= size;
        }

### LinkedList\#add(int, E) ###

public void add(int index, E element) { 
            checkPositionIndex(index);
    		// 如果是在末尾插入
            if (index == size)
                linkLast(element);
            else
                // 如果是起始或者中间插入
                linkBefore(element, node(index));
        }
    
    	void linkBefore(E e, Node<E> succ) { 
            // index 位置的节点的前一节点
            final Node<E> pred = succ.prev;
            // 将新节点插入到 index 位置，指定其前一个节点和后一个节点
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            // 长度 + 1
            size++;
            // modCount + 1
            modCount++;
        }

### LinkedList\#get ###

public E get(int index) { 
            checkElementIndex(index);
            // 最多要遍历链表的一半长度，这里做了优化
            return node(index).item;
        }

### LinkedList\#set ###

public E set(int index, E element) { 
            checkElementIndex(index);
            // 找到指定 index 的节点
            Node<E> x = node(index);
            E oldVal = x.item;
            // 替换节点的 item 
            x.item = element;
            return oldVal;
        }

### LinkedList\#size ###

public int size() { 
            return size;
        }

### LinkedList\#contains ###

public boolean contains(Object o) { 
            return indexOf(o) != -1;
        }
    	
    	// 时间复杂度 O(n)
    	public int indexOf(Object o) { 
            int index = 0;
            if (o == null) { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }

### LinkedList\#remove(java.lang.Object) ###

public boolean remove(Object o) { 
            if (o == null) { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    // 删除第一个 null 节点
                    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;
        }
    
    	// 对删除的节点前后节点的指针进行调整
    	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;
            }
    		// gc
            x.item = null;
            // 长度 - 1
            size--;
            // modCount + 1
            modCount++;
            return element;
        }

### LinkedList\#remove(int) ###

public E remove(int index) { 
            checkElementIndex(index);
            return unlink(node(index));
        }

### LinkedList\#clear ###

public void clear() { 
            // 清空每个节点的 item、next、prev 为 null
            for (Node<E> x = first; x != null; ) { 
                Node<E> next = x.next;
                x.item = null;
                x.next = null;
                x.prev = null;
                x = next;
            }
            // first 和 last 设置为 null
            first = last = null;
            // 长度设置为 0
            size = 0;
            // modCount + 1
            modCount ++;
        }

除了这些 API，LinkedList 还实现了 Deque 的 API，如获取链表的头节点 getFirst、删除链表的头节点 removeFirst 等，具体的就不介绍了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 2]

## 总结 ##

LinkedList非常适合大量数据的插入与删除，但其对处于中间位置的元素，无论是增删还是改查都需要折半遍历，这在数据量大时会十分影响性能。在使用时，尽量不要涉及查询与在中间插入数据，另外如果要遍历，也最好使用`foreach`，也就是`Iterator`提供的方式。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3395cdb1af974b11a8ae22fe06d5f7d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/f01da98c26e640a187373d61bb65a175.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/ab992c86a5d64383a1484f806019e5d1.png