双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项前后项即可,插入数据较快;其实主要是数据结构的东西
三个属性:头尾节点、size
Node节点(内部静态私有类)
构造方法:
无参:构造一个空链表。
有参构造函数:
public LinkedList(Collection<? extends E> c) {
this();//调用无参构造方法构造一个空的链表
addAll(c);
}
先产生一个空链表,再调用addAll(Collection<? extends E> c)方法,再有addAll调用addAll(int index, Collection<? extends E> c),传入的index为size,在构造函数这也就是从0开始覆盖,
add过程:先对index的两种情况进行了处理:一种是index==size(在尾部插入),另一种是index,遍历传入的c(将c转换为Object),创建newNode,依次循环即可
支持放入null元素,但不是说节点为null,而是节点中的item为null
add方法:
直接调用linkLast,在尾部添加节点
linkLast的步骤:
获得last节点为l,创建新对象(设置传入的对象的prev为l节点,next为null),再设置last为新创建的对象,最后判断l是否为空,如果是,first为新创立的节点,否则,l.next为新创立的对象,再修改size
此时堆栈的形式为:
最后,双向链表:
remove方法:
嗯,记得先覆盖equals方法
L6.jpgutil集合支持往里面放入null值元素(不是null)。当然了,代码主要功能是调用了unlink方法
unlink步骤为:先判断前后节点是否为空并设置,最后另x.item = null,更新size等,返回
复杂度:
LinkedList底层链表删除元素只是简单的修改了一下引用地址,时间复杂度为O(1)。
参考:https://zhuanlan.zhihu.com/p/28101975
网友评论