鏈表

• 由一系列節(jié)點(diǎn)組成的有序集合。
• 分為單向鏈表, 雙向鏈表，循環(huán)鏈表
• 單向鏈表: 每一個(gè)節(jié)點(diǎn)都有一個(gè)指針指向下一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的指針指向null
• 雙向鏈表: 每一個(gè)節(jié)點(diǎn)都有兩個(gè)指針(這里用p, n代表兩個(gè)指針)，p指向前一個(gè)節(jié)點(diǎn)，n指向下一個(gè)節(jié)點(diǎn)。但第一個(gè)節(jié)點(diǎn)的p指向null, 最后一個(gè)節(jié)點(diǎn)的n指向null
• 循環(huán)鏈表: 每一個(gè)節(jié)點(diǎn)都有兩個(gè)指針(這里用p, n代表兩個(gè)指針), 第一個(gè)節(jié)點(diǎn)的p指向最后一個(gè)節(jié)點(diǎn), 最后一個(gè)節(jié)點(diǎn)的n指向第一個(gè)節(jié)點(diǎn)。這樣就形成了循環(huán)

java的LinkedList - 雙向鏈表

這里以java的LinkedList的源碼學(xué)習(xí)，不多說(shuō)，先看源碼

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

上面代碼定義了一個(gè)類，代表一個(gè)節(jié)點(diǎn)的實(shí)體類，里面有3個(gè)成員變量，next用于指向下一個(gè)節(jié)點(diǎn)，prev用于指向前一個(gè)節(jié)點(diǎn)，item則是該節(jié)點(diǎn)承載的元素。

接下來(lái)，看一下它的一些添加元素的方法

public boolean add(E e) {
    linkLast(e);
    return true;
}

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

添加元素主要有4個(gè)方法，

• add和addLast其實(shí)是同一方法，都是在后面添加一個(gè)元素，所有都調(diào)用了linkLast(e)；
• addFirst則調(diào)用linkFirst(e)；
• add(index, element)這個(gè)方法是把元素添加某個(gè)位置，先調(diào)用checkPositionIndex(index)檢查index是否在[0，size]之間, 接著判斷想添加到index是否等于size,
  因?yàn)槲恢檬?開(kāi)始，如果index == size，直接調(diào)用linkLast()放到最后一個(gè)位置即可。否則調(diào)用linkBefore方法

繼續(xù)看linkLast，linkFirst，linkBefore這三個(gè)方法 ....

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

這個(gè)方法目的是把元素放到最前面，first和last是兩個(gè)Node<E>的成員變量，可以理解為用來(lái)記錄第一個(gè)和最后一個(gè)的來(lái)臨時(shí)變量。
先創(chuàng)建一個(gè)節(jié)點(diǎn)new Node<>(null, e, f)，要把元素放到最前面，此時(shí)newNode就是第一個(gè)節(jié)點(diǎn)，之前的第一個(gè)節(jié)點(diǎn)就成為newNode的下一個(gè)節(jié)點(diǎn)。
接著判斷 f == null, 這里的f是指沒(méi)添加之前的第一個(gè)節(jié)點(diǎn)，如果f為null, 那么當(dāng)前添加就是第一個(gè)節(jié)點(diǎn)，也是最后一個(gè)節(jié)點(diǎn)，所以newNode賦值為last;
如果f不為null, 那么f的p指針就應(yīng)該指向newNode。最后記錄節(jié)點(diǎn)的變量+1。

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

linkLast方法目的是把元素放到最后面，思路跟linkFirst差不多， 臨時(shí)變量l記錄最后一個(gè)節(jié)點(diǎn)，然后創(chuàng)建一個(gè)新的節(jié)點(diǎn)，該節(jié)點(diǎn)p指向l, n指向null，
如果l為null, 沒(méi)添加元素前為空集合，所以當(dāng)前也是第一個(gè)節(jié)點(diǎn)，賦值為first;如果l不為null, 那么 l 的n應(yīng)該指向新的節(jié)點(diǎn)。最后節(jié)點(diǎn)數(shù)+1.

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

linkBefore方法的目的是將元素e放到一個(gè)指定的節(jié)點(diǎn)之前。 succ是這個(gè)指定的節(jié)點(diǎn)。首先用臨時(shí)變量pred記錄succ的前一個(gè)節(jié)點(diǎn),
接著創(chuàng)建一個(gè)新的節(jié)點(diǎn)，p指向pred, n指向succ, succ的p指針就指向這個(gè)新的節(jié)點(diǎn)newNode。如果pred 為null, succ的前一個(gè)節(jié)點(diǎn)為null,
那么newNode就是第一個(gè)節(jié)點(diǎn);如果pred不為null, pred的n指針應(yīng)該指向newNode。最后節(jié)點(diǎn)數(shù)+1

添加分析完了，接下來(lái)看看移除

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}


public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}


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

removeFirst, removeLast 分別調(diào)用unlinkFirst(f), unlinkLast(l);

看remove方法，遍歷鏈表，從first開(kāi)始, 找到和o相等的元素，調(diào)用unlink方法完成移除。

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

f是第一個(gè)節(jié)點(diǎn)，f.item和f.next分別臨時(shí)賦值給element和next，接著f.item和f.next都設(shè)為null,就意味著移除了第一個(gè)節(jié)點(diǎn),
那么next這個(gè)節(jié)點(diǎn)就是第一節(jié)點(diǎn)了，賦值給first; 如果next為null, 那么last為null,說(shuō)明現(xiàn)在鏈表整個(gè)為空啦;如果next不為null,將next的p指針指向null。

private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

l是最后一個(gè)節(jié)點(diǎn)，l.item和l.prev分別臨時(shí)賦值給element和prev,接著l.item和l.prev都設(shè)為null,就意味著移除了最后一個(gè)節(jié)點(diǎn)了,
那么prev這個(gè)節(jié)點(diǎn)就是最后一個(gè)節(jié)點(diǎn)了,賦值給last; 如果prev為null, 那么first也為null,說(shuō)明現(xiàn)在鏈表整個(gè)為空啦;如果prev不為null,將prev的n指針指向null。

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.item， x.next, x.prev分別臨時(shí)賦值給element, next和prev; 重新調(diào)整next 和prev節(jié)點(diǎn),
如果prev為null, 那么next節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn);如果prev不為null, prev的n指向next, x的p設(shè)為null;
如果next為null, 那么prev節(jié)點(diǎn)就是最后一個(gè)節(jié)點(diǎn); 如果next不為null, next的p指向prev, x的next設(shè)為null；
最后把x.item設(shè)為null,移除當(dāng)前, size--代表節(jié)點(diǎn)數(shù)減1, modCount記錄的是鏈表的操作次數(shù)，所以怎么都是加1。

到此， 雙向鏈表的實(shí)現(xiàn)就基本完成啦。如果要實(shí)現(xiàn)循環(huán)鏈表，在雙向鏈表的基礎(chǔ)上，把第一個(gè)節(jié)點(diǎn)的p指向最后一個(gè), 把最后一個(gè)節(jié)點(diǎn)的n指向第一個(gè)節(jié)點(diǎn)。