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

}