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是同一對象
這樣就形成了閉環(huán)，只要有header對象，無論從前向后還是從后向前都能追溯到元素
get()方法體現(xiàn)了這一特點(diǎn)
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 對刪除倒庵、增加的效率比較高
查詢的效率因?yàn)橐粩嗟难刂湵聿樵兯孕氏鄬Ρ容^慢
尾插法插入集合
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;
}
