C++链表笔记

C++链表笔记

hash070 329 2022-03-03

简介

在计算机科学中，链表（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