链表的概念

我们知道数组是很常用的数据储存方式,而链表就是继数组之后,第二种最通用的数据储存方式了。数组需要存放在连续的空间,计算机很容易实现。而链表的好处是不用确定空间长度,不够的时候,直接申请新的节点,帮助插入。所以链表可以更灵活地进行内存分配。

链表(linked list)是一种序列形的数据结构,其中包含了很多通过链接 (link) 被串起来的节点。每个节点有一个数据域,储存着节点的数值,还有一个指针域,指向下一个节点。

Linked List

简单来说,链表是由一系列节点组成的,每个节点通过链接和其他节点链接。每个节点包含两个属性,一个是数值,记录了节点的数据,另一个是指针,记录了下一个节点的位置。正因为节点的指针能够记录其他节点的位置,所以我们不需要将节点按顺序排列。

链表的类型

链表有很多不同的类型,但本质上都是一系列通过链接相连的节点。

单链表:链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。

Singly-linked-list.svg

双链表:双链表是为了解决链表节点不知道前面节点的尴尬,于是在节点的定义中,存在一个父节点,和一个子节点。这样就能顺着父节点往回找。

Doubly-linked-list.svg

循环链表:在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。

Circularly-linked-list.svg

块状链表:块状链表结合了数组和链表的特性,将连续成段的数组通过链接串起来。块状链表的特点是插入很灵活,寻找特定元素也比正常链表快速。

链表是一种重要的基础数据结构,可以用来生成其它类型的数据结构,比如之后讲到的堆、栈、树和图等等。单向链表也是链表中最基础的类型,其它变种也是基于它的,在接下来的一部分,我会着重讲解单向链表。

链表的基本操作

每种数据结构都有其对应的操作,而链表包含以下基本操作:

  1. 插入:将一个新元素插入链表的任意位置。
  2. 删除:将一个元素从链表中删除。
  3. 查找(遍历):查找一个特定的元素。
  4. 更新:更新一个节点上的元素。

单向链表的实现

以下是链表的定义:

public class LinkedList {
    static class ListNode(
        int val; 
        ListNode next;
        public ListNode(int val) {
            this.val = val;
    }
    ListNode head; 
    ListNode tail;
    int size;
    public LinkedList() { 
        head = null;
        tail = null;
        size = 0;
    }
}

其中ListNode是节点的定义,其中的属性val就是数据,而next就是下一个节点。而 LinkedList 则是单向链表类,其中包含头节点head和尾节点tail。在初始化的时候,我们将头尾节点都设为null,size初始化为0。

插入

在一个链表中插入新元素分为以下三种情况:

  • 插入到链表的最前头,作为新的头结点。
  • 插入到链表中间的位置。
  • 插入到链表的尾部,作为链表中最后的元素。

虽然新元素的插入位置不固定,但是链表插入的思想的固定的。插入只需要两步:将新节点的next指针指向插入位置后的节点,再将插入节点前的next指针指向新插入的节点。

比如,我们在链表 {1, 2, 3, 4} 的基础上分别实现在头部、中间、尾部插入新元素5,过程如下图所示:

链表中插入元素的 3 种情况示意图

要注意的是,我们必须先执行步骤1,再执行步骤2;如果先执行步骤2,否则会导致插入位置后续的节点无法被找到。以下是代码:

// insert the element to the specific position, position starts from index 0
public void insert(int position, int number) {
    if (position > size) {
        return;
    }
    ListNode newNode = new ListNode(number);
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        if(tail == null) {
            tail = newNode;
        }
        size++;
    } else if (position == size) {
        this.append(number);
    } else {
        ListNode prev = head;
        for (int i = 0; i < position - 1; i++) {
            prev = prev.next;
        }
        ListNode next = prev.next;
        newNode.next = next;
        prev.next = newNode;
        size++;
    }
}
// append the new element to the end of the list
public void append(int number) { 
    ListNode newNode = new ListNode(number);
    if(tail == null) {
        tail = newNode;
    } else {
        tail.next = newNode;
        tail = newNode;
    }
    size++;
}

删除

删除元素如下图所示,只要找到我们要删除的节点,然后将前面节点的next指针指向被删除节点的下一节点即可:

链表删除元素示意图
public void delete(int number) {
    if(head != null && head.val == number) { // delete the head node
        head = head.next;
        size--;
        if(size == 0) { // corner case: no element is left
            tail = head;
        }
    } else {
        ListNode prev = head;
        ListNode cur = head;
        while (prev != null && cur != null) {
            if (cur.val == number) {
                if(cur == tail) { // corner case: delete the last element
                    tail = prev;
                }
                prev.next = cur.next;
                size--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}

查找

查找元素比较简单,只要从头节点开始遍历,找到与目标值相对应的节点,返回其位置即可:

public int search(int number) {
    ListNode cur = head;
    for(int index = 0; cur != null; index++) {
        if(cur.val == number) {
            return index;
        }
        cur = cur.next;
    }
    return -1;
}

更新

更新链表和查找相似,只要找到对应的节点后,改变节点的值即可:

public int update(int oldValue, int newValue) {
    ListNode cur = head;
    for(int index = 0; cur != null; index++) {
        if(cur.val == oldValue) {
            cur.val = newValue;
            return index;
        }
        cur = cur.next;
    }
    return -1;
}

Java完整代码

LeetCode题目