链表（linked list）是一种常见的数据结构，用于存储一系列元素。它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
在 C++ 中，可以使用结构体来表示链表节点，然后使用指针将这些节点连接起来。
----------
在常见的链表实现中，头指针（head pointer）是链表的一部分。头指针是一个指针变量，指向链表中的第一个节点。通过头指针，可以访问整个链表的节点序列。
在 C++ 中，头指针通常是一个类的私有成员变量，在链表的操作中用来标识链表的起始位置。通过头指针，可以遍历整个链表，执行插入、删除等操作。
需要注意的是，头指针只是指向链表中第一个节点的指针，它本身并不包含任何数据。链表的实际数据存储在节点中，而头指针只是用来指示链表的起始位置。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class LinkedList {
private:
Node* head; // 头指针，指向链表的第一个节点
public:
LinkedList() {
head = nullptr; // 初始时链表为空
}
// 在链表头部插入一个新节点
void insertAtBeginning(int newData) {
Node* newNode = new Node;
newNode->data = newData;
newNode->next = head;
head = newNode;
}
// 删除链表中的第一个节点
void deleteAtBeginning() {
if (head == nullptr) {
cout << "Linked list is empty. Cannot delete from an empty list." << endl;
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
// 打印链表的所有节点数据
void printList() {
Node* temp = head;
cout << "Linked List: ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
LinkedList myList;
myList.insertAtBeginning(35);
myList.insertAtBeginning(75);
myList.insertAtBeginning(49);
myList.printList(); // 输出: Linked List: 9 7 3
myList.deleteAtBeginning();
myList.printList(); // 输出: Linked List: 7 3
return 0;
}
让我们来解释一下插入数据的顺序和头指针之间的关系。
// 在单向链表中，头指针通常指向链表中的第一个节点。当我们要在链表的头部插入一个新节点时，我们需要进行以下步骤：
// 创建一个新节点，并设置它的数据值。
// 将新节点的 next 指针指向当前的第一个节点，使新节点成为新的第一个节点。
// 更新头指针，使它指向新的第一个节点。
// 这样做的原因是，链表的头指针需要始终指向链表的第一个节点，以便我们能够轻松地访问整个链表。
-------------------
// 这段代码定义了一个名为 insert 的函数，用于在链表中插入新节点。让我解释一下这段代码的逻辑：
// 函数接受两个参数：指向链表头节点的引用 head 和要插入的新节点的值 value。
// 首先，它创建了一个新的节点 newNode，并将新节点的数据域初始化为 value。
// 接着，它检查链表是否为空。如果链表为空（即 head 为 nullptr），则将新节点设为链表的头节点。
// 如果链表不为空，则遍历链表，直到找到最后一个节点（即指针域为 nullptr 的节点）。
// 将新节点链接到链表的末尾，即将当前最后一个节点的指针域指向新节点。
#include <iostream>
// 定义链表节点结构体
struct Node {
int data; // 数据域
Node* next; // 指针域，指向下一个节点
};
// 在链表中插入新节点
// 这段代码定义了一个名为 insert 的函数，用于在链表中插入新节点。让我解释一下这段代码的逻辑：
// 函数接受两个参数：指向链表头节点的引用 head 和要插入的新节点的值 value。
// 首先，它创建了一个新的节点 newNode，并将新节点的数据域初始化为 value。
// 接着，它检查链表是否为空。如果链表为空（即 head 为 nullptr），则将新节点设为链表的头节点。
// 如果链表不为空，则遍历链表，直到找到最后一个节点（即指针域为 nullptr 的节点）。
// 将新节点链接到链表的末尾，即将当前最后一个节点的指针域指向新节点。
// 这样，新节点就成功地插入到了链表的末尾。这个函数的时间复杂度是 O(n)，其中 n 是链表中节点的数量，因为它需要遍历整个链表来找到最后一个节点。
void insert(Node*& head, int value) {
Node* newNode = new Node;
newNode->data = value; // 手动设置数据域的值
newNode->next = nullptr; // 手动设置指针域的值
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {// 如果链表不为空，则遍历链表，直到找到最后一个节点（即指针域为 nullptr 的节点）。
current = current->next;
}
current->next = newNode;// 将新节点链接到链表的末尾，即将当前最后一个节点的指针域指向新节点。
}
}
// 打印链表
void printList(Node* head) {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
// 主函数
int main() {
Node* head = nullptr;
insert(head, 1);
insert(head, 2);
insert(head, 3);
printList(head);
return 0;
}
--------------------------------------------
// 在没有头指针的情况下，我们仍然需要一个指针来引导我们访问链表的第一个节点。这个指针可以是一个指向第一个节点的指针，比如在示例中使用的 start 指针。通过使用这个指针，我们可以找到链表的第一个节点，并在其前面插入新节点，然后更新 start 指针以指向新的第一个节点。
// 因此，插入数据的顺序与头指针的关系在于，无论是否有头指针，我们都需要确保链表的第一个节点正确地指向新插入的节点，以确保我们可以轻松地访问整个链表。
#include <iostream>
// 定义节点结构体
struct Node {
int data;
Node* next;
};
// 在链表头部插入一个新节点
Node* insertAtBeginning(Node* start, int newData) {
// 创建一个新节点
Node* newNode = new Node;
newNode->data = newData;
newNode->next = start; // 新节点的下一个节点指向当前第一个节点
return newNode; // 返回新节点作为新的第一个节点
}
// 打印链表
void printList(Node* start) {
Node* current = start;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
int main() {
Node* start = nullptr; // 定义一个指向第一个节点的指针，并初始化为 nullptr
// 在链表头部插入节点
start = insertAtBeginning(start, 3);
start = insertAtBeginning(start, 7);
start = insertAtBeginning(start, 9);
// 打印链表
std::cout << "Linked List: ";
printList(start);
return 0;
}