数据结构中的链表（Java实现）

采用链式存储的线性表称为链表，链表可以分为单链表、双向链表、循环链表。本文带领大家学习单链表，重点掌握单链表的基本操作（增删查改）。

单链表的存储结构

所谓线性表的链式存储，是指采用一组任意的存储单元存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。

为了表示这些元素之间的逻辑关系，除了需要存储元素本身的信息外，还需要存储指示其后继元素的地址信息。这两部分组成的存储结构称为结点。

结点包括两个域：数据域和指针域。其中，数据域存放数据元素的信息，指针域存放元素的直接后继元素存储地址，如下图所示。


通过指针域把 n 个结点根据线性表中元素的逻辑顺序链接在一起，就构成了链表。由于链表中的每个结点的指针域只有一个，因此这样的链表称为线性链表或者单链表。

例如，一个采用链式存储结构的线性表（Yang,Zheng,Feng,Xu,Wu,Wang,Geng）的存储结构如下图所示。


存取链表中的元素时，必须从头指针 head 出发，头指针 head 指向链表的第一个结点，从头指针 head 可以找到链表中的每一个元素。

由于单链表的每个结点的地址存放在其直接前驱结点的指针域中，而第一个结点没有直接前驱结点，因此需要一个头指针指向第一个结点。同时，由于表中的最后一个元素没有直接后继元素，因此需要将单链表的最后一个结点的指针域置为“空”（null）。

一般情况下，我们只关心链表的逻辑顺序，而不关心链表的实际存储位置。通常用箭头代替指针来连接结点序列。因此，如图 2 所示的线性表可以形象化为如下图所示的序列。


其中，“∧”表示指针域为空，不指向任何结点。有时为了操作上的方便，在单链表的第一个结点之前增加一个结点，称为头结点。头结点的数据域可以存放线性表的附加信息，如线性表的长度；头结点的指针域可以存放第一个结点的地址信息，即指向第一个结点。头指针指向头结点，不再指向链表的第一个结点。

带头结点的单链表如下图所示。


若带头结点的链表为空链表，则头结点的指针域为“空”，如下图所示。


单链表的存储结构用 Java 语言描述如下：

class ListNode { //定义结点
    int data;
    ListNode next;
    ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
    }
    ListNode(int data) {
        this.data = data;
    }
}

其中，ListNode 为链表的结点类型。

链表的基本操作可通过 LinkList 类成员函数实现，初始时，链表为空，可通过其构造函数初始化。

public class LinkList {
    public ListNode head;
}

单链表上的基本运算

单链表上的基本运算包括链表的建立、单链表的插入、单链表的删除、单链表的长度等。

1) 单链表的初始化操作

LinkList() {
    head = new ListNode();
}

2) 判断单链表是否为空

public boolean ListEmpty() {
    if (head == null)
        return true;
    else
        return false;
}

3) 按序号查找操作

链表是一种顺序存取结构，只能从头指针开始存取元素。因此，要查找单链表中的第 i 个元素，需要从单链表的头指针 head 出发，利用结点的 next 域依次访问链表的结点，并进行比较操作。利用计数器从 0 开始计数，直到计数器为 i，就找到了第 i 个结点。

public ListNode GetNode(int i) {
    ListNode cur = head; //标记当前结点
    int j = 1;
    while (cur != null && j < i) {
        cur = cur.next;
        j++;
    }
    if (j == i)
        return cur;
    else
        return null;
}

4) 定位操作

定位操作是指按内容查找并返回结点引用的操作。从单链表的头指针出发，依次访问每个结点，并将结点的值与 e 比较，若相等，则返回该结点的引用，表示成功；若没有与 e 值相等的元素，则返回 null，表示失败。

public ListNode LocateElem(int e) {
    //按内容查找单链表中元素值为e的元素，若查找成功，则返回对应元素的结点引用，否则返回null，表示失败
    ListNode p = head.next; //p指向第一个结点
    while (p != null) {
        if (p.data != e) { //没有找到与e相等的元素
            p = p.next; //继续找下一个元素
        } else { //找到与e相等的元素
            break; //退出循环
        }
    }
    return p; //返回元素值为e的结点引用
}

5) 插入操作

插入操作就是将元素 e 插入链表中指定的位置 i，若插入成功，则返回 true，否则返回 false。

boolean InsertList(int i, int e) {
    int j = 1;
    ListNode pre;
    if (i < 1)
        return false;
    if (i == 1) {
        ListNode newNode = new ListNode(e);
        head = newNode;
        return true;
    } else {
        pre = head;
        while (pre.next != null && j < i - 1) {
            pre = pre.next;
            j++;
        }
        if (j != i - 1) {
            System.out.println("插入位置错误！");
            return false;
        }
        ListNode newNode = new ListNode(e);
        newNode.next = pre.next;
        pre.next = newNode;
        return true;
    }
}

在单链表的第 i 个位置插入一个新元素 e 可分为 3 个步骤：

① 在链表中找到其直接前驱结点，即第 i-1 个结点，并由 pre 指向该结点，如下图所示。


② 动态申请一个新的结点，并由 p 指向该结点，将值 e 赋给 p 指向结点的数据域，如下图所示。


③ 修改 pre 和 p 指向结点的指针域，如下图所示。这样就完成了在第 i 个位置插入结点的操作。


在单链表中插入新结点分为两个步骤：

• 将新结点的指针域指向第 i 个结点，即 p.next=pre.next。
• 直接将前驱结点的指针域指向新结点，即 pre.next=p。

注意：插入结点的操作步骤不能反过来，即先执行 pre.next=p 操作，后执行 p.next=pre.next 操作，这是错误的。

6) 删除操作

删除操作就是将单链表中的第 i 个结点删除，其他结点仍然构成一个单链表。若删除成功，则返回删除的元素值，否则抛出异常。

public int DeleteList(int i) throws Exception //删除单链表中的第i个位置的结点。若删除成功，则返回删除的元素值，否则抛出异常
{
    ListNode pre, p;
    int j, e;
    pre = head;
    j = 0;
    while (pre.next != null && j < i - 1) //在寻找的过程中确保被删除结点存在
    {
        pre = pre.next;
        j++;
    }
    if (pre.next == null || j != i - 1) //若没找到要删除的结点的位置，则说明删除位置错误
    {
        throw new Exception("删除位置错误");
    }
    p = pre.next;
    pre.next = p.next; //将前驱结点的指针域指向要删除结点的下一个结点，将pre指向的结点与单链表断开
    e = p.data;
    return e;
}

删除单链表中的第 i 个结点分为以下 3 个步骤：

① 找到第 i 个结点的直接前驱结点，即第 i-1 个结点，并将 pre 指向该结点，p 指向第 i 个结点，如下图所示。


② 修改 pre 和 p 指向结点的指针域，使 p 指向的结点与原链表断开，即 pre.next=p.next。

③ 动态释放 p 指向的结点，如下图所示。

注意：在寻找第 i-1 个结点（被删除结点的前驱结点）时，要保证被删除结点存在。如果要删除的结点在链表中不存在，就会在执行循环后出现 p 指向空指针域，执行 pre.next=p.next 就会造成错误。

7) 求线性表的表长

public int ListLength() {
    int length = 0;
    ListNode cur = head;
    while (cur != null) {
        cur = cur.next;
        length++;
    }
    return length;
}

8) 输出链表

public void DispLinkList()
{
    int i;
    ListNode cur = head;
    while (cur != null) {
        System.out.print(" " + cur.data);
        cur = cur.next;
    }
}