数据结构与算法：链表及其应用

基本介绍

相比数组，链表是一种稍微复杂一点的数据结构。数组和链表都属于线性表，一个是顺序存储结构，一个是链式存储结构，最主要的的差别是底层存储结构。

数组需要一块连续的内存空间来存储，对内存要求较高，如果申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即使内存剩余空间总和大于100MB，仍然申请失败。

链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果申请的是 100MB 大小的链表，只要剩余内存不小于于100MB根本不会有问题。如果剩余内存地址是连续的，也是可以的。

常见的链表结构有单链表、双链表、循环链表。本文主要介绍双链表，以及的它的使用和自定义手写双链表。

单链表

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的**“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针** next。

其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

与数组一样，链表也支持数据的查找、插入和删除操作。在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。

从图中我们可以看出，针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。

但是，有利就有弊。链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第 k 位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。所以，链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

双链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

单链表的插入、删除操作的时间复杂度已经是 O(1) 了，双向链表还能再怎么高效呢？别着急，刚刚的分析比较偏理论，很多数据结构和算法书籍中都会这么讲，但是这种说法实际上是不准确的，或者说是有先决条件的。再来带你分析一下链表的两个操作。

先来看删除操作

在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

• 删除结点中“值等于某个给定值”的结点；
• 删除给定指针指向的结点。

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。

尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。

但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！

同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。你可以参照我刚刚讲过的删除操作自己分析一下。

除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

• 第一次处理：将所有元素根据点数分别存放到9个链表中，然后将链表连接起来，此时的链表中元素的点数是有序的
• 第二次处理：将所有元素根据花色分别存放到3个链表中，然后将链表连接起来，此时的链表中元素的点数和花色均是有序的

代码如下：

/**
 * 麻将类
 */
public class Mahjong {
    public int suit;//筒(1)，万(2)，条(3)
    public int rank;//点数 一  二  三

    public Mahjong(int suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {
        return "("+this.suit+" "+this.rank+")";
    }
}

测试类

/**
 * 链表的应用
 * 链式基数排序
 * 麻将的排序
 */
public class Client {

    @Test
    public void test() {
        LinkedList<Mahjong> list = new LinkedList<Mahjong>();
        list.add(new Mahjong(3,1));
        list.add(new Mahjong(2,3));
        list.add(new Mahjong(3,7));
        list.add(new Mahjong(1,1));
        list.add(new Mahjong(3,9));
        list.add(new Mahjong(2,2));
        list.add(new Mahjong(3,2));
        list.add(new Mahjong(1,3));
        list.add(new Mahjong(3,8));
        System.out.println(list);
        //[(3 1), (2 3), (3 7), (1 1), (3 9), (2 2), (3 2), (1 3), (3 8)]
        radixSort(list);
        System.out.println(list);
        //[(1 1), (1 3), (2 2), (2 3), (3 1), (3 2), (3 7), (3 8), (3 9)]
    }

    public void radixSort(LinkedList<Mahjong> list) {
        //按点数进行分组
        LinkedList[] rankList = new LinkedList[9];
        int rankLength = rankList.length;
        for (int i = 0; i < rankLength; i++) {
            rankList[i] = new LinkedList();
        }
        //把数据一个个放到对应的链表中
        while(list.size() > 0) {
            //取一个
            Mahjong mahjong = list.remove();
            //存放到对应的点数的链表中,下标为点数减1
            rankList[mahjong.rank-1].add(mahjong);
            //循环结束，list就为空了
        }
        //把9组不同点数的链表合并串联在一起
        for (int i = 0; i < rankLength; i++) {
            list.addAll(rankList[i]);
        }
        //按花色(筒子，万子，条子)进行分组
        LinkedList[] suitList = new LinkedList[3];
        int suitLength = suitList.length;
        for (int i = 0; i < suitLength; i++) {
            suitList[i] = new LinkedList();
        }
        //把数据一个个放到对应的链表中
        while(list.size() > 0){
            //取出一个元素(麻将)
            Mahjong mahjong = list.remove();
            //存放到对应的花色的链表中
            suitList[mahjong.suit-1].add(mahjong);
        }
        //把3组不同花色的链表合并串联在一起
        for (int i = 0; i < suitLength; i++) {
            list.addAll(suitList[i]);
        }
    }
}

下面我们自己实现一个双向链表LinkedList，关于代码中添加和删除数据的逻辑，可对照下图一步一步进行对比分析：

双向链表添加数据

双向链表删除数据

/**
 * 手写双链表
 */
public class LinkedList<E> {
    /**
     * 结点
     */
    private static class Node<E>{
        E item;
        Node<E> prev;
        Node<E> next;

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

    public LinkedList() {

    }

    //头结点
    Node<E> first;
    //尾结点
    Node<E> last;
    //大小
    int size;

    /**
     * 插入数据
     */
    public void add(E e) {
        linkLast(e);
    }

    private void linkLast(E e) {
        Node<E> newNode = new Node<E>(last, e, null);
        //临时变量，保存中间值
        Node<E> l = last;
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
            //new Node<E>(last,e,null); 已经完成下面的操作
            //last.prev = l;
        }
        size++;
    }

    /**
     * 根据索引查找结点
     */
    public E get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        return node(index).item;
    }

    /**
     * 获取index位置上的结点
     * 双链表查询较数组较慢是，需要循环
     * 而双链表查询比单链表快
     * 因为判断要查询结点index在链表前半部分，
     * 就从前往后查，如果index在链表后半部分，
     * 那么就从后往前查。
     */
    private Node<E> node(int index) {
        
        //如果index在整个链表的前半部分
        if (index < (size >> 1)) {//size >> 1 ---> size / 2
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {//如果index在整个链表的后半部分
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * 插入数据在index位置
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == size) {//在尾部结点添加数据
            linkLast(e);
        } else {
            Node<E> target = node(index);//比如index=2
            //需要打断index=1和index=2两个结点的联系，新建两组结点的前驱和后继联系
            Node<E> pre = target.prev;//中间变量存放index=1的结点
            Node<E> newNode = new Node<E>(pre,e,target);//对应红色箭头步骤1、2
            if (pre == null) {//向index=0的位置添加数据(结点)
                first = newNode;
            } else {
                pre.next = newNode;//对应红色箭头步骤3
                target.prev = newNode;//对应红色箭头步骤4
            }
            size++;
        }
    }

    /**
     * 删除数据
     */
    public void remove(int index) {
        Node<E> target = node(index);
        unLinkNode(target);
    }

    private void unLinkNode(Node<E> p) {//比如index=2
        //拿到要删除结点的前驱和后继
        Node<E> pre = p.prev;
        Node<E> next = p.next;
        if (pre == null) {
            first = p.next;//表示删除头结点
        } else if (next == null) {
            last = p.prev;//表示删除尾结点
        } else {
            pre.next = p.next;//表示目标结点的前驱的后继指向目标结点的后继
            next.prev = p.prev;//表示目标结点的后继的前驱指向目标结点的前驱
        }
        size--;
    }

}

测试类：

/**
 * 自定义(手写)双链表的测试类
 */
public class Client {
    @Test
    public void test() {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(4);
        linkedList.add(1);
        linkedList.add(3);
        print(linkedList);//0:4 1:1 2:3
        linkedList.add(1,2);
        print(linkedList);//0:4 1:2 2:1 3:3
        linkedList.add(0,66);
        linkedList.add(0,88);
//        linkedList.remove(3);
        print(linkedList);
    }

    private void print(LinkedList<Integer> linkedList) {
        int size = linkedList.size;
        for (int i = 0; i < size; i++) {
            System.out.print(i+":"+linkedList.get(i)+"  ");
        }
        System.out.println("");
    }
}

常见的关于链表的算法题

反转单链表

逻辑原理如下图：

核心代码

/**
 * 反转单链表
 */
public void reverseList() {
	Node<E> current = head.next;
	//切断head.next指向的current(当前链表的头结点变为新链表的尾结点)
	//所以next为空
	head.next=null;
	while (current != null) {
		//记录current结点的下一结点
		Node<E> currentNext = current.next;
		//current指向head，断开了指向currentNext
		current.next = head;
		//指针后移一位
		head = current;
		current = currentNext;
	}
}

交换链表相邻的元素

/**
 * 交换链表相邻的元素(结点)
 */
 public void swapPairs() {
    Node pre =  new Node(0);
    pre.next = head;//prev -> head
    if (head==null||head.next==null) return;//表示空链表或只有一个结点，无需交换
    while (pre.next != null && pre.next.next != null) {//原始链表至少要有两个结点
	     // node1 是当前要反转的第一个结点  pre -> node1 -> node2 -> node3
	     Node node1 = pre.next;//1
	     System.out.println("node1= "+node1.data);
	     // node2 是当前要反转的第二个结点
	     Node node2 = pre.next.next;
	     // 第二个结点放到第一个位置  pre -> node2
	     if (pre.next == head) {
	         //如果不添加判断，pre->node2->node1->node3
	         //但是pre.next=node2 即不再指向head,相当于把头结点删了
	         head = node2;
	         pre.next = node2;
	     } else {
	         pre.next = node2;
	     }
	     // 第三个结点放在第二个结点后面 node1 -> node3
	     node1.next = node2.next;
	     // 接第一第二个  pre -> node2 -> node1 -> node3
	     node2.next = node1;
	     //pre向后移两个结点
	     pre = pre.next.next;
   }
}