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元无门槛券
私享最新 技术干货
腾讯云开发者
