C++ 中的链表数据结构及图解

2025年3月17日 | 阅读 8 分钟

单链表是一种我们用来存储数据元素的线性动态数据结构。数组也是一种线性数据结构，其中数据项存储在连续的内存块中。

与数组不同，链表不需要将数据元素存储在连续的内存区域或块中。

链表由称为“节点”的元素组成，每个节点分为两部分。第一部分是存储实际数据的地方，第二部分是存储指向下一个节点的指针的地方。这种结构称为“单链表”。

C++ 中的链表

本教程将深入介绍单链表。

单链表的结构如下图所示

Linked List Data Structure in C++ With Illustration

正如我们在上面所见，链表的第一个节点称为“头”，最后一个节点称为“尾”。由于最后一个节点没有指定内存地址，因此链表的最后一个节点将具有空（null）的下一个指针。
由于每个节点都包含指向下一个节点的指针，因此链表中的数据元素不需要存储在连续的位置。节点可以分散在内存中。由于每个节点都包含下一个节点的地址，因此我们可以随时访问节点。
我们可以快速地在链表中添加和删除数据项。因此，链表可以动态地增加或收缩。链表没有最大数据项数量限制。因此，只要有可用的内存，我们就可以向链表中添加任意数量的数据项。
由于我们不必提前指定链表需要多少个项，因此链表除了易于插入和删除外，还可以节省内存空间。链表唯一使用的空间是存储指向下一个节点的指针，这会增加一些开销。

接下来，我们将介绍可以在链表上执行的各种操作。

1) 插入

通过向链表添加数据的操作来扩展链表。虽然这看起来很简单，但考虑到链表的结构，我们知道每次添加数据项时，我们都必须更改新添加数据项之前和之后节点的下一个指针。

第二个需要考虑的方面是新数据项将被插入的位置。

数据项可以插入到链表中的三个位置。

a. 在链表开头

下图所示的链表包含数字 2->4->6->8->10。如果我们向列表中添加一个新节点 1 作为第一个节点，那么指向节点 2 的头节点现在将指向节点 1，而节点 1 的下一个指针将具有节点 2 的内存地址，如下图所示。

因此，新的链表是 1->2->4->6->8->10。

b. 在给定节点之后

在这种情况下，我们给定一个节点，并必须在其后面添加一个新节点。如果节点 f 被添加到链表 a->b->c->d->e 的节点 c 之后，链表将如下所示。

因此，我们在上面的图中检查给定的节点是否存在。如果存在，则创建一个新节点 f。然后，我们将节点 c 的下一个指针指向新节点 f。节点 f 的下一个指针现在指向节点 d。

c. 在链表末尾

第三种情况是，将一个新节点添加到链表的末尾。考虑下面的链表：a->b->c->d->e，并在末尾添加节点 f。添加节点后，链表将如下所示。

因此，我们创建一个新节点 f。然后将指向 null 的尾指针指向 f，并将节点 f 的下一个指针指向 null。在下面的编程语言中，我们已经生成了所有三种插入函数。

在 C++ 中，链表可以声明为结构体或类。声明为结构体的链表是经典的 C 风格声明。在现代 C++ 中，链表主要用作类，尤其是在使用标准模板库时。

以下应用程序使用结构体来声明和生成链表。其成员将是数据和指向下一个元素的指针。

C++ 程序

#include <iostream>
using namespace std;

struct Node
{
   int data;
   struct Node *next;
};
void push ( struct Node** head, int nodeData )
{
   struct Node* newNode1 = new Node;
 
   newNode1 -> data = nodeData;
   newNode1 -> next = (*head);
 
   (*head) = newNode1;
}
void insertAfter ( struct Node* prevNode, int nodeData )
{
if ( prevNode == NULL )
{
   cout << "the given previous node is required,cannot be NULL"; 
   return; 
    
} 
   struct Node* newNode1 =new Node; 
   newNode1 -> data = nodeData;
   newNode1 -> next = prevNode -> next;
    prevNode -> next = newNode1;
}
void append ( struct Node** head, int nodeData )
{
struct Node* newNode1 = new Node;
 
struct Node *last = *head;
newNode1 -> data = nodeData;
newNode1 -> next = NULL;
if ( *head == NULL )
{
*head = newNode1;
return;
}
while ( last -> next != NULL )
last = last -> next;
last -> next = newNode1;
return;
}
void displayList ( struct Node *node )
{
   while ( node != NULL )
   {
      cout << node -> data << "-->";
      node = node -> next;
   }
 
if ( node== NULL)
cout<<"null"; 
} 
int main () 
{
struct Node* head = NULL;
append ( &head, 15 ); 
push ( &head, 25 ); 
push ( &head, 35 ); 
append ( &head, 45 );
insertAfter ( head -> next, 55 );
 
cout << "Final linked list: " << endl;
displayList (head);
 
return 0;
}

输出

Final linked list: 
35-->25-->55-->15-->45-->null

2) 删除

与插入类似，从链表中删除节点也需要考虑节点可以被删除的多个点。我们可以删除链表的第一个、最后一个或任意一个第 k 个节点。为了在删除后维护链表，我们必须正确更新下一个指针和所有其他链表指针。

在下面的 C++ 实现中，我们有两个删除方法：删除列表的第一个节点和删除列表的最后一个节点。我们首先将节点添加到列表的头部。然后显示每个添加和删除之后的列表内容。

C++ 程序

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   };
Node* deletingFirstNode ( struct Node* head )
{
   if ( head == NULL )
   return NULL;
   Node* tempNode = head;
   head = head -> next;
   delete tempNode;
 
   return head;
}
Node* removingLastNode ( struct Node* head )
{
   if ( head == NULL )
   return NULL;
 
   if ( head -> next == NULL ) {
      delete head;
      return NULL;
   }
Node* secondLast = head;
while ( secondLast -> next -> next != NULL )
secondLast = secondLast->next;
delete ( secondLast -> next );
secondLast -> next = NULL;
 
return head;
}
void push ( struct Node** head, int newData )
{
   struct Node* newNode1 = new Node;
   newNode1 -> data = newData;
   newNode1 -> next = ( *head );
   ( *head ) = newNode1;
}
int main()
{
   Node* head = NULL;
   push ( &head, 25 );
   push ( &head, 45 );
   push ( &head, 65);
   push ( &head, 85 );
   push ( &head, 95 );
 
         Node* temp;
 
   cout << "Linked list created " << endl; for ( temp = head; temp != NULL; temp = temp -> next )
   cout << temp->data << "-->";
   if ( temp == NULL )
   cout << "NULL" << endl;
   head = deletingFirstNode (head);
   cout << "Linked list after deleting head node" << endl; for ( temp = head; temp != NULL; temp = temp -> next )
   cout << temp->data << "-->";
   if ( temp == NULL )
   cout<<"NULL"<<endl;
   head = removingLastNode (head);
   cout << "Linked list after deleting last node" << endl; for ( temp = head; temp != NULL; temp = temp -> next )
   cout << temp -> data << "-->";
   if ( temp == NULL )
   cout << "NULL";
 
   return 0;
}

输出

Linked list created 
95-->85-->65-->45-->25-->NULL
Linked list after deleting head node
85-->65-->45-->25-->NULL
Linked list after deleting last node
85-->65-->45-->NULL

节点计数

在遍历链表时，可以执行计数节点数量的操作。在前面的方法中，我们看到，如果我们想插入/删除一个节点或显示链表的内容，我们必须从头开始遍历链表。

设置一个计数器并在遍历每个节点时递增，将为我们提供链表中的节点数量。

数组和链表之间的区别

Array	链表
数组的大小是固定的。	链表的大小是可变的。
插入新元素困难。	插入和删除更简单。
允许随机访问。	不允许随机访问。
元素相对靠近或连续存储。	元素不连续。
不需要为下一个指针分配额外空间。	下一个指针需要额外内存。

功能

由于链表和数组都是存储对象的线性数据结构，因此它们在大多数应用中可以以相似的方式使用。

以下是一些链表的应用示例

可以使用链表来实现栈和队列。
当我们需要将图表示为邻接表时，可以使用链表来实现它们。
我们还可以使用链表来表示数学多项式。
在哈希的情况下，链表用于实现桶。
当程序需要动态内存分配时，我们可以使用链表，因为在这种情况下链表效率更高。

结论

链表是一种数据结构，用于以线性但非连续的形式存储数据元素。链表由节点组成，每个节点有两个组件。第一个组件包含数据，第二个组件有一个指针，存储列表中下一个成员的内存地址。

作为链表结束的标志，列表中的最后一项的下一个指针设置为 NULL。Head 是列表中的第一项。链表允许执行各种操作，如插入、删除、遍历等。对于动态内存分配，链表比数组更受欢迎。

由于无法像数组那样随机访问元素，因此打印或遍历链表很困难。与数组相比，插入-删除操作的成本较低。

在本教程中，我们学习了有关线性链表的所有知识。链表也可以是双向链表或循环链表。在接下来的教程中，我们将详细介绍这些链表。

下一主题按给定大小的组反转链表

C++ 中的链表数据结构及图解

C++ 中的链表

1) 插入

2) 删除

节点计数

数组和链表之间的区别

功能

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

C++ 中的链表数据结构及图解

C++ 中的链表

1) 插入

2) 删除

节点计数

数组和链表之间的区别

功能

结论

相关帖子

检查一个队列是否可以使用一个栈排序到另一个队列

图的迭代深度优先遍历

检查二维矩阵中是否存在可能的路径

分配最少页数

复制带有 next 和 arbit 指针的链表

融合 vs 堆叠

二进制链表的十进制等价物

列表数据结构

最大化硬币，使根到叶子路径和为正

数组中第 K 大的元素

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器