如何在Java 中实现LinkedList

这期内容当中小编将会给大家带来有关如何在Java 中实现LinkedList，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

来看一下 LinkedList 中的属性：

//链表的节点个数
transient int size = 0;
//指向头节点的指针
transient Node<E> first;
//指向尾节点的指针
transient Node<E> last;

1、结点结构

Node 是在 LinkedList 里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域 item，一个后置指针 next，一个前置指针 prev。

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;
 }
}

2、添加元素

对于链表这种数据结构来说，添加元素的操作无非就是在表头/表尾插入元素，又或者在指定位置插入元素。因为 LinkedList 有头指针和尾指针，所以在表头或表尾进行插入元素只需要 O(1) 的时间，而在指定位置插入元素则需要先遍历一下链表，所以复杂度为 O(n)。

在表头添加元素的过程如下：

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点，源码的实现如下：

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++;
}

在表尾添加元素跟在表头添加元素大同小异，如图所示

当向表尾插入一个节点时，很显然当前节点的后继一定为 null，而前驱结点是 last指针指向的节点，然后还要修改 last 指针指向新的尾节点。此外，还要修改原来尾节点的后继指针，使它指向新的尾节点，源码的实现如下：

void linkLast(E e) {
 final Node<E> l = last;
 //当前节点的前驱指向尾节点，后继指向 null
 final Node<E> newNode = new Node<>(l, e, null);
 //尾指针指向新的尾节点
 last = newNode;
 //如果原来有尾节点，则更新原来节点的后继指针，否则更新头指针
 if (l == null)
 first = newNode;
 else
 l.next = newNode;
 size++;
 modCount++;
}

最后，在指定节点之前插入，如图所示

当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点，源码的实现如下：

void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 //指定节点的前驱
 final Node<E> pred = succ.prev;
 //当前节点的前驱为指点节点的前驱，后继为指定的节点
 final Node<E> newNode = new Node<>(pred, e, succ);
 //更新指定节点的前驱为当前节点
 succ.prev = newNode;
 //更新前驱节点的后继
 if (pred == null)
 first = newNode;
 else
 pred.next = newNode;
 size++;
 modCount++;
}

上述就是小编为大家分享的如何在Java 中实现LinkedList了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。