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;
}
