数据结构之链表(Linked list)

说明： 如果仔细阅读完全文后，可能感觉有些不统一，这里先说明下原因。

链表尾引用不统一：在介绍单链表时，只有一个链表首部的引用(head) 指向第一个节点。你看到后面关于双链表及循环列表时，除了指向第一个节点的引用 还有指向最后一个节点（尾部）的引用。

这样做主要是， 链表设计可能包含尾部的引用，也可能不包含，在最后关于时间复杂度的对比也做了区分。个人也倾向添加尾部引用，但为了完整性 以及 更好的对比理解有无尾部引用的差异，所以在单链表 是没有尾部引用设计 来实现。 单链表 总结的比较详细，每个关键操作 都有代码及示意图。

命名不统一： 是单链表时 首部引用使用的head，而双链表直接使用的JDK源码中的代码介绍（没做任何改动） first和last。 那时单链表已经弄好了，代码及示意图改起来比较麻烦，而且个人更喜欢head的命名。

这些完全不会影响理解的。

链表概述

链表(Linked list)也是一种线性数据结构，通过每个节点中的指针(引用)依次连接 形成的顺序存储。

单链表(Singly linked list)

单链表中每个元素(链表中称为节点，node)包含两部分:数据部分 和 一个指向下一个节点的引用。最后一个节点指向为null。

链表的入口点称为head，它是第一个节点的引用。如果链表为空 则head指向为null。

示意图：

双链表(Doubly linked list)

双链表中每个节点包含3个部分：数据部分 和两个引用，一个指向下个节点(next) 另一个指向前一个节点(previous)。

示意图：

循环链表(Circular linked list)

最后一个节点引用 指向 第一个节点(或者head)。

单链表和双链表都可以形成循环链表，如下示意图(上面一个是 单循环链表 ，后面一个是 双循环链表 )：

链表操作

单链表操作

节点定义：定义节点中的数据项 和 下一个节点引用。

//E->anyType object
private static class Node<E> {
    //数据项
    private E data;
    //指向next节点的引用
    private Node<E> next;
 
    //构造
    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }
}

head定义：指向 第一个节点(即链表首部)的引用 ，初始化为null

private Node<E> head = null;

插入

• 插入链表首部

创建一个节点，节点的next指向head的引用，然后让head指向新建的节点即可。

若head为null，即当前链表为空，即向链表中插入新建的节点, 节点的next指向null。

public void addFirst(E item) {
    head = new Node<E>(item, head);
}

变化如下示意图

• 插入目标节点的前面

目标节点数据为key，在目标节点前插入新的节点(数据为toInsert)。

具体过程看下面代码及注释。

public void insertBefore(E key, E toInsert) {
   //若head为null，即链表为空，不存在目标节点 直接返回
   if(head == null) return;
   //若head指向的链表第一个节点 就是目标节点，即要把新建节点插入链表首部
   if(head.data.equals(key)) {
      addFirst(toInsert);
      return;
   }
 
   Node<E> prev = null;
   Node<E> curr = head;
   //curr定义了 指向当前节点，prev指向当前节点的上个节点。一直顺序查找，若找到目标节点(数据为key)，则curr指向目标节点，prev指向了目标节点的上个节点。
   while(curr != null && !curr.data.equals(key)) {
      prev = curr;
      curr = curr.next;
   }
   //若curr不为空，即找到目标节点，在curr和prev之间插入了新节点（数据为toInsert）。若curr为null，即没找到。
   if(curr != null) prev.next = new Node<E>(toInsert, curr);
}

示意图如下（链表不为空 且 目标节点不是第一个节点）：

• 插入某个节点后面

相比上面(插入某节点的前面)比较容易，只需一个指向当前节点的临时变量即可。查找到目标节点后，即在之后插入新节点即可。

public void insertAfter(E key, E toInsert) {
   Node<E> curr = head;
   //查找目标节点，找到即curr指向目标节点
   while(curr != null && !curr.data.equals(key)) {
       curr = curr.next;
   }
 
   //curr不为null，即找到目标节点。在之后插入即可。
   if(curr != null)
       curr.next = new Node<E>(toInsert, curr.next);
}

示意图：

• 插入链表尾部

若head为null，则链表为空。插入链表首部即可。

若不为空，使用临时变量tmp从head依次往后遍历，当tmp的next为null时即链表尾部，插入到后面即可。

public void addLast(E item) {
   if(head == null) {
       addFirst(item);
   } else {
      Node<E> tmp = head;
      while(tmp.next != null) tmp = tmp.next;
      tmp.next = new Node<E>(item, null);
   }
}

删除

有点类似插入。

下面以删除某指定数据的节点为例。

public void remove(E key) {
   //head为null，即链表为空
   if(head == null) throw new RuntimeException("linkedlist is null, cannot delete");
 
   //链表第一个节点即目标节点，改变head指向下个节点就可以了。
   if(head.data.equals(key)) {
      head = head.next;
      return;
   }
 
 
   Node<E> prev = null;
   Node<E> curr  = head;
   //查找，若找到即curr指向目标节点，prev指向目标节点的上个节点
   while(curr != null && !curr.data.equals(key)) {
      prev = curr;
      curr = curr.next;
   }
   //curr为null，即没找到
   if(curr == null) throw new RuntimeException("cannot find your node, cannot delete");
   //curr不为null,删除目标节点（即改变prev的next 指向curr的next即可）
   prev.next = curr.next;
}

示意图：

注：上述插入或删除操作中，都有查找或遍历的过程。因此查找或遍历不单独列出。

双链表操作

在Java中实现的LinkedList类是一个双链表，因此直接使用了JDK源码说明（只在代码中添加了注释，没做任何修改）。

下面是节点及这两个引用的代码:类中定义了两个引用，分别指向链表的首部和尾部，

transient int size = 0;
 
 
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
*            (first.prev == null && first.item != null)
*/
transient Node<E> first;//指向首部(第一个节点)
 
 
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
*            (last.next == null && last.item != null)
*/
transient Node<E> last;//指向尾部(最后一个节点)
 
 
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;
    }
}

插入到链表首部

具体看下面的代码注释和示意图。

/**
* Links e as first element.
*/
private void linkFirst(E e) {
    //f指向first指向的节点。即f和first同时指向第一个节点。f在方法中标志 链表插入前的第一个节点
    final Node<E> f = first;
    //创建新的节点，节点的prev指向null,next指向f(即链表插入前第一个节点)
    final Node<E> newNode = new Node<>(null, e, f);
    //first指向新节点(链表首部已改变)
    first = newNode;
    if (f == null)
        //若f为null，即插入前链表是空的，插入到新节点既是开始节点也是结束节点，所以last也指向了它
        last = newNode;
    else
        //如果f不为空，则让f(插入前的第一个节点)的prev指向新节点就完成了。
        f.prev = newNode;
    size++;
    modCount++;
}

示意图：

这个是f指向不为空的情况示意图。

若f为null,则没有节点指向新建节点，同时新建节点的next指向的是null, 尾部引用last也会指向新建节点。

详细点就是：

第一步---红色：final Node<E> f = first；

第二步---橙色： final Node<E> newNode = new Node<>(null, e, f);

第三步---绿色：first = newNode;

第四步---深蓝： f.prev = newNode;

插入到某个元素前面

这里是目标节点已经找到了后的操作。查找目标节点可以参考单链表中的代码。

下面代码：用e新建节点，插入到succ节点之前。

/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //这里把succ称为目标节点。succ在这里是已经查找到并存在的，查找过程可参考单链表中相关代码。
    //用pred指向 目标节点succ的上个节点。
    final Node<E> pred = succ.prev;
    //新建节点，prev指向pred 即新建节点的prev指向目标节点的上个节点，next指向目标节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //目标节点的prev指向 新建节点
    succ.prev = newNode;
    if (pred == null)
        //若pred为null 是目标节点上个节点为null，即链表插入前只有一个节点，所以first会指向新建节点。
        first = newNode;
    else
        //若pred不为null,目标节点的上个节点的next指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

插入到链表尾部

因为有两个引用first、last分别指向链表首部和链表尾部。这样尾部操作就变得和首部操作一样容易，不需要找到链表尾部才能插入。看完上面这个应该很简单，不做解释了。

/**
* Links e as last element.
*/
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++;
}

删除

源码中，首先查找到数据与o相同的第一个节点，在通过unlink删除该节点，并返回状态。

查找那考虑了o是否为null，很严谨。o==null?get(i)==null:o.equals(get(i))。jdk文档很多地方说明都可以看到，如果null去执行equals，就会出现Null pointer access：的异常了，值得注意。

/**
* Removes the first occurrence of the specified element from this list,
* if it is present.  If this list does not contain the element, it is
* unchanged.  More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists).  Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
    //这里就是区分o是否为null，找到第一个指定element的节点，通过unlink删除。
    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;
}
 
 
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    if (prev == null) {
        //prev为null 即x是首部(第一个节点)，first指向next即可
        first = next;
    } else {
        //prev不为null，x与prev之间关联即断开。prev的next指向next了，x的prev为null
        prev.next = next;
        x.prev = null;
    }
 
    //同prev处理类似，断开x与next联系
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
 
 
    x.item = null;
    size--;
    modCount++;
    return element;
}

示意图是prev和next都不为null的情况：

橙色--->prev.next = next; x.prev = null;

红色---> next.prev = prev; x.next = null;

最后x.item E也被置为null,size--。x被删除。

循环链表

循环链表的最后一个节点有指向第一个节点的引用。

仅已单循环链表为例。

下面是几个操作示例，可以看下代码和注释，不做详细说明了。看过上面应该很容易理解。

private Node<E> head = null;
private Node<E> tail = null;
 
 
private class Node<E> {
    E value;
    Node<E> next;
    public Node(E value) {
        this.value = value;
    }
}
 
 
//往尾部(即tail节点之后)添加节点
public void addNode(E value) {
    Node<E> newNode = new Node<>(value);
    if (head == null) {
        //head为null，即链表为空，head指向新建节点。
        head = newNode;
    } else {
        tail.next = newNode;
    }
    //tail指向新节点，即新节点相当于链表的尾部
    tail = newNode;
    //tail.next即新节点next指向head，形成环
    tail.next = head;
}
 
 
//查找，链表中是否包含数据为searchValue的节点
public boolean containsNode(E searchValue) {
    Node<E> currentNode = head;
    if (head == null) {
        return false;
    } else {
        //以head开始依次向后查找，直到碰到的仍是head停止。找到返回
        do {
            if (currentNode.value == searchValue) {
                return true;
            }
            currentNode = currentNode.next;
        } while (currentNode != head);
        return false;
    }
}
 
 
//删除查找到的第一个数据为valueToDelete的节点
public void deleteNode(E valueToDelete) {
    Node<E> currentNode = head;
    if (head != null) {
        if (currentNode.value == valueToDelete) {
            //head节点且值为valueToDelete
            head = head.next;
            tail.next = head;
        } else {
            //以head开始依次向后查找，直到碰到的仍是head停止。找到删除
            do {
                Node<E> next = currentNode.next;
                if (next.value == valueToDelete) {
                    currentNode.next = next.next;
                    break;
                }
                currentNode = currentNode.next;
            } while (currentNode != head);
        }
    }
}

链表与数组比较

简单做了个表格

链表

数组

动态分配：需要时才分配内存

固定分配：大小固定，new时即分配所有内存

分散存储：内存中不连续存储

连续存储：内存中连续存储

总量限制：由于分散存储，受内存总量限制

使用限制：由于连续存储，若无合适连续控件即无法完成分配，且容易形成内存碎片

插入/删除方便：改变节点中指向next的或者prev的引用即可

插入/删除代价大：需创建新数组并移动元素

有内存浪费：节点中需额外存储next或prev的信息

无内存浪费：数组元素只存放数据

顺序访问：在某个节点沿某一方向只能逐一访问

随机访问：可以直接计算得到某一元素的地址

链表的一些操作复杂度

操作

链表

数组

访问(访问第N个元素)

O(n)

O(1)

插入到首部

O(1)

O(n)

插入到尾部

有尾部引用tail:O(1)

无尾部引用O(n)

O(n)

插入到中部

查找时间+O(1)~=O(n)

O(n)

查找

O(n)

O(n) 删除

类似插入，看删除位置或者链表的设计

O(n)