简介

在计算机科学中,链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

链表的结构

链表中的每个结点都包含一个或多个保存数据的成员。例如,存储在结点中的数据可以是库存记录;或者它可以是由客户的姓名、地址和电话号码等组成的客户信息记录。

除了数据之外,每个结点还包含一个后继指针指向链表中的下一个结点。

img

非空链表的第一个结点称为链表的头。要访问链表中的结点,需要有一个指向链表头的指针。从链表头开始,可以按照存储在每个结点中的后继指针访问链表中的其余结点。最后一个结点中的后继指针被设置为 nullptr 以指示链表的结束。

因为指向链表头的指针用于定位链表的头部,所以也可以认为它代表了链表头。同样的指针也可以用来定位整个链表,从头开始,后面跟着后续指针,所以也可以把它看作整个链表。

img

链表在C++中的表示方法

为了表示链表,需要有一个表示链表中单个节点的数据类型。

第一个图就是一个普通的节点结构,我们需要创建一个像这样的结构体。

struct ListNode
{
    double value;
    ListNode *next;
};

在上述代码中,"ListNode"为该结构体的名称,结构体的成员“value”是节点的数据部分,这里可以换成另一个结构体用于存放别的数据,另一个结构成员则被声明为ListNode的指针,它将负责指向下一个结构体。

像ListNode 这样的结构,它包含一个指向相同类型数据结构的指针,因此可以说是一个包含对自身引用的类型。像这样的类型称为自引用数据类型或自引用数据结构。

在声明完“ListNode”表示节点后,就可以定义一个初始为空的链表了。

定义方法:

首先定义一个用作链表头的指针并将其初始化为nullptr(空指针)

LinkList *head = nullptr;

然后让我们试着创建链表中的第一个包含数据的节点,存储值为3.14,如下所示

    head = new ListNode;//分配新节点
    head->value = 3.14;//存储数据
    head->next = nullptr;//表示链表的结尾
    cout << head->value << endl;
//运行结果:
3.14

下面让我们继续创建一个新的节点

    ListNode *secondPtr = new ListNode;//一个新的节点
    secondPtr->value = 1.03;//存储数据
    secondPtr->next = nullptr;//第二个结点是链表的结尾
    head->next = secondPtr;//让第一个结点的next值指向第二个节点的地址
    cout << head->next->value << endl;//此时head->next等价于"secondPtr"
//运行结果:
3.14
1.03

下面是这个示例的完整代码

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
    double value;
    ListNode *next;
};

int main() {
    ListNode *head = nullptr;
    head = new ListNode;//分配新节点
    head->value = 3.14;//存储数据
    head->next = nullptr;//表示链表的结尾
    cout << head->value << endl;
    ListNode *secondPtr = new ListNode;//一个新的节点
    secondPtr->value = 1.03;//存储数据
    secondPtr->next = nullptr;//第二个结点是链表的结尾
    head->next = secondPtr;//让第一个结点的next值指向第二个节点的地址
    cout << head->next->value << endl;//此时head->next等价于"secondPtr"
}

在C++中利用构造函数初始化节点

C++ 结构体可以有构造函数。对于定义链表结点类型的结构来说,如果能给它提供一个或多个构造函数,那将会带来很大的方便,因为这样将使得结点在创建时即可初始化。前文还曾经提到过,构造函数可以像常规函数一样,使用默认形参来定义,而为结点的后继指针提供一个默认的 nullptr 形参是很常见的。

通过这个构造函数,我们可以使用更加简洁的代码来实现节点的创建

    ListNode *secondNode = new ListNode(12.43);
    ListNode *head= new ListNode(3.14,secondNode);
    cout<<head->value<<endl;
    cout<<head->next->value<<endl;
//输出结果
3.14
12.43

也可以放弃第二个指针,直接就用一个head

    ListNode *head = new ListNode(11.11);//新建一个链表节点,此时“head”指向它
    head = new ListNode(22.22, head);//又新建一个“next”指向“head”的节点,创建完成后,“head”将指向这个新的节点
    head = new ListNode(33.33, head);//如法炮制,再建一个
    cout << head->value << endl;
    cout << head->next->value << endl;
    cout << head->next->next->value << endl;
//输出结果
33.33
22.22
11.11

img

如图所示,通过这种方法新创建的链表将排在首位,所以输出结果和创建顺序是相反的。这种情况和栈的特性(FILO)差不多。(FILO指的是First In Last Out,同理FIFO指的是First In First Out)

如果想要实现像队列(FIFO)这样的特性的话,也可以用下面的方法来实现链表:

    LinkNode *head=new LinkNode(11.11, nullptr);//头节点
    LinkNode *end=head;//创建一个end指针,用于方便建立节点之间的连接
    end->next=new LinkNode(22.22, nullptr);//让end指针指向第二个节点
    end=end->next;//end切换到第二个节点
    end->next=new LinkNode(33.33, nullptr);//end指向第三个节点
    end=end->next;//end切换到第三个节点
//测试代码
    cout<<head->a<<endl;
    cout<<head->next->a<<endl;
    cout<<head->next->next->a<<endl;
//输出结果
11.11
22.22
33.33

遍历链表

从链表头开始,涉及整个链表,并在每个结点上执行一些处理操作的过程被称为遍历链表。

例如,如果需要打印某个链表中每个结点的内容,则必须遍历该链表。假设某个链表的链表头指针是 head,要遍历该链表,则需要使用另一个指针 ptr 指向链表的开头:

ListNode *ptr = head;然后就可以通过使用表达式 *ptr 或者使用结构指针操作符 -> 来处理由 ptr 指向的结点。例如,如果需要打印在结点上的值,则可以编写以下代码:

cout << ptr->value;一旦在该结点的处理完成,即可将指针移动到下一个结点(如果有的话),其语句如下:

ptr = ptr->next;以上语句使用指向结点后继的指针来替换了指向该结点的指针,实现了结点之间的移动。因此,要打印整个链表,可以使用如下代码:

    LinkNode *ptr = head;//初始化遍历指针指向要遍历链表的头指针
    while (ptr != nullptr) {//只要这个指针不是空指针
        cout << ptr->a << endl;//输出结点的内容
        ptr = ptr->next;//移动到下一个结点
    }
//输出结果(假设head所指向的线性表包含11.11,22.22,33.33这三个数据)
11.11
22.22
33.33

Q.E.D.