一.链表的概念
链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的结构类似于一条链子，因此得名。 相比于传统的数组，链表具有以下特点： 1. 动态增长： 链表的节点可以在运行时动态地添加或删除，而不需要像数组那样预先分配固定的内存空间。 2. 高效插入和删除： 在链表中插入或删除节点只需要修改相邻节点的指针，不需要像数组那样进行大量的数据移动。 3. 不支持随机访问： 由于链表中的节点是通过指针链接起来的，所以无法像数组那样通过索引直接访问特定位置的元素。 根据指针的方向，链表可以分为单向链表、双向链表和循环链表等。其中，单向链表的指针只指向后一个节点，而双向链表的节点同时包含指向前一个和后一个节点的指针。循环链表则将最后一个节点的指针指向第一个节点，形成一个环状结构。 链表在很多编程场景中都有广泛应用，比如实现链表数据结构、哈希表、栈和队列等。它的灵活性和高效性使其在处理动态数据和需要频繁插入、删除操作的情况下具有优势。
二.链表中的常见问题
在链表中进行插入和删除操作时，有几个关键问题需要注意 1. 指针的正确更新：在插入和删除节点时，需要确保相关节点的指针正确地更新，以维护链表的完整性。特别是在双向链表中，需要同时更新前向和后向指针。 2. 空指针的处理：如果要删除链表中的最后一个节点，需要特别注意处理空指针，以避免后续操作出现错误。 3. 检查边界条件：在进行插入和删除操作之前，需要检查相关的边界条件，例如链表是否为空、要插入或删除的位置是否合法等。 4. 内存管理：在动态分配和释放节点内存时，需要注意内存泄漏和内存重复释放等问题，确保正确地管理内存资源。 5. 考虑特殊情况：例如，在插入节点时，如果要插入的位置是链表的头部，可能需要特殊处理。 6. 代码的可读性和可维护性：编写清晰、简洁的代码，并添加必要的注释，以提高代码的可读性和可维护性。
三.链表的优势
链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的结构类似于一条链子，因此得名。 相比于传统的数组，链表具有以下特点： 1. 动态增长：链表的节点可以在运行时动态地添加或删除，而不需要像数组那样预先分配固定的内存空间。 2. 高效插入和删除：在链表中插入或删除节点只需要修改相邻节点的指针，不需要像数组那样进行大量的数据移动。 3. 不支持随机访问：由于链表中的节点是通过指针链接起来的，所以无法像数组那样通过索引直接访问特定位置的元素。 根据指针的方向，链表可以分为单向链表、双向链表和循环链表等。其中，单向链表的指针只指向后一个节点，而双向链表的节点同时包含指向前一个和后一个节点的指针。循环链表则将最后一个节点的指针指向第一个节点，形成一个环状结构。 链表在很多编程场景中都有广泛应用，比如实现链表数据结构、哈希表、栈和队列等。它的灵活性和高效性使其在处理动态数据和需要频繁插入、删除操作的情况下具有优势。
四.手撕链表
代码语言：javascript复制typedef struct ListNode
{
Stu student;
struct ListNode* next;
}ListNode;
//创建头节点
ListNode* createHead()
{
ListNode* Head = (ListNode*)malloc(sizeof(ListNode));
if (Head == NULL)
return NULL;
Head->next = NULL;
return Head;
}
//创建节点
ListNode* createNode(Stu student)
{
ListNode* pcur = (ListNode*)malloc(sizeof(ListNode));
if (pcur == NULL)
return NULL;
pcur->student = student;
pcur->next = NULL;
return pcur;
}
//插入节点
void insertNode(ListNode* head, Stu student)
{
ListNode* pcur = createNode(student);
pcur->next = head->next;
head->next = pcur;
}
//删除节点
void deleteNode(ListNode* head, char* num, FILE* pf)
{
ListNode* prev = head;
ListNode* pcur = head->next;
while (pcur && strcmp(pcur->student.num, num))
{
if (!strcmp(pcur->student.num, num))
{
prev->next = pcur->next;
free(pcur);
return;
}
prev = prev->next;
pcur = pcur->next;
}
if (!pcur)
{
printf("数据不存在,删除失败n");
}
else
{
prev->next = pcur->next;
free(pcur);
}
}
//打印链表
void printList(ListNode* head)
{
ListNode* pcur = head->next;
printf("编号t姓名t成绩n");
while (pcur)
{
printf("%st%st%dn", pcur->student.num, pcur->student.name, pcur->student.grade);
pcur = pcur->next;
}
}
//查找节点
void seekNode(ListNode* head, char* num)
{
ListNode* pcur = head->next;
while (pcur && strcmp(pcur->student.num, num))
{
pcur = pcur->next;
}
if (pcur == NULL)
printf("数据不存在n");
else
{
printf("编号姓名成绩n");
printf("%st%st%dn", pcur->student.num, pcur->student.name, pcur->student.grade);
}
}
//修改节点
void modifyNode(ListNode* head, char* num, Stu student)
{
ListNode* pcur = head->next;
while (pcur && strcmp(pcur->student.num, num))
{
pcur = pcur->next;
}
if (pcur == NULL)
printf("要修改的数据不存在n");
else
{
pcur->student = student;
}
}
