首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

java基础之LinkedList

我是个木得感情的更新机器

LinkedList的属性:

// 链表的表头,表头无数据。Entry是个链表类数据结构,详细明细请看后面。

private transient Entry header = new Entry(null, null, null);

// LinkedList中元素个数,即当前容量

private transient int size = 0;

LinkedList节点所对应的数据结构

包含三个属性:上一节点,下一节点,节点值。

从这里可以看出,LinkedList其实是一个双向链表,可以向前后两个方向获取。

private static class Entry {

// 当前节点的值

E element;

// 下一个节点

Entry next;

// 上一个节点

Entry previous;

//节点的构造函数。

Entry(E element, Entry next, Entry previous) {

this.element = element;

this.next = next;

this.previous = previous;

}

}

LinkedList的随机访问

获取LinkedList中指定位置的节点,每次都从头或者尾开始查找,效率最低。因此,在遍历时劲量不要使用这种方式,应该使用迭代器或者for each方式。

private Entry entry(int index) {

if (index = size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);

Entry e = header;

// 获取index处的节点。

// 若index 小于长度的1/2,则从前先后查找

if (index > 1)) {

for (int i = 0; i

e = e.next;

} else {

// 否则,从后向前查找

for (int i = size; i > index; i--)

e = e.previous;

}

return e;

}

LinkedList迭代器:

遍历时初始化迭代器从头或尾开始找到位置,之后使用每次只查询下一个即可。

private class ListItr implements ListIterator {

// 上一次返回的节点 private Entry lastReturned = header;

// 下一个节点

private Entry next;

// 下一个节点对应的索引值

private int nextIndex;

// 预期的改变次数。用来实现fail-fast机制。 private int expectedModCount = modCount;

// 构造函数。

// 从index位置开始进行迭代

ListItr(int index) {

// index的有效性判断

if (index size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);

// 若 index 小于双向链表长度的一半,则从第一个元素开始往后查找;

if (index > 1)) {

next = header.next; for (nextIndex=0; nextIndex

next = next.next;

} else {

// 否则,从最后一个元素往前查找

next = header; for (nextIndex=size; nextIndex>index; nextIndex--)

next = next.previous;

}

}

// 实现fail-fast机制,前文说过。

final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException();

}

}

反向迭代器实现:

private class DescendingIterator implements Iterator {

final ListItr itr = new ListItr(size());

// 判断双向链表的当前节点是否达到开头,是重写迭代器的方法

public boolean hasNext() {

return itr.hasPrevious();

}

// 反向迭代器获取下一个元素,就是重写迭代器的方法,并反向获取

public E next() {

return itr.previous();

}

// 删除节点

public void remove() {

itr.remove();

}

}

linkedList的序列化与反序列化:

先写入容量,再写具体值;

先读出容量,再读出每个具体值

// 将LinkedList的容量,元素值都写入到输出流中

private void writeObject(java.io.ObjectOutputStream s)

throws java.io.IOException {

s.defaultWriteObject();

// 写入容量

s.writeInt(size);

// 将链表中所有节点的值都写入到输出流中 for (Entry e = header.next; e != header; e = e.next)

s.writeObject(e.element);

}

private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {

s.defaultReadObject();

// 从输入流中获取容量

int size = s.readInt();

// 新建表头节点

header = new Entry(null, null, null);

header.next = header.previous = header;

// 从输入流中将“所有值”并逐个添加到链表中

for (int i=0; i

}

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200111A0423O00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券