链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。与数组不同,链表不是连续的内存空间,而是通过指针链接在一起。下面我们将深入探讨如何使用C++实现链表,包括创建、插入、删除和遍历等操作。
一、链表的基本原理
链表由多个节点(Node)组成,每个节点至少包含两部分:存储的数据和指向下一个节点的指针。链表的起始节点称为头节点(Head),终止节点称为尾节点(Tail),尾节点的指针通常指向空(NULL)。
链表的主要优势在于动态分配内存,这使得在插入和删除节点时比数组更加高效。然而,访问链表中的元素通常需要从头节点开始遍历,因此不如数组直接访问元素快。
二、C++实现链表
1. 定义节点类
首先,我们需要定义一个节点类,它包含数据和指向下一个节点的指针。
class Node {
public:
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
// 构造函数
Node(int data) {
this->data = data;
this->next = NULL;
}
};
2. 创建链表
我们可以通过连续创建新的节点,并将它们链接在一起来构建链表。
// 创建链表函数
Node* createLinkedList(int arr[], int n) {
Node* head = NULL; // 初始化头节点为空
Node* tail = NULL; // 初始化尾节点为空
for (int i = 0; i next = newNode; // 将尾节点的next指向新节点
tail = newNode; // 更新尾节点为新节点
}
}
return head; // 返回头节点指针,代表整个链表
}
3. 遍历链表
要遍历链表中的所有节点,我们需要从头节点开始,通过每个节点的next指针访问下一个节点,直到next为空(即达到尾节点)。
void traverseLinkedList(Node* head) {
Node* current = head; // 从头节点开始遍历
while (current != NULL) { // 当当前节点不为空时继续遍历
cout data next; // 移动到下一个节点
}
cout