LinkedList Source code 1.6

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

private transient int size = 0;

/**

* Constructs an empty list.

*/

public LinkedList() {

header.next = header.previous = header;

}

LinkedList 是一个双向链表

表头和表位都是header同一对象

header->e->e->e->header

两个header是同一对象

这样就形成了闭环，只要有header对象，无论从前向后还是从后向前都能追溯到元素

get()方法体现了这一特点

public E get(int index) {

return entry(index).element;

}

/**

* Returns the indexed entry.

*/

private Entry entry(int index) {

if (index < 0 || index >= size)

throw new IndexOutOfBoundsException("Index: "+index+

", Size: "+size);

Entry e = header;

if (index < (size >> 1)) {

for (int i = 0; i <= index; i++)

e = e.next;

} else {

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

e = e.previous;

}

return e;

}

遍历

public Object[] toArray() {

Object[] result = new Object[size];

int i = 0;

for (Entry e = header.next; e != header; e = e.next)

result[i++] = e.element;

return result;

}

linkedlist 对删除、增加的效率比较高

查询的效率因为要不断的沿着链表查询所以效率相对比较慢

尾插法插入集合

public boolean addAll(int index, Collection c) {

if (index < 0 || index > size)

throw new IndexOutOfBoundsException("Index: "+index+

", Size: "+size);

Object[] a = c.toArray();

int numNew = a.length;

if (numNew==0)

return false;

modCount++;

Entry successor = (index==size ? header : entry(index));

Entry predecessor = successor.previous;

for (int i=0; i

Entry e = new Entry((E)a[i], successor, predecessor);

predecessor.next = e;

predecessor = e;

}

successor.previous = predecessor;

size += numNew;

return true;

}