第一百零六天学习记录：数据结构与算法基础：单链表（王卓教学视频）

**第一百零六天学习记录**

**数据结构与算法基础：单链表**

**王卓教学视频**

今天是我们学习的第106 天，主题是单链表。单链表是一种常见的线性数据结构，它们通过指针连接起来，每个结点包含一个值和一个指向下一个结点的指针。

### 单链表定义

ctypedef struct Node {
 int data;
 struct Node* next;
} Node;

在上面的代码中，我们定义了一个 `Node` 结构体，包含两个成员变量：`data` 和 `next`。其中，`data` 是结点的值，而 `next` 是指向下一个结点的指针。

### 单链表操作单链表支持以下基本操作：

* **插入**:在链表中插入一个新结点。
* **删除**:从链表中删除一个结点。
* **查找**:根据值找到链表中的某个结点。
* **遍历**:按照链表的顺序访问所有结点。

### 单链表实现下面是单链表的基本实现：

ctypedef struct Node {
 int data;
 struct Node* next;
} Node;

// 创建一个新结点Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 if (!newNode) {
 printf("Memory error
");
 return NULL;
 }
 newNode->data = data;
 newNode->next = NULL;
 return newNode;
}

// 插入结点void insertNode(Node** head, int data) {
 Node* newNode = createNode(data);
 if (*head == NULL) {
 *head = newNode;
 return;
 }
 Node* current = *head;
 while (current->next != NULL) {
 current = current->next;
 }
 current->next = newNode;
}

// 删除结点void deleteNode(Node** head, int data) {
 if (*head == NULL) return;

 // 如果删除的结点是头结点 if ((*head)->data == data) {
 Node* temp = *head;
 *head = (*head)->next;
 free(temp);
 return;
 }

 Node* current = *head;
 while (current->next != NULL) {
 if (current->next->data == data) {
 Node* temp = current->next;
 current->next = current->next->next;
 free(temp);
 return;
 }
 current = current->next;
 }
}

// 查找结点Node* findNode(Node* head, int data) {
 while (head != NULL) {
 if (head->data == data) {
 return head;
 }
 head = head->next;
 }
 return NULL;
}

// 遍历链表void traverseList(Node* head) {
 Node* current = head;
 while (current != NULL) {
 printf("%d ", current->data);
 current = current->next;
 }
 printf("
");
}

在上面的代码中，我们实现了单链表的基本操作，包括插入、删除、查找和遍历。

### 单链表应用单链表有很多实际应用：

* **缓存管理**:单链表可以用来管理缓存中的数据。
* **浏览器历史记录**:单链表可以用来保存浏览器的历史记录。
* **文件系统**:单链表可以用来组织文件系统中的文件。

### 总结本文介绍了单链表的基本概念、定义和实现。我们讨论了单链表支持的基本操作，包括插入、删除、查找和遍历。最后，我们看到了单链表在实际应用中的重要性。

**参考资料**

* 《数据结构与算法基础》王卓* 《C语言程序设计》周志明