单链表
1. 基础了解
学习之前先了解线性表、顺序表和链表
线性表的两个特点:
- 有限的序列
- 序列中的每一个元素都有唯一的前驱和后继,除了开头和结尾两个节点
顺序表的特点:
- 分配一块连续的内存去存放这些数据,例如数组
链表:
- 内存是不连续的,元素会各自被分配一块内存,内存和内存之间用指针进行项链
2. 单链表
- 一个节点包括:data、next
- next指向下一个节点的位置
- 一般包含 1个链表包含头结点 和 n个数据节点
3. 单链表操作:
-
增加
- 头插法:一个新的节点,next指向原先的链表头
- 尾插法:原先的链表尾指向,一个新的节点。
-
删除:
只需要找到对应节点,将对应节点的前一个节点指向这个节点的**后继,**只操作一个指针
4. 代码示例
-
定义新的类型:Node,用于创建节点
#include <stdio.h> #include <stdlib.h>/* 定义新的类型Node,用于创建节点 */ typedef struct Node {int data; //datastruct Node* next; //存放下一个节点结构体的位置 }Node;
-
初始化头节点函数
/* 初始化头结点 */ Node* initlist() {/* 开辟空间 */Node* list = (Node*)(malloc(sizeof(Node)));/* 初始化 */list->data = 0;list->next = NULL;return list; }
-
增加、删除函数
/* 头插法 */ 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* current = list; //保存头结点的地址Node* node = (Node*)(malloc(sizeof(Node)));node->data = data;node->next = NULL; //指向NULLwhile (current->next) //如果current的后继不为NULL、则进入while{current = current->next; //否则current会指向下一个节点}current->next = node; //将current指向的最后一个节点 与新节点连接list->data++; //当前链表中插入了一个元素 }/* 删除 */ void delete (Node* list, int data) {Node* current = list; //保存头结点地址Node* previous = list; //用于保存上一个结点地址current = current->next; //使current指向第一个(数据)节点的位置while (current){ //如果current不为空指针则进入whileif (current->data == data){ //如果是我要删除的dataprevious->next = current->next;//把上一个节点的next链接到下一个节点free(current); //释放当前节点list->data--; //当前链表中删除了一个元素break;}previous = current; //保存当前位置current = current->next; //指向下一个节点} }
-
打印列表函数
/* 打印链表 */ void printList(Node* list){Node* current = list; //保存头结点地址current = current->next; //使current指向第一个(数据)节点的位置while (current) { //如果current不为空指针则进入whileprintf("%d ", current->data);current = current->next; //指向下一个节点}printf("\\n"); }
-
测试
/* 测试 */ void main() {printf("Hello World!!\\n");/* 初始化链表 */Node* list = initlist();/* 头插法 */headInsert(list, 1);headInsert(list, 2);headInsert(list, 3);headInsert(list, 4);headInsert(list, 5);/* 尾插法 */tailInsert(list, 6);tailInsert(list, 7);tailInsert(list, 8);tailInsert(list, 9);tailInsert(list, 10);/* 删除 */delete(list, 1);delete(list, 6);/* 打印 */printList(list);return 0; }