LinkedList
-
介紹
LinkedList是基于雙向鏈表實(shí)現(xiàn)的；
隨機(jī)訪問(wèn)頭部與尾部速度快剖张；
隨機(jī)中間值速度較慢，因?yàn)樾枰苿?dòng)指針顾犹；
頭部與尾部插入與刪除速度快锄奢；
中間插入就略慢一下剧腻，因?yàn)樾枰苿?dòng)指針灰伟；
其實(shí)現(xiàn)了Deque接口；可當(dāng)一個(gè)Deque使用
重要屬性
//List的大小
transient int size = 0;
//頭部節(jié)點(diǎn)
transient Node<E> first;
//尾部節(jié)點(diǎn)
transient Node<E> last;
- add方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//獲取尾部節(jié)點(diǎn)
final Node<E> l = last;
//創(chuàng)建新節(jié)點(diǎn)闭翩，使其上一個(gè)節(jié)點(diǎn)指向尾部節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);
//更新尾部節(jié)點(diǎn)
last = newNode;
if (l == null)
//如果l是空的先蒋，說(shuō)明add之前無(wú)元素寇蚊，將頭部節(jié)點(diǎn)指向新節(jié)點(diǎn)
first = newNode;
else
//將原尾部節(jié)點(diǎn)指向新的節(jié)點(diǎn)
l.next = newNode;
size++;
modCount++;
}
尾部添加一個(gè)節(jié)點(diǎn)步驟：
newNode.prev=last => last.next=newNode => last=newNode
與ArrayList相比笔时，ArrayList可能會(huì)觸發(fā)擴(kuò)容操作(影響速度)，LinkedList則是直接追加道最后一個(gè)節(jié)點(diǎn)
- addLast方法
//與add方法邏輯一致
public void addLast(E e) {
linkLast(e);
}
- addFirst方法
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
//獲取頭節(jié)點(diǎn)
final Node<E> f = first;
//創(chuàng)建新節(jié)點(diǎn)仗岸，使其下一個(gè)節(jié)點(diǎn)指向頭節(jié)點(diǎn)
final Node<E> newNode = new Node<>(null, e, f);
//更新頭節(jié)點(diǎn)
first = newNode;
if (f == null)
//將尾部節(jié)點(diǎn)指向新節(jié)點(diǎn)
last = newNode;
else
//將原頭部節(jié)點(diǎn)指向新的節(jié)點(diǎn)
f.prev = newNode;
size++;
modCount++;
}
頭部添加一個(gè)節(jié)點(diǎn)步驟：
newNode.next=first => first.prev=newNode => first=newNode
與ArrayList相比允耿，ArrayList向頭部添加一個(gè)元素需要后面元素copy移位，還可能觸發(fā)擴(kuò)容扒怖；效率上LinkedList指定搞一些
- add方法(添加到指定位置)
public void add(int index, E element) {
//檢查index是否有越界
checkPositionIndex(index);
//index與size相等较锡，則是往尾部添加
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//往指定節(jié)點(diǎn)succ前插入一節(jié)點(diǎn)
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
指定節(jié)點(diǎn)前插入一個(gè)新節(jié)點(diǎn)步驟：
newNode.pred=succ.prev => newNode.next=succ => succ.prev.next=newNode
與ArrayList相比，ArrayList需要移位index后元素盗痒，LinkedList需要遍歷尋找節(jié)點(diǎn)
- addAll方法
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
如果是往尾部添加的話蚂蕴，直接for循環(huán)往后鏈就得了；
如果不是的話，先遍歷找到index對(duì)應(yīng)的節(jié)點(diǎn)骡楼，然后再往下鏈熔号，鏈完后，與尾部接上即可了鸟整；
與ArrayList相比跨嘉，ArrayList尾部添加的話，copy一次數(shù)組吃嘿；ArrayList中間插入的話需copy兩次數(shù)組祠乃；
- get方法
public E get(int index) {
//檢查index是否有越界
checkElementIndex(index);
return node(index).item;
}
//根據(jù)index獲取節(jié)點(diǎn)，通過(guò)遍歷子節(jié)點(diǎn)方式
Node<E> node(int index) {
//判斷如果index小于size的一半兑燥，則從頭部開(kāi)始遍歷子節(jié)點(diǎn)亮瓷；否則從尾部遍歷子節(jié)點(diǎn)
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
與ArrayList相比，LinkedList.get效率略低降瞳，需要遍歷子節(jié)點(diǎn)查詢嘱支。
- set方法
//根據(jù)index獲取子節(jié)點(diǎn)，然后替換其值
public E set(int index, E element) {
//檢查index是否有越界
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
與ArrayList相比挣饥，LinkedList.set效率略低除师，需要遍歷子節(jié)點(diǎn)查詢。
- remove方法(根據(jù)元素移除)
//遍歷找到節(jié)點(diǎn)扔枫，然后移除
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//移除一個(gè)節(jié)點(diǎn)
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
移除一個(gè)節(jié)點(diǎn)的步驟：
x.prev.next=x.next => x.next.prev=x.prev => x...=null
與ArrayList相比汛聚，ArrayList遍歷后得到index，然后移除(需要index后元素移位)短荐，LinkedList遍歷得到節(jié)點(diǎn)倚舀，直接移除。
- remove方法(根據(jù)index移除)
//遍歷獲取節(jié)點(diǎn)忍宋，然后移除
public E remove(int index) {
//檢查index是否有越界
checkElementIndex(index);
return unlink(node(index));
}
與ArrayList相比痕貌，ArrayList移除元素后index后元素移位，LinkedList是遍歷取得節(jié)點(diǎn)直接移除
- clear方法
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
與ArrayList.clear 差不多糠排，都是遍歷置空數(shù)據(jù)
