单链表基本算法(理论及 C/C++ 代码实现)单链表(带头节点)的基本概念
单链表是一种基本的链式数据结构,由节点(Node)构成,每个节点包含两个部分:数据区域和指针区域。指针区域用于存储下一个节点的地址。因此,单链表是一种线性表,但与数组不同,它的存储空间不是连续的。
单链表的基本概念包括:
1. 节点:链表中的元素,每个节点包含两部分,数据部分(data)和指向下一个节点的指针(next)。
2. 头节点:头节点是整个链表的起点,用于存储链表的头信息,通常不存储实际数据,主要用于方便链表的操作。
3. 链表尾部:指向 NULL
的最后一个节点,表示链表的结束。
带头节点的单链表相比不带头节点的链表,多了一个不存储实际数据的头节点,能够简化某些操作,尤其是在处理首位置插入和删除操作时。
以下是单链表一些常见操作及其 C/C++ 实现:
#include <iostream>
using namespace std;
// 定义单链表节点结构
struct ListNode {
int data; // 节点数据
ListNode* next; // 下一节点的指针
// 构造函数
ListNode(int x) : data(x), next(NULL) {}
};
// 初始化链表,返回头节点
ListNode* initList() {
// 创建头节点,头节点数据部分通常不使用
return new ListNode(0);
}
// 在链表末尾插入新节点
void insertAtEnd(ListNode* head, int data) {
ListNode* newNode = new ListNode(data); // 创建新节点
ListNode* current = head; // 从头节点开始遍历
// 找到最后一个节点
while (current->next != NULL) {
current = current->next;
}
// 将新节点连接到最后一个节点之后
current->next = newNode;
}
// 在指定位置插入新节点
void insertAtPosition(ListNode* head, int data, int position) {
ListNode* newNode = new ListNode(data);
ListNode* current = head;
// 找到指定位置的前一个节点
for (int i = 0; i < position && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
cout << "Position out of bounds" << endl;
return;
}
// 插入节点
newNode->next = current->next;
current->next = newNode;
}
// 删除指定位置的节点
void deleteAtPosition(ListNode* head, int position) {
ListNode* current = head;
// 找到指定位置的前一个节点
for (int i = 0; i < position && current->next != NULL; i++) {
current = current->next;
}
if (current->next == NULL) {
cout << "Position out of bounds" << endl;
return;
}
// 删除节点
ListNode* temp = current->next;
current->next = current->next->next;
delete temp;
}
// 打印链表
void printList(ListNode* head) {
ListNode* current = head->next; // 跳过头节点
while (current != NULL) {
cout << current->data << " -> ";
current = current->next;
}
cout << "NULL" << endl;
}
// 主函数示例
int main() {
ListNode* head = initList(); // 初始化带头节点的链表
insertAtEnd(head, 5);
insertAtEnd(head, 10);
insertAtEnd(head, 15);
printList(head); // 输出: 5 -> 10 -> 15 -> NULL
insertAtPosition(head, 1, 0);
printList(head); // 输出: 1 -> 5 -> 10 -> 15 -> NULL
deleteAtPosition(head, 2);
printList(head); // 输出: 1 -> 5 -> 15 -> NULL
return 0;
}
上述代码段演示了如何创建一个带头节点的单链表以及进行基本的插入、删除、打印操作。注意,带头节点的链表操作相对简单,因为不需要考虑链表为空或删除第一个节点时的特殊情况。