这期内容当中小编将会给大家带来有关如何在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了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。