数据结构与算法——链表

1. 概述

前面说到了数组，利用连续的内存空间来存储相同类型的数据，其最大的特点是支持下标随机访问，但是删除和插入的效率很低。今天来看另一种很基础的数据结构——链表。链表不需要使用连续的内存空间，它使用指针将不连续的内存块连接起来，形成一种链式结构。

2. 单链表

首先来看看单链表，存储数据的内存块叫做节点，每个节点保存了一个 next 指针，指向下一个节点的内存地址，结合下图你就很容易看明白了：

其中有两个节点指针比较的特殊，首先是链表头节点的指针，它指向了链表的第一个节点的地址，利用它我们可以遍历得到整个链表。其次是尾结点的指针，它指向了 null ，表示链表结束。

不难看出，单链表的最大特点便是使用指针来连接不连续的节点，这样我们不用担心扩容的问题了，并且，链表的插入和删除操作也非常的高效，只需要改变指针的指向即可。

结合上图不难理解，单链表能够在 O(1) 复杂度内删除和添加元素，这就比数组高效很多。但是，如果我们要查找链表数据怎么办呢？链表的内存不是连续的，不能像数组那样根据下标访问，所以只能通过遍历链表来查找，时间复杂度为 O(n)。下面是单链表的代码示例：

public class SingleLinkedList {
    private Node head = null;//链表的头节点

    //根据值查找节点
    public Node findByValue(int value) {
        Node p = head;
        while (p != null && p.getData() != value)
            p = p.next;
        return p;
    }

    //根据下标查找节点
    public Node findByIndex(int index) {
        Node p = head;
        int flag = 0;
        while (p != null){
            if (flag == index)
                return p;
            flag ++;
            p = p.next;
        }
        return null;
    }

    //插入节点到链表头部
    public void insertToHead(Node node){
        if (head == null) head = node;
        else {
            node.next = head;
            head = node;
        }
    }
    public void insertToHead(int value){
        this.insertToHead(new Node(value));
    }

    //插入节点到链表末尾
    public void insert(Node node){
        if (head == null){
            head = node;
            return;
        }

        Node p = head;
        while (p.next != null) p = p.next;
        p.next = node;
    }
    public void insert(int value){
        this.insert(new Node(value));
    }

    //在某个节点之后插入节点
    public void insertAfter(Node p, Node newNode){
        if (p == null) return;
        newNode.next = p.next;
        p.next = newNode;
    }
    public void insertAfter(Node p, int value){
        this.insertAfter(p, new Node(value));
    }

    //在某个节点之前插入节点
    public void insertBefore(Node p, Node newNode){
        if (p == null) return;
        if (p == head){
            insertToHead(newNode);
            return;
        }
        //寻找节点p前面的节点
        Node pBefore = head;
        while (pBefore != null && pBefore.next != p){
            pBefore = pBefore.next;
        }

        if (pBefore == null) return;
        newNode.next = pBefore.next;
        pBefore.next = newNode;
    }
    public void insertBefore(Node p, int value){
        insertBefore(p, new Node(value));
    }

    //删除节点
    public void deleteByNode(Node p){
        if (p == null || head == null) return;
        if (p == head){
            head = head.next;
            return;
        }
        Node pBefore = head;
        while (pBefore != null && pBefore.next != p){
            pBefore = pBefore.next;
        }

        if (pBefore == null) return;
        pBefore.next = pBefore.next.next;
    }

    //根据值删除节点
    public void deleteByValue(int value){
        Node node = this.findByValue(value);
        if (node == null) return;
        this.deleteByNode(node);
    }

    //打印链表的所有节点值
    public void print(){
        Node p = head;
        while (p != null){
            System.out.print(p.getData() + "  ");
            p = p.next;
        }
        System.out.println();
    }
        //定义链表节点
    public static class Node{
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }

        public int getData() {
            return data;
        }
    }
}

3. 循环链表

循环链表和单链表的唯一区别便是链表的尾结点指针并不是指向 null，而是指向了头节点，这样便形成了一个环形的链表结构：

4. 双向链表

双向链表，顾名思义，就是链表不只是存储了指向下一个节点的 next 指针，还存储了一个指向前一个节点的 prev 指针，如下图：

为什么要使用这种具有两个指针的链表呢？主要是为了解决链表删除和插入操作的效率问题。

在单链表中，要删除一个节点，必须找到其前面的节点，这样就要遍历链表，时间开销较高。但是在双向链表中，由于每个节点都保存了指向前一个节点的指针，这样我们能够在 O(1) 的时间复杂度内删除节点。

插入操作也类似，比如要在节点 p 之前插入一个节点，那么也必须遍历单链表找到 p 节点前面的那个节点。但是双向链表可以直接利用前驱指针 prev 找到前一个节点，非常的高效。

这也是双向链表在实际开发中用的更多的原因，虽然每个节点存储了两个指针，空间开销更大，这就是一种典型的用空间换时间的思想。

下面是双向链表的代码示例：

public class DoubleLinkedList {
    private Node head = null;//链表的头节点

    //在某个节点之前插入节点，这里方能体现出双向链表的优势
    public void insertBefore(Node p, Node newNode) {
        if (p == null) return;
        if(p == head) {
            this.insertToHead(newNode);
            return;
        }
        
        newNode.prev = p.prev;
        p.prev.next = newNode;
        
        newNode.next = p;
        p.prev = newNode;
    }
    public void insertBefore(Node p, int value) {
        this.insertBefore(p, new Node(value));
    }
    
    //删除某个节点
    public void deleteByNode(Node node) {
        if(node == null || head == null) return;
        if (node == head) {
            head = head.next;
            if(head != null) head.prev = null;
            return;
        }
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        if(next != null) next.prev = prev;
    }
    
    //根据值删除节点
    public void deleteByValue(int value) {
        Node node = this.findByValue(value);
        if (node == null) return;
        this.deleteByNode(node);
    }
   
    //定义链表节点
    public static class Node{
        private int data;
        private Node prev;//链表的前驱指针
        private Node next;//链表的后继指针
        
        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }

        public int getData() {
            return data;
        }
    }
}