鏈表是很常見的一種數(shù)據(jù)結(jié)構(gòu)腌歉。通常有兩種實現(xiàn)方式：一種是使用數(shù)組，一種使用指針避除。數(shù)組涉及數(shù)據(jù)移動和擴(kuò)容問題怎披，但隨機(jī)查找方便；指針插入刪除方便瓶摆，但隨機(jī)查找不方便
下面學(xué)習(xí)java的LinkedList（雙向鏈表）凉逛，由于java沒有指針，所以使用對象來實現(xiàn)群井。以下精簡版：
常見方法：add状飞、get、remove、size昔瞧、isEmpty等指蚁，簡單起見就不抽取父類了
public class MyLinkedList<T> {
/** 節(jié)點 */
@SuppressWarnings("hiding")
private class LinkedNode<T> {
private T value;
private LinkedNode<T> prev;
private LinkedNode<T> next;
public LinkedNode(T value, LinkedNode<T> prev, LinkedNode<T> next) {
this.value = value;
this.prev = prev; // 前向
this.next = next; // 后向
}
}
/** 元素數(shù) */
private transient int size;
/** 頭部 */
private transient LinkedNode<T> first;
/** 尾部 */
private transient LinkedNode<T> last;
public boolean addFirst(T element) {
linkFirst(element);
return true;
}
// 頭部添加數(shù)據(jù)
private void linkFirst(T element) {
LinkedNode<T> temp = first;
LinkedNode<T> newNode = new LinkedNode<>(element, null, null);
first = newNode; // 第一個節(jié)點改為新結(jié)點
if (last == null) {
last = newNode;
} else {
// 將原來的首節(jié)點的前向設(shè)為新節(jié)點
temp.prev = first;
}
size++;
}
// 尾部添加數(shù)據(jù)
public boolean addLast(T element) {
linkLast(element);
return true;
}
private void linkLast(T element) {
LinkedNode<T> temp = last;
LinkedNode<T> newNode = new LinkedNode<>(element, null, null);
last = newNode; // 最后一個節(jié)點改為新結(jié)點
if (first == null) {
first = newNode;
} else {
// 將原來的尾節(jié)點的后向設(shè)為新節(jié)點
temp.next = last;
}
size++;
}
// 頭部刪除數(shù)據(jù)
public T removeFirst() {
final LinkedNode<T> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private T unlinkFirst(LinkedNode<T> f) {
final T element = f.value; // 用于返回數(shù)據(jù)
final LinkedNode<T> next = f.next;
f.value = null;
f.next = null;
first = next;
if (next == null)
last = null; // 已經(jīng)沒有元素
else
// 第一個元素前向應(yīng)為null
next.prev = null;
size--;
return element;
}
// 尾部刪除數(shù)據(jù)
public T removeLast() {
final LinkedNode<T> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private T unlinkLast(LinkedNode<T> l) {
final T element = l.value; // 用于返回數(shù)據(jù)
final LinkedNode<T> prev = l.prev;
l.value = null;
l.prev = null;
last = prev;
if (prev == null)
first = null; // 已經(jīng)沒有元素
else
// 最后一個元素后向應(yīng)為null
prev.next = null;
size--;
return element;
}
public T getLast() {
if (last != null) {
return last.value;
}
return null;
}
public T getFirst() {
if (first != null) {
return first.value;
}
return null;
}
}
刪除數(shù)據(jù)方法未添加，這里簡單說一下就行：
- 刪除指定數(shù)據(jù)自晰，JDK實現(xiàn)：如果數(shù)據(jù)是null走一個循環(huán)專門檢測空值凝化；不是null，專門一個循環(huán)酬荞，用equal判斷是否是要找的數(shù)據(jù)
- 刪除指定位置的數(shù)據(jù)搓劫，檢測 position < （size >> 1）成立使用first遍歷 position次找到數(shù)據(jù)；否則使用last前向遍歷position次
