当前位置：首页 > news >正文

【C++】链表

news 2025/6/30 15:04:45

链表是一种常见的数据结构，用于存储和组织数据。它的每个元素被称为结点（Node），结点是链表的基本单位，链表由一系列结点（Node）组成，每个结点包含两个部分：数据部分（数据域）和指针部分（指针域）。

数据域用于存储结点所携带的数据，可以是任意类型，例如整数、字符、对象等。而指针域用于存储指向下一个结点的指针，形成了结点之间的链接。因此链表的对象也被称为结点。每个结点代表链表中的一个元素或数据项。

链表有多种类型，其中最常见的是单向链表（Singly Linked List）和双向链表（Doubly Linked List）。

单向链表中，每个结点只有一个指针，指向下一个结点。链表的第一个结点称为头结点，最后一个结点的指针为空（NULL）。

双向链表中，每个结点有两个指针，一个指向前一个结点，一个指向下一个结点。这样的设计使得在双向链表中可以从任意一个结点开始，向前或向后遍历链表。

链表的优点之一是它的动态性。与数组不同，链表的大小可以在运行时动态地增长或缩小，不需要预先指定固定的容量。这使得链表在需要频繁插入和删除节点的场景中更加高效。

链表的缺点是访问特定位置的结点需要从头结点开始遍历，直到找到目标结点，因此访问效率较低。此外，链表需要额外的空间来存储结点的指针，因此在空间利用方面可能不如数组。

在实际应用中，链表常用于实现栈、队列和其他高级数据结构，也可以用作辅助数据结构来解决特定问题。

下面是一个简单的单向链表的示例代码，用于演示链表的基本操作：

#include <iostream>// 定义链表节点
struct Node {int data;Node* next;//data用于存储节点的数据，而next是指针域，用于指向下一个节点的地址。
};// 遍历并打印链表
void printLinkedList(Node* head) {Node* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;
}int main() {// 创建链表节点Node* head = new Node();Node* second = new Node();Node* third = new Node();// 设置节点的数据和链接关系head->data = 1;head->next = second;second->data = 2;second->next = third;third->data = 3;third->next = nullptr;// 打印链表printLinkedList(head);// 释放链表内存delete head;delete second;delete third;return 0;
}