链表(C语言)—学习笔记

一、简介

链表的基本概念

        链表由一系列节点组成，每个节点包含数据域和指针域。数据域存储具体的数据，指针域存储指向下一个节点的地址（在单链表中），通过指针将各个节点连接起来，形成一个链式的结构，数据就可以按照这个链条依次访问。

链表的类型

• 单链表：每个节点只有一个指向下一个节点的指针，节点依次相连形成一个单向的链条，只能从链表头开始沿着指针方向依次访问后续节点。比如火车车厢，每节车厢（节点）只连接着后面一节车厢，只能朝着一个方向前进。
• 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点，这样可以在链表中双向移动，既可以从前往后访问，也可以从后往前访问。就像双向车道，车辆可以双向行驶。
• 循环链表：分为单循环链表和双循环链表。单循环链表的尾节点的指针指向头节点，形成一个环形；双循环链表不仅尾节点的指针指向头节点，头节点的前向指针也指向尾节点。例如操场上的跑道，运动员可以一直循环跑下去。

链表的操作

初始化链表、插入操作、删除操作、查找操作、遍历操作、链表长度计算等

链表的优缺点

• 优点
  • 动态分配内存：链表不需要预先分配固定大小的内存空间，在需要添加新节点时可以动态分配内存，适合数据数量不确定的场景。比如一个在线游戏的玩家列表，玩家数量随时可能变化，使用链表可以灵活处理。
  • 插入和删除效率高：在链表中插入或删除一个节点，只需要修改相关节点的指针，时间复杂度为O(1)（前提是已经知道要操作的位置）。例如在一个人员名单链表中添加或移除一个人，只需要调整相关人员之间的连接关系。
• 缺点
  • 随机访问效率低：要访问链表中的某个节点，需要从链表头开始依次遍历，直到找到目标节点，时间复杂度为O(n)。就像在一个长长的队伍中找某个人，只能从队伍开头一个一个地找。
  • 额外的指针开销：每个节点都需要额外的指针来存储下一个节点（或前后节点）的地址，会增加内存的使用。

链表的应用场景

实现栈、队列等数据结构。 内存管理、文件系统等领域。

二、链表操作

typedef struct ListNode {    //定义链表的结构体int val;struct ListNode *next;
}ListNode;

//创建一个新的结点
ListNode *CreateNode(const int val) {ListNode *NewNode = (ListNode *)malloc(sizeof(ListNode));if (NewNode == NULL) {printf("内存分配失败");return NULL;}NewNode->val = val;NewNode->next = NULL;return NewNode;
}

1. 初始化链表

初始化链表是创建链表的起始步骤。对于单链表，通常会设置一个头指针，若链表为空，头指针指向 NULL。在有头节点的链表中，会先创建一个头节点，该节点的数据域可空置不用，其指针域初始化为 NULL，头指针指向这个头节点。初始化操作是后续所有链表操作的基础，为链表后续的节点添加等操作做好准备。

void InitList(ListNode *head) {head->next = NULL;
}

2. 插入操作

• 头插入：创建新节点后，直接将新节点的指针指向当前链表的头节点（若有头节点则指向头节点之后的第一个数据节点），然后更新头指针使其指向新节点。这种插入方式时间复杂度为 O(1)，因为只涉及到指针的重新赋值，不依赖链表的长度。例如在一个记录学生信息的链表中，若新入学一名学生，使用头插入可以快速将其信息添加到链表前端。

void InsertHead(ListNode *head,const int val) {ListNode *NewNode = CreateNode(val);if (NewNode == NULL) {return;}NewNode->next = head->next;head->next = NewNode;
}

• 尾插入：首先要遍历整个链表，找到链表的尾节点（尾节点的指针域为 NULL）。创建新节点后，将尾节点的指针指向新节点，新节点的指针域置为 NULL。由于需要遍历链表，其时间复杂度为 O(n)，其中 n 是链表的长度。比如在一个任务列表链表中，将新任务添加到列表末尾，就可以使用尾插入。

void InsertEnd(ListNode *head, const int val) {ListNode *NewNode = CreateNode(val);if (NewNode == NULL) {return;}if (head == NULL) {head = NewNode;}else {ListNode *temp = head;while (temp->next != NULL) {temp = temp->next;}temp->next = NewNode;}
}

• 指定位置插入：先遍历链表找到要插入位置的前一个节点。创建新节点后，让新节点的指针指向原位置的节点，再将前一个节点的指针指向新节点。此操作同样需要遍历链表来定位插入位置，时间复杂度为 O(n)。例如在一个按成绩排序的学生链表中，要将一个新学生插入到合适的位置，就需要先找到插入点。

3. 删除操作

• 删除头节点：将头指针直接指向原头节点的下一个节点（若有头节点则跳过原头节点后的第一个数据节点），然后释放原头节点的内存。该操作时间复杂度为 O(1)，因为只涉及指针的修改和一次内存释放。比如在一个新闻列表链表中，若第一条新闻过时需要删除，就可以使用这种方式。

void DeleteHead(ListNode *head) {if (head == NULL) {printf("链表为空，无法删除头结点。\n");return;}ListNode *temp = head;head->next = head->next->next;//free(temp->next);    //这个free有点问题，有没有大佬帮忙解决一下printf("头结点已删除。\n");
}

• 删除尾节点：需要遍历链表找到倒数第二个节点，将其指针域置为 NULL，然后释放尾节点的内存。由于要遍历链表，时间复杂度为 O(n)。例如在一个历史记录链表中，删除最后一条记录时就需要进行尾节点删除操作。

void DeleteEnd(ListNode *node) {//如果链表为空（即传入的 node 为 NULL），则直接返回，不进行任何操作。if (node == NULL) {   return;}//如果链表只有一个节点（即 node->next 为 NULL），则释放该节点，并将指针置为 NULLif (node->next == NULL) {free(node);}else {while (node->next->next != NULL) {node = node->next;}free(node->next);node->next = NULL;}
}

• 删除指定节点：先遍历链表找到要删除节点的前一个节点，然后将前一个节点的指针指向要删除节点的下一个节点，最后释放要删除节点的内存。此操作的时间复杂度也是 O(n)，因为需要遍历链表来定位节点。例如在一个联系人链表中，删除某个特定联系人的信息时就会用到。

4. 查找操作

从链表的头节点开始，依次比较每个节点的数据域与要查找的值。若找到匹配的节点，则返回该节点的指针；若遍历完整个链表都未找到，则返回 NULL。查找操作的时间复杂度为 O(n)，因为在最坏情况下需要遍历整个链表。比如在一个图书信息链表中查找某本特定图书的信息，就需要使用查找操作。

ListNode* findElement(ListNode* head, int target) {ListNode* current = head;while (current != NULL) {if (current->val == target) {return current;}current = current->next;}return NULL;
}

5. 遍历操作

从链表的头节点开始，通过节点的指针域依次访问每个节点，对每个节点的数据域进行相应的处理，如打印数据等。遍历操作会依次访问链表中的每一个节点，时间复杂度为 O(n)。例如在一个员工信息链表中，要打印出所有员工的信息，就需要进行遍历操作。

void printList(ListNode* head) {ListNode* current = head->next;while (current != NULL) {printf("%d ", current->val);current = current->next;}printf("\n");
}

6. 链表长度计算

从链表的头节点开始，设置一个计数器，每访问一个节点计数器加 1，直到遍历完整个链表，计数器的值就是链表的长度。此操作需要遍历链表，时间复杂度为 O(n)。比如在一个商品列表链表中，计算商品的数量时就会用到长度计算操作。

int LengthNode(const ListNode* head) {if (head == NULL) {return 0;}int len=0;while (head->next != NULL) {head = head->next;len++;}return len;
}