Java LinkedList 双向链表实现原理
相信大家都明白 LinkedList 是基于双向链表而实现的，本篇文章主要讲解一下双向链表的实现，并且我们参考 LinkedList 自己实现一个单链表尝试一下。
什么是链表？简单的来讲一下什么是链表：首先链表是一种线性的数据结构（其他数据结构还有，树、图），是在每一个节点里存到下一个节点（next）的指针（Pointer）。
链表最大的好处则是采用了见缝插针的方式，链表中的每一个节点分布在内存的不同位置（链表不需要一块连续完整的空间），依靠 next 指针关联起来。这样可以灵活有效地利用零散的碎片空间。由于不必须按顺序存储，链表的插入和删除操作可以达到 O(1) 的复杂度。
而双向链表比单向链表稍微复杂一些（仅仅一些），它的每一个节点除了拥有 data 和 next 指针，还拥有指向前置节点的 prev 指针。意思就是：单向链表只可以访问到下一个节点，而双向链表不仅可以访问下一个节点还可以访问上一个节点。
图我懒的画出自：https://zhuanlan.zhihu.com/p/29627391，下面那个图也是。
大家如果看过 LinkedList 就可以发现它就是使用双向链表实现的，这里使用两个 LinkedList 提供的方法说明一下其背后的实现原理，就使用一个 add() 方法加一个 remove() 方法吧。
node 构造器
private static class Node {
E item;
/*
从属性可以看出来是双向链表
next -> 下一个节点; prev -> 上一个节点
*/
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
add() 方法，稍微注意一下：add() 被重载了，下面的 add() 方法直接将元素追加到链表的尾部不需要指定下标，另外一个 add() 可以指定下标（index）进行插入数据操作。
// 方法入口
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
/*
1: 获取当先的最后一个元素, 即: 尾部
2: 初始化 Node, 可以看到这里直接将 l 一起也传递了过去, 因为之前说过
双向链表不仅可以访问下一个节点还可以访问上一个节点.
现在插入了新的元素那么原来的尾元素就成为了现在新的尾元素的上一个节点.
所以现在的尾元素的上一个节点是 l, 下一个节点一定是 null.
3: 将创建的新节点指定为 last 节点, 这里 LinkedList 提供了 head、last 方便获取以及指定获取头节点、尾节点
*/
final Node l = last;
final Node newNode = new Node(l, e, null);
last = newNode;
/*
4: 这里使用 final 修饰 l 也是很厉害的, 如果 l == null 就证明了是刚创建并且没有使用的, 所以把新节点指定为 head(头节点)
5：否则 l 的下一个节点 next 属性直接指向新节点
6：链表大小 +1, 这里的 size 也是 LinkedList 提供的一个属性, 大家平时使用的 list.size() 方法就是直接返回的这个 size
即: return size;
*/
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
remove()，也是被重载了，我刚试了一下默认的直接 remove() 直接从 0 下标开始删除一位，另一个 remove() 是通过指定下标进行删除，最后一个通过指定值去删除。咱们在这里要说的就是通过 index 下标去删除。
// 方法入口
public E remove(int index) {
/*
1: 检查 index 是否越界. index >= 0 && index < size
2: 调用删除(实际就是 GC), 先获取了 node 然后调用 unlink 方法.
*/
checkElementIndex(index);
return unlink(node(index));
}
// 获取 Node 这里使用了二分查找思想, 但并没有像递归一样, 而只执行了一次.
Node node(int index) {
/*
1: 判断 index 范围, 按位运算获取当先链表 size 的中间值
2: 小于中间值则从 first 节点开始遍历也是就是前问说的 head
大于中间值则从 last 尾巴节点开始遍历, 这样如果大量数据最不理想的情况下效率也是相同的
3: 返回节点
*/
if (index > 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 调用删除(实际就是 GC)
E unlink(Node x) {
/*
1: 获取删除节点的元素, 没有意义也不知道为什么都要删除了为什么还要获取一下再返回出去?
2: 获取当前删除节点的下一个节点
3: 获取当前删除节点的上一个节点
这里包括上面之所以都使用 final 修饰变量, 是为了数据一致性（原因之一）.
*/
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;
/*
4: 如果删除节点的上一个节点是 null 就证明了它是头节点 head, 将删除节点的下一个节点指定为 head
不是 null 则将**上一个节点的 next 指针指向删除节点的 next 节点**
然后将删除节点的上一个节点指针赋为 null, 等着被 GC, x.prev = null;
*/
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
/*
5: 如果 next 是 null 是证明删除节点没有下一个节点, 则将删除节点的上一个节点指定为 last 节点
如果 next 不是 null 则将**下一个节点对上一个节点的指针修改为删除节点的上一个节点** 这句话有点绕一定要理解.
然后将删除节点的下一个节点指针赋为 null, 等着被 GC, x.next = null;
*/
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
/*
6: 到这一步 x.item = null; 一个 Node 中所有的属性都已经是 null 了, 等着被 GC 回收就可以了
然后删除节点的上下节点指针已经更新完成, 已经完成了删除操作了 90% 了
7: size - 1, 当前链表的长度 -1
完毕.
*/
x.item = null;
size--;
modCount++;
return element;
}
自定义单向链表
下面关于单向链表的操作是最基本的，需要完善的地方还是有的。remove() 方法暂时只提供了删除 head 元素，添加了一个检查链表的方法。
public class LinkedTable {
private Node head;
private Node last;
private Long size = 0L;
public void linkLast(Object object) {
Node newNode = new Node(object);
if (size == 0) {
// first data
head = newNode;
last = newNode;
} else {
// last data
last.next = newNode;
last = newNode;
}
size++;
}
public void linkFirst(Object object) {
Node newNode = new Node(object);
newNode.next = head;
head = newNode;
size++;
}
private Object unlinkFirst(Node node) {
final Object o = node.object;
final Node next = node.next;
// call GC
head.object = null;
head.next = null;
head = next;
if (next == null) {
last = null;
}
size--;
return o;
}
public Object removeFirst() {
Node node = head;
if (node == null) {
throw new IndexOutOfBoundsException("Index out of length! ");
}
return unlinkFirst(node);
}
void add(Object object) {
linkLast(object);
}
void addLast(Object object) {
linkLast(object);
}
void addFirst(Object object) {
linkFirst(object);
}
Object getLast() {
return last.object;
}
Object getFirst() {
return head.object;
}
// check linked table
public void checkLinkedTable() {
Node node = head;
while (node != null) {
System.out.print(node.object.toString() + " ");
node = node.next;
}
System.out.println("");
}
public Object get(Long index) throws Exception {
if (index = size) {
throw new IndexOutOfBoundsException("Index out of length! ");
}
if (index == 0) {
return head.object;
}
if (index == size - 1) {
return last.object;
}
Node node = head;
for (Long i = 0L; i < index; i++) {
node = node.next;
}
return node.object;
}
public Long getSize() {
return size;
}
private static class Node {
Object object;
Node next;
public Node(Object o) {
this.object = o;
}
}
}
验证自定义单向链表
public class test {
public static void main(String...args) throws Exception {
LinkedTable linkedTable = new LinkedTable();
linkedTable.add("BKN481");
linkedTable.add("BKN482");
linkedTable.add("BKN483");
linkedTable.add("BKN484");
linkedTable.add("BKN485");
linkedTable.checkLinkedTable();
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.removeFirst();
System.out.println(linkedTable.getSize());
linkedTable.checkLinkedTable();
}
}
输出：
BKN481 BKN482 BKN483 BKN484 BKN485
4
3
2
1
BKN485
完毕，欢迎批评指教。
作者：SunnyJim
