数据结构学习-链表（一）链表基本介绍及创建
天才小猫熊
805
2023.02.20
发布于 未知归属地
C++学习分享

本文仅用于个人学习记录，编程语言为C++，希望大家共同交流。

链表的基本介绍

C++中的链表是一种非常常用的数据结构，可以用来动态地存储和操作数据。

它可以存储一系列的数据，并且允许在其中添加、删除和修改元素。链表可以分为单向链表、双向链表和循环链表等多种类型。

链表由一系列的节点组成，每个节点包含两个成员变量，分别是数据域和指针域。数据域用来存储节点的数据，指针域用来指向下一个节点或者上一个节点（在双向链表中）。

以下是一个简单的链表节点结构的示例代码：

struct ListNode {
    int val;
    ListNode* next;
};
  • 这个结构体包含两个成员变量 val 和 next。其中，val 用来存储节点的数据，next 是一个指向下一个节点的指针。
  • 链表的逻辑结构类似于下图
  • image.png

图片来源于网络，链接放在文末。

使用这个结构体可以定义一个单向链表，每个节点包含一个整数和指向下一个节点的指针，示例代码如下：

ListNode* head = nullptr;  // 链表头指针

// 创建第一个节点
head = new ListNode();
head->val = 1;
head->next = nullptr;

// 创建第二个节点
ListNode* node1 = new ListNode();
node1->val = 2;
node1->next = nullptr;
head->next = node1;

// 创建第三个节点
ListNode* node2 = new ListNode();
node2->val = 3;
node2->next = nullptr;
node1->next = node2;

这个示例代码创建了一个包含三个节点的链表，其中头节点的值为 1，第二个节点的值为 2，第三个节点的值为 3。可以使用指针 head 来访问链表中的元素。

关于 head->next = nullptr 和node1->next = nullptr

  • head->next = nullptr 是将头节点的下一个节点指针设为 null，表示这是一个空链表，头节点不指向任何节点。头节点不存储数据，只是用来指向链表的第一个节点，它通常是链表的入口。

在创建一个空链表时，可以将头节点的下一个节点指针设置为 null，表示链表不包含任何节点。当链表中添加第一个节点时，将头节点的指针指向这个节点，从而建立链表。如果链表不是空的，则头节点的指针应该指向链表的第一个节点。

在示例程序中，我们将头节点的下一个节点指针设置为 null，因为这是一个空链表，没有任何节点。随后，我们依次创建链表中的每个节点，并将它们链接起来，从而建立链表。

  • node1->next = nullptr 是将节点 node1 的下一个节点指针设为 null，表示节点 node1 后面没有任何节点。

在链表中，每个节点都有一个数据成员和一个指向下一个节点的指针成员。指针成员用于链接节点，将一个节点和另一个节点相连，从而形成链表。如果一个节点的指针成员为 null，则表示该节点是链表的最后一个节点，它不再指向任何其他节点。

在示例程序中，我们依次创建链表中的每个节点，并将它们链接起来，从而建立链表。对于节点 node1，它的下一个节点指针被设为 null，表示它是链表中的最后一个节点，它不再指向其他节点。这意味着，当遍历链表时，当我们到达 node1 后面没有其他节点可以访问，遍历也就到此结束了。

创建一个链表

下面是一个示例程序，演示如何创建一个链表并遍历它：
编译环境VS2019

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
};

int main() {
    // 创建头节点
    ListNode *head = new ListNode();
    head->val = 1;
    head->next = nullptr;

    // 创建第一个节点
    ListNode *node1 = new ListNode();
    node1->val = 2;
    node1->next = nullptr;
    head->next = node1;

    // 创建第二个节点
    ListNode *node2 = new ListNode();
    node2->val = 3;
    node2->next = nullptr;
    node1->next = node2;

    // 遍历链表
    ListNode *p = head;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 释放内存
    p = head;
    while (p != nullptr) {
        ListNode *temp = p;
        p = p->next;
        delete temp;
    }

    return 0;
}

在这个示例程序中，我们首先创建一个头节点，然后创建第一个节点，并将头节点的指针指向第一个节点。然后再创建第二个节点，并将第一个节点的指针指向第二个节点。最后，我们遍历链表并输出每个节点的值。需要注意的是，在使用链表时，需要注意内存管理。在 C++ 中，使用 new 操作符动态分配的内存需要手动释放，否则会导致内存泄漏。因此，在这个示例程序中，我们需要手动释放每个节点的内存，可以使用 delete 操作符来完成。

程序输出的结果是：

1 2 3

这说明程序成功创建了一个包含三个节点的链表，并遍历了每个节点，按照顺序输出了每个节点的值。最后程序释放了链表中每个节点所占用的内存空间，防止内存泄漏。

参考来源：

  1. 一口气搞懂「链表」，就靠这20+张图了 https://zhuanlan.zhihu.com/p/249144171
  2. 链表：创建一个简单的链表并输出链表内容 https://www.cnblogs.com/Wayne123/p/9796014.html
评论 (2)