Loading... # LinkedList 源码笔记 ## 个人理解 LinkedList由双向链表实现，每个链表内装着指向下一链表节点的地址值，因此想要查找LinkedList中某一个节点的元素值，就需要从头开始判断元素值，不是则找下一地址，这使得增删改查中间元素所花费的代价过于大，而首尾的增删则较为简单，在原有节点上修改/添加地址值即可。常用栈、队列来与LinkedList进行类比。 ## 概述 LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(它是个接口名字)。 关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。 LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用 `Collections.synchronizedList() `方法对其进行包装。 ## 实现 双向链表  双向链表的每个节点用内部类`Node`表示。LinkedList通过`first`和`last`引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候`first`和`last`都指向`null`。 Node是私有内部类: ```java 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; } } ``` ## add() add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。  ```java //add(E e) public boolean add(E e) { 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++; return true; } //add(int index, E element) public void add(int index, E element) { checkPositionIndex(index);//index >= 0 && index <= size; if (index == size)//插入位置是末尾，包括列表为空的情况 add(element); else{ Node<E> succ = node(index);//1.先根据index找到要插入的位置 //2.修改引用，完成插入操作。 final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null)//插入位置为0 first = newNode; else pred.next = newNode; size++; } } ``` ## remove() remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(Object o)，另一个是删除指定下标处的元素remove(int index)。 两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法，而remove(int index)使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个remove()方法都是通过 `unlink(Node<E> x)` 方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。 ```java //unlink(Node<E> x)，删除一个Node E unlink(Node<E> x) { 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;//let GC work size--; return element; } ``` ## get() `get(int index)`得到指定下标处元素的引用，通过调用上文中提到的`node(int index)`方法实现。 ```java public E get(int index) { checkElementIndex(index);//index >= 0 && index < size; return node(index).item; } ``` 参考：[Java LinkedList源码剖析](https://www.cnblogs.com/CarpenterLee/p/5457150.html) 最后修改：2022 年 09 月 25 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 本作品采用 CC BY-NC-SA 4.0 International License 进行许可。
