public class LinkedList {
// 双向链表实现,无容量限制,但每个元素都要构造Node对象,使用了更多空间
transient Node<E> first;
transient Node<E> last;
// 通过下标寻找元素,是从头遍历的
// 所以get(index) 和 set(index, element)效率低
// 总而言之,凡是带有index查找逻辑的方法,都需要遍历
// 相比ArrayList,免去了复制移动的操作
Node<E> node(int index) {
// assert isElementIndex(index);
// 使用了二分法,所有靠近开头和结尾的元素比较快
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 插入元素到链表头
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; // 整个链表的first指向新元素
if (f == null)
last = newNode;
else
f.prev = newNode; //原来的头结点prev指向新元素
size++;
modCount++;
}
// 插入元素到链表末尾,不用遍历,效率高
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode; // 整个链表的last指针指向新元素
if (l == null)
first = newNode;
else
l.next = newNode; // 原来的last节点next指向新元素
size++; // 增加链表长度
modCount++;
}
// 删除头元素
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next; // 链表的头指针指向元素的next节点
if (next == null)
last = null;
else
next.prev = null; // 元素的next节点的prev置null
size--;
modCount++;
return element;
}
// 删除尾元素
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev; // 链表的last指向元素prev的节点
if (prev == null)
first = null;
else
prev.next = null; // prev节点的next置null
size--;
modCount++;
return element;
}
}
LinkedList小抄
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...