数据结构之LinkList链表

链表与数组在数据结构的江湖上被并称为南数组、北链表，其江湖地位可见一斑

概念

链表作为最基础的通用存储结构，它的作用和数组是一样的，但存储数据的方式略有不同。数组需要预先获取一定的内存空间，且内存的地址是连续的，在存储数据的时候，插入和删除都需要遍历数组，还需要移动部分数据，是十分低效的。而链表能够解决以上问题，下面来看一下链表的结构。

链表的数据项存储在链表节点中，一个节点可以叫Node也可以叫Link，它包含数据项和一个引用，数据项存储数据本身，通常是一个包含各种数据的类的对象，而引用则是引用下一个节点，一般记为next，链表的核心实现就是这个next，它标记了每个节点之间的联系，像一根线一样把这些散落在内存各个角落的节点对象串了起来。下面通过代码来直观的理解一下：

/**
 * 链表的节点，用来存放数据
 */
public class Node {
    // 数据变量
    private String data;
    // next引用
    public Node next;
    // 构造函数
    public Node(String str) {
        data = str;
    }
    // getter
    public String getData() {
        return data;
    }
    // Node的打印方法
    public void displayNode() {
    System.out.print("{ Node: " + data + " }..");
    }
}

可以看到，链表节点的关键两个属性，一个是数据项（这里简单的表示为String类型的data），一个是指向下一个链表节点的next引用（这里为了访问简单设置为public），虽然还不知道下一个节点是谁，但在链表的数据数据结构中，将数据插入时，就会建立这个联系。

单向链表

以上说明了链表的重要概念，节点与引用，下面来展示如何构成一个链表，首先从最简单的单向链表开始，单向链表顾名思义，只有一端可以插入和访问的链表，链表类LinkList值仅维护第一个链表节点first的信息，其它的节点通过next引用，以下是实现代码：

/**
 * 单向链表：维护头节点的信息，对链表的操作都从头部开始
 */
public class LinkList {
    // 头节点的引用
    Node first;
    // 构造方法
    public LinkList() {
        first = null;
    }
    // 插入方法，头插法
    public void insertFirst(String str) {
        Node newNode = new Node(str);
        newNode.next = first;
        first = newNode;
    }
    // 删除方法，删除头部节点
    public Node deleteFirst() {
        Node temp = first;
        first = first.next;
        return temp;
    }
    // 打印链表方法
    public void display() {
        System.out.print("LinkList: ");
        Node current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }
    // 判断链表是否为空的方法
    public Boolean isEmpty() {
        return first == null;
    }
    // 在链表中查找的方法
    public Node find(String str) {
        Node current = first;
        while (current != null) {
            if (current.getData() != str)
                current = current.next;
            return current;
        }
        System.out.println("could not find Node :" + str);
        return null;
    }
    // 从链表中查找元素删除方法
    public Node delete(String str) {
        Node current = first;
        Node previous = first;
        while (current != null) {
            if (current.getData() != str) {
                previous = current;
                current = current.next;
            } else {
                previous.next = current.next;
                return current;
            }
        }
        System.out.println("cloud not find Node:" + str + ", failed to delete it");
        return null;
    }
}

代码中定义了唯一一个变量：头节点的引用first，还有一些链表的常用方法：插入、删除、查找、展示等，可以发现这些方法都是由头节点first展开的，在表达这些方法的时候需要注意边界和特殊情况first的分析。

双端链表

注意是双端列表，不是双向链表，在上面的单向链表中，链表类仅维护了一个头节点的引用first，那么如果要在链表尾部插入一个数据，需要遍历整个链表，这种效率很低。双端链表不仅维护了first头节点的引用，而且还维护了last尾节点的引用，这样访问尾节点就像访问头节点一样方便，这种特性使得双端链表比起单向链表在一些场合更有效率，比如说队列。

以下展示双端链表的实现代码，节点还是引用上面的Node类

public class DoubleSideLinkList {

    // 首节点和尾节点的引用
    Node first;
    Node last;

    // constructor
    public DoubleSideLinkList() {
        first = null;
        last = null;
    }

    // isEmpty
    public boolean isEmpty() {
        return first == null;
    }

    // insert first
    public void insertFirst(String str) {
        Node newNode = new Node(str);
        if (isEmpty()) {
            last = newNode;
        }
        newNode.next = first;
        first = newNode;
    }

    // insert last
    public void insertLast(String str) {
        Node newNode = new Node(str);
        if (isEmpty()) {
            first = newNode;
        }
        last.next = newNode;
        last = newNode;
    }

    // delete first
    public Node deleteFirst() {
        Node temp = first;
        // 仅有一个元素
        if (first.next == null)
            last = null;
        first = first.next;
        return temp;
    }

    // display
    public void displayList() {
        System.out.println("List (first-->last): ");
        Node current = first;
        while(current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }
}

可以看出，双端链表可以很方便的从尾节点插入数据，这里需要说明的是，这个链表依然是单向的，每个节点也仅有一个引用next指向下一个节点，所以遍历和查找的方法与单向链表没什么差别，在此就不做展示。在实现双端链表的insert与delete方法的时候需要注意特殊情况：列表为空或者列表将要为空时，first与last的处理。

有序链表

有序链表中，数据是按照关键值的有序排列的，有序链表的插入速度优于有序数组，而且可以扩展到所有有效的内存，所以在很多场合可以使用有序链表，在以下的实现中，我们还是引用上面的Node类，因为数据项data为String类型，我们以数据项的hashcode为序来实现有序链表：

public class SortedLinkList {

    // filed
    Node first;

    // constructor
    public SortedLinkList() {
        first = null;
    }

    public boolean isEmpty() {
        return (first==null);
    }

    public void insert(String key) {
        Node current = first;
        Node previous = null;
        Node newNode = new Node(key);

        while (current != null && current.getData().hashCode() < key.hashCode()) {
            previous = current;
            current = current.next;
        }
        if (previous == null) {
            first = newNode;
        } else {
            previous.next = newNode;
        }
        newNode.next = current;
    }

    public Node remove() {
        Node temp = first;
        first = first.next;
        return temp;
    }

    public void display() {
        System.out.print("LinkList: ");
        Node current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }
}

有序链表主要是insert方法比较难实现，也是需要考虑特殊情况，即链表为空。

双向链表

双向链表与双端链表不同，双端链表虽然可以从尾部插入节点，但是每个节点引用的还是其下一个节点，遍历也是单向的，而双向链表则可以从头部或者从尾部开始遍历，为了实现这一特性，我们需要修改一下节点类Node，为了区分，我们以Link为节点命名，在Link中，不仅实现对下一节点的引用next，而且还实现了对上一个节点的引用previous，如下：

public class Link {

    private int data;

    public Link next;

    public Link previous;

    public Link(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void displayLink() {
        System.out.print(data + " ");
    }
}

唯一不同的点就是指向上一个节点的引用previous，虽然仅在节点中加了一个引用，但是双向链表的实现却麻烦了很多，其中各种引用关系特别容易混乱，而且还有一些特殊情况需要考虑，下面一起来感受一下：

public class DoublyLinkList {

    // 头节点和尾节点的引用，也是双端的
    Link first;
    Link last;

    // constructor
    public DoublyLinkList() {
        first = null;
        last = null;
    }

    // isEmpty
    public boolean isEmpty() {
        return first == null;
    }

    // insert first
    public void insertFirst(int data) {
        Link newLink = new Link(data);

        if (isEmpty()) {
            last = newLink;
        } else {
            first.previous = newLink;
        }
        newLink.next = first;
        first = newLink;
    }

    // insert last
    public void insertLast(int data) {
        Link newLink = new Link(data);

        if (isEmpty()) {
            first = newLink;
        } else {
            last.next = newLink;
            newLink.previous = last;
        }
        last = newLink;
    }

    // insert after
    public boolean insertAfter(int key, int data) {
        Link newLink = new Link(data);
        Link current = first;
        // find
        while(current != null) {
            if (current.getData() != key) {
                current = current.next;
            } else {
                if (current == last) {
                    newLink.next = null;
                    last = newLink;
                } else {
                    newLink.next = current.next;
                    current.next.previous = newLink;
                }
                current.next = newLink;
                newLink.previous = current;
                return true;
            }
        }
        System.out.println("cloud not find the key: " + data);
        return false;
    }

    // delete first
    public Link deleteFirst() {
        Link temp = first;
        if (first.next == null) {
            last = null;
        } else {
            first.next.previous = null;
        }
        first = first.next;
        return temp;
    }

    // delete last
    public Link deleteLast() {
        Link temp = last;
        if (first.next == null) {
            first = null;
        } else {
            last.previous.next = null;
        }
        last = last.previous;
        return temp;
    }

    // delete key
    public Link deleteKey(int data) {
        Link current = first;
        while (current != null) {
            if (current.getData() != data) {
                current = current.next;
            } else {
                if (current == first) {
                    first = first.next;
                } else {
                    current.previous.next = current.next;
                }
                if (current == last) {
                    last = last.previous;
                } else {
                    current.next.previous = current.previous;
                }
                return current;
            }
        }
        System.out.println("cloud not find the key: " + data + ", delete failed!");
        return null;
    }

    // display forward
    public void displayForward() {
        System.out.println("List (first-->last): ");
        Link current = first;
        while (current != null) {
            current.displayLink();
            current = current.next;
        }
        System.out.println();
    }

    // display backward
    public void displayBackward() {
        System.out.println("List (last-->first): ");
        Link current = last;
        while (current != null) {
            current.displayLink();
            current = current.previous;
        }
        System.out.println();
    }
}

这是一个双向链表，同时也是双端列表，可以从前向后或者从后向前遍历，也可以在链表的任何地方插入或是删除节点，在实现这些方法时，需要修改与插入或删除节点有关系的前后四个引用，且还需要考虑first与last、列表为空或者仅有一个元素的特殊情况，可以通过画图来加深理解。

效率与总结

以上我们介绍并实现了单向链表、双端链表、有序链表和双向链表，接下来我们来讨论一下这些链表的效率。
链表与数组作为通用数据结构经常被拿来做对比，以链表和数组这两个通用数据结构为基础的一些抽象数据模型，比如java中的ArrayList与LinkedList，也经常被拿出来作比较，总的来说主要有两大区别：

1. 链表插入和删除的效率高于数组，链表插入、删除头节点、尾节点的时间效率为O(1)，而在链表中间插入、删某一节点的时间复杂度为O(N)，虽然与数组相同操作的时间复杂度相同，可是数组需要复制移动元素位置来填补空洞，所以链表的效率还是要优于数组的，特别是复制时间占比较重的情况中。
   数组则是随机访问元素的效率要高于链表，可以通过数组下标直接访问的到。

2. 链表比数组优越的另一个重要因素就是，链表可以扩展到所有可用的内存空间，且不用像数组一样初始化容量，也不需要可以扩容。另外当一个数组对象需要一个连续的大内存空间时，会有几率触发jvm的GC去整理内存空间以获取一片连续的内存，而链表则没有这方面的限制，所以在内存的使用效率上，链表优于数组。

正如以上所述，一般来说，链表如果采用头插法(或删除)，则时间复杂度均为O(1)，而如果是随机插入或者向有序链表中插入的时间效率均为O(N)，因为需要找到合适的位置；

有序链表可以在O(1)的时间返回或删除最小或最大值，如果一个应用需要频繁的返回最小值且不需要快速的插入时间，则可以选择有序链表来实现，如优先级队列；

双向链表由于两端都可以插入、删除和遍历，所以可以用来做双端队列。

参考文章

《Data Structures & Algorithms in Java》 Robert Lafore著