Java LinkedList 双向链表实现原理双向链表实现原理
相信大家都明白相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下自己实现一个单链表尝试一下。
什么是链表?什么是链表?
简单的来讲一下什么是链表:首先链表是一种线性的数据结构(其他数据结构还有,树、图),是在每一个节点里存到下一个节点(next)的指针(Pointer)。
链表最大的好处则是采用了见缝插针的方式,链表中的每一个节点分布在内存的不同位置(链表不需要一块连续完整的空间),依靠 next 指针关联起来。这样可以灵活有效地利用零散的碎片空间。
由于不必须按顺序存储,链表的插入和删除操作可以达到 O(1) 的复杂度。
而双向链表比单向链表稍微复杂一些(仅仅一些),它的每一个节点除了拥有 data 和 next 指针,还拥有指向前置节点的 prev 指针。意思就是:单向链表只可以访问到下一个节点,而双向链
表不仅可以访问下一个节点还可以访问上一个节点。
双向链表双向链表
图我懒的画出自:https://zhuanlan.zhihu.com/p/29627391,下面那个图也是。
单向链表单向链表
LinkedList 实现实现
大家如果看过大家如果看过 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) {
评论0