单链表设计与实现

01. 单链表简介

在数据结构中，单链表的实现可以分为 带头结点 和 不带头结点 两种方式，这里我们讨论第二种方式。

• 头结点：链表第一个节点不存实际数据，仅作为辅助节点指向首元节点（第一个数据节点）。
• 头指针：永远指向头结点（非空链表头结点始终存在）。

单链表核心数据结构及操作声明：

typedef struct Node {int data;         // 节点数据域struct Node* next;// 节点指针域
} Node;
// 初始化带头结点的空链表
Node* InitList();
// 头插法建立链表
void HeadInsert(Node* list, int data);
// 尾插法建立链表
void TailInsert(Node* list, int data);
// 删除指定数据节点
void Delete(Node* list, int data);
// 遍历打印链表
void PrintList(Node* list);
//创建单链表
Node* list = InitList();
HeadInsert(list,1);//如头插
TailInsert(list,2);//如尾插

02.链表初始化

创建一个头结点，内部的data标明有多少个节点的计数，头结点的指针域置为空。

Node* InitList() {Node* list = (Node*)malloc(sizeof(Node));list->data = 0;list->next = NULL;return list;
}

---

03.头插法与尾插法

头插法简单，只需要在头结点后面插入即可，尾插法较为复杂，需要保存头结点指针，当list->next的节点不为空的时候，会继续往下面执行while循环，跳出循环的时候标明已经指向最后一个结点，随后即可插入。

void headInsert(Node* list, int data) {Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = list->next;list->next = node;list->data++;
}
void tailInsert(Node* list, int data) {Node* head = list;//此处会改变头结点，所以临时保存一下Node* node = (Node*)malloc(sizeof(Node));node->data = data;node -> next = NULL;list = list->next;//将指针移动到头结点，头结点也移动了！！！while (list->next) {//当list的下一个节点不为空的时候，会继续往下面执行list = list->next;//list继续往下面执行}list->next = node;head->data++;
}

---

04.链表的删除

链表的删除需要pre和current两个指针配合，通过比对其中的data里面的数据进行判断，不符合时，两个指针都向后移，知道匹配到对应数据时停下删除该结点。

void Delete(Node* list, int data) {Node* pre = list;Node* current = list->next;while (current){if (current->data = data) {pre->next = current->next;free(current);break;/无重复退出}pre = current;current = current->next;}list->data--;
}

---

05.链表的输出

依次循环输出即可。

void printlist(Node* list) {list = list->next;//指向头结点while (list){//list不为空就继续执行printf("%d ", list->data);list = list->next;//list往下走}printf("\n");
}

---

图片后续有时间会补上！！

;
list = list->next;//list往下走
}
printf(“\n”);
}

---### 图片后续有时间会补上！！