前言
LinkedList在我们平时工作中使用频率非车高，底层是基于双向链表数据结构实现，下面从经常使用的几个方法来了解其原理。
正文
结构
我们先看下LinkedList的重要属性
/** 存储链表数量 */ transient int size = 0; /** 存储链表的头节点 */ transient Node<E> first; /** 存储链表的尾节点 */ 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; } }
添加方法
方法：add(E e)
public boolean add(E e) { linkLast(e); return true; }
方法：add(int index, E element)
public void add(int index, E element) { //校验下标范围是否在链表范围内 checkPositionIndex(index); //插入位置等于链表容量大小，证明是需要插入到尾部。 //因为下标是从0算起的，所以链表中size大小的位置肯定是为空的。 if (index == size) linkLast(element); else //找出下标对应链表中的节点，并在其前面进行插入 linkBefore(element, node(index)); }
这里会根据下标找出当前链表中的那个节点，然后在其前面位置进行插入，相当于顶替了其位置，将原来那个节点挤到它的后面去。
查找过程如下：
方法：linkLast(E e)
void linkLast(E e) { //保存一下尾节点 final Node<E> l = last; //创建一个新的节点，并对其属性进行赋值。将e作为其数据值， //将其上节点指向l，将下节点指向null final Node<E> newNode = new Node<>(l, e, null); //将链表的尾部引用指向新添加的节点 last = newNode; //如果头节点为空，证明新创的节点为该链表中的第一个 if (l == null) first = newNode; else //将新节点与之前的尾节点进行关联 l.next = newNode; size++; modCount++; }
该方法采用尾插法，将数据放到尾部。
方法：linkBefore(E e, Node succ)
void linkBefore(E e, Node<E> succ) { // assert succ != null; //保存其上个节点引用的值 final Node<E> pred = succ.prev; //新建节点，将其下个节点引用指向succ，也就是上面通过下标查找出来的那个节点 final Node<E> newNode = new Node<>(pred, e, succ); //将succ上个节点指向新插入的节点，建立关联 succ.prev = newNode; if (pred == null) //进入这里，证明之前通过下标查找出来的值是个头节点 first = newNode; else //将上节点的引用指向新节点 pred.next = newNode; size++; modCount++; }
方法：linkFirst(E e)
private void linkFirst(E e) { //保存第一个节点 final Node<E> f = first; //创建新节点，将尾部指向当前链表的头节点，其上节点赋值为null final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) //进入这里代表当前链表是空的，所以尾部节点赋值为新插入节点 last = newNode; else //将之前链表的头节点与新插入节点建立连接 f.prev = newNode; //统计值 size++; modCount++; }
查询方法
方法：get(int index)
public E get(int index) { //校验下标是否在链表当前容量大小范围内 checkElementIndex(index); return node(index).item; }
Node<E> node(int index) { // assert isElementIndex(index); //将二进制位右移动1位，相当于除2 //看是位于左边还是右边 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
通过二切法可以提高查询效率。
方法：peek()
public E peek() { //获取头节点值 final Node<E> f = first; return (f == null) ? null : f.item; }
方法：poll()
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
获取头节点值，并移除头节点
删除方法
方法：remove()
public E remove() { return removeFirst(); }
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
方法：remove(int index)
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
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; } //将值置为NULL x.item = null; size--; modCount++; return element; }
总结
链表不需要指定容量，只要内存够大，就可以一直存储下去。链表存储时，分配完内存空间后，只需要将引用进行关联就可以，比起ArrayList可能会造成空间移动，效率高得多。但是在存储时，我们看到它是采用遍历的方式，进行下标查询，随便使用了二分进行切割，但在数据量大的情况下自旋时间长，对CPU的消耗比较大。
————————————————
版权声明：本文为CSDN博主「@猪大肠」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_45031612/article/details/129206513
