1.为什么需要链表？

链表是一种灵活的数据结构，它允许在内存中动态地存储和操作元素。以下是一些需要使用链表的原因：

(资料图)

1. 动态数组的缺点：数组的大小是在程序运行时固定的，如果需要添加或删除元素，就需要重新分配内存并复制数据。这会导致大量的内存浪费和性能问题。而链表可以动态地调整大小，只需要增加或删除节点即可。2. 插入和删除操作的效率：在链表中插入和删除元素比在数组中高效得多。因为链表中的节点不需要移动整个数组，只需要修改指针指向即可。这使得链表在处理大量数据时具有更高的效率。3. 随机访问的效率：链表的随机访问效率较低，因为需要从头结点开始遍历整个链表才能找到目标元素。但是，链表可以通过哈希表等数据结构来优化随机访问效率。4. 适用场景：链表适用于那些需要频繁插入和删除元素的场景，例如缓存、队列、栈等数据结构。此外，链表还可以用于实现一些高级算法，如广度优先搜索(BFS)和深度优先搜索(DFS)。

总之，链表是一种非常有用的数据结构，它可以在某些情况下提供比数组更好的性能和灵活性。

2.链表基本概念

链表(Linked List)是一种数据结构，它允许在单个内存位置中存储多个元素。与数组不同，链表中的元素不是连续存储的，而是通过指针相互连接。链表的主要优点是动态地添加和删除元素，而不需要像数组那样需要预先分配固定大小的空间。

链表的基本概念包括：

1. 头结点(Head Node):链表的第一个节点通常被称为头结点。头结点本身不存储实际的数据，它仅用于指向链表的下一个节点。2. 尾节点(Tail Node):链表的最后一个节点通常被称为尾节点。尾节点同样不存储实际的数据，它仅用于指向链表的第一个节点的前一个节点。3. 指针(Pointer):指针是一个变量，它存储另一个变量的地址。在链表中，指针用于连接各个节点。每个节点包含一个指向下一个节点的指针，这样可以形成一个单向链。4. 访问(Accessing):要访问链表中的某个元素，首先需要找到该元素所在的节点。然后，可以通过解引用指针来访问该节点的数据部分。例如，如果有一个指向头结点的指针p,可以使用*p来访问头结点的数据部分。5. 插入(Insertion):在链表中插入一个新元素时，需要先找到合适的位置。可以将新元素插入到头结点之后、尾节点之前的位置，或者尾节点之后的位置。具体操作取决于所选位置是否为空闲状态。插入操作可能涉及修改指针的指向，以便将新元素链接到正确的位置。6. 删除(Deletion):从链表中删除一个元素时，需要找到该元素所在的节点。然后，可以将该节点的指针设置为其后继节点的指针，从而删除该节点。删除操作可能涉及修改指针的指向，以便更新整个链表的结构。

3.链表的形成方式

链表是由包含数据的多个结点前后连接形成的链式结构1.结点：每一个结点是一小片连续的、存放了数据的内存空间，是形成链表的基本单元2.结点的构成：每个结点由两方面内容组成：（1）数据域：真正要处理的数据，可以是单个基本类型的数据，也可以是多个不同类型的数据共同构成。（2）指针域：一般用来存放另一结点的首地址，即指针域是用来指向另一个结点的（或者赋值为NULL，即不指向任何结点。）

4.简单链表的形成

链表正是通过指针域将各个结点有机地联接成一个整体。设有A、B、C、D四个结点，按下图形成链表注意（1）head：设计的头部指针, 指向链表头结点（2）NULL：尾部结点的指针域为空，不指向任何结点。（3）前一节点的指针域存放下一结点的首地址

节点结构体：

//节点结构体struct LinkNode{//数据域void * data;//指针域struct LinkNode * next;};

链表结构体

//链表结构体struct LList{//头节点struct LinkNode pHeader;//链表长度int m_size;};

//不让用户直接访问LListtypedef void * LinkList;

————————————————版权声明：本文为CSDN博主「刘鑫磊up」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/liu17234050/article/details/110502629

5.链表的操作

5.1初始化链表

LinkList init_LinkList(){ struct LList * myList = malloc(sizeof(struct LList)); if (myList == NULL) { return NULL; } myList->pHeader.data = NULL; myList->pHeader.next = NULL; myList->m_size = 0; return myList;}//初始化链表LinkList mylist = init_LinkList();

5.2链表的插入操作

//需要做插入操作的链表是list，插入位置是pos，插入的数据是datavoid insert_LinkList(LinkList list, int pos, void * data)if (list == NULL){return;}if ( data == NULL){return;}//将list还原成 struct LList数据类型struct LList * myList = list;if (pos < 0 || pos > myList->m_size){//无效位置 强制做尾插pos = myList->m_size;}//找到插入节点的前驱节点位置struct LinkNode * pCurrent = &myList->pHeader;for (int i = 0; i < pos;i++){pCurrent = pCurrent->next;}//pCurrent 要插入节点的前驱//创建新节点    struct LinkNode * newNode = malloc(sizeof(struct LinkNode));newNode->data = data;newNode->next = NULL;//建立节点关系newNode->next = pCurrent->next;pCurrent->next = newNode;//更新链表长度myList->m_size++;}//准备数据struct Person p1 = { "亚瑟", 18 };struct Person p2 = { "妲己", 20 };struct Person p3 = { "安琪拉", 19 };struct Person p4 = { "凯", 21 };struct Person p5 = { "孙悟空", 999 };struct Person p6 = { "李白", 999 };//插入数据insert_LinkList(mylist, 0, &p1);insert_LinkList(mylist, 0, &p2);insert_LinkList(mylist, -1, &p3);insert_LinkList(mylist, 0, &p4);insert_LinkList(mylist, 1, &p5);insert_LinkList(mylist, 0, &p6);

5.3链表的遍历操作

//遍历链表void foreach_LinkList(LinkList list, void(*myForeach)(void *)){if (list ==NULL){return;}struct LList * mylist = list;struct LinkNode* pCurrent = mylist->pHeader.next;for (int i = 0; i < mylist->m_size;i++){myForeach(pCurrent->data);pCurrent = pCurrent->next;}}//遍历struct Person{char name[64];int age;};void myPrintPerson(void * data){struct Person * p = data;printf("姓名：%s  年龄：%d\n", p->name, p->age);}foreach_LinkList(mylist, myPrintPerson);

5.4链表的删除操作

//删除链表  按位置void removeByPos_LinkList(LinkList list, int pos){if ( list == NULL){return;}struct LList * mylist = list;if (pos < 0 || pos > mylist->m_size - 1){return;}//找到待删除节点的前驱节点struct LinkNode * pCurrent = &mylist->pHeader;for (int i = 0; i < pos;i++){pCurrent = pCurrent->next;}//记录待删除的节点struct LinkNode * pDel = pCurrent->next;//重新建立节点关系pCurrent->next = pDel->next;free(pDel);pDel = NULL;//更新链表长度mylist->m_size--;}

//按照值删除链表void removeByValue_LinkList(LinkList list, void* data, int(*myCompare)(void*, void*)){if (list == NULL){return;}if (data == NULL){return;}struct LList* mylist = list;//创建两个辅助指针struct LinkNode* pPrev = &mylist->pHeader;struct LinkNode* pCurrent = pPrev->next;for (int i = 0; i < mylist->m_size; i++){//pCurrent->data  data 将两个指针比较利用回调 交给用户if (myCompare(pCurrent->data, data)){pPrev->next = pCurrent->next;free(pCurrent);pCurrent = NULL;mylist->m_size--;break;}//没找到 辅助指针后移pPrev = pCurrent;pCurrent = pCurrent->next;}}

5.5清空链表

//清空链表void clear_LinkList(LinkList list){if (list == NULL){return;}struct LList* mylist = list;struct LinkNode* pCurrent = mylist->pHeader.next;for (int i = 0; i < mylist->m_size; i++){struct LinkNode* pNext = pCurrent->next;free(pCurrent);pCurrent = pNext;}mylist->pHeader.next = NULL;mylist->m_size = 0;}

5.6返回链表长度

//返回链表长度int  size_LinkList(LinkList list){if (list == NULL){return -1;}struct LList* mylist = list;return mylist->m_size;}

5.7销毁链表

//销毁链表void destroy_Linklist(LinkList list){if (list == NULL){return;}//清空链表clear_LinkList(list);free(list);list = NULL;}

5.8完整代码

#define _CRT_SECURE_NO_WARNINGS#include#include#include//节点结构体struct LinkNode{//数据域void* data;//指针域struct LinkNode* next;};//链表结构struct LList{//头结点struct LinkNode pHeader;//链表长度int m_size;};typedef void* LinkList;//初始化链表LinkList init_LinkList(){struct LList* myList = malloc(sizeof(struct LList));if (myList == NULL){return NULL;}myList->pHeader.data = NULL;myList->pHeader.next = NULL;myList->m_size = 0;return myList;}//插入链表void insert_LinkList(LinkList list, int pos, void* data){if (list == NULL){return;}if (data == NULL){return;}//将list还原成struct LList数据类型struct LList* myList = list;if (pos < 0 || pos > myList->m_size){//无效位置 强制做尾插pos = myList->m_size;}//找到插入节点的前驱节点位置struct LinkNode* pCurrent = &myList->pHeader;for (int i = 0; i < pos; i++){pCurrent = pCurrent->next;//通过循环找到待插入位置的前驱节点}//pCurrent要插入节点的前驱//创建新节点struct LinkNode* newNode = malloc(sizeof(struct LinkNode));newNode->data = data;newNode->next = NULL;//建立节点关系newNode->next = pCurrent->next;pCurrent->next = newNode;//更新链表长度myList->m_size++;}//遍历链表void foreach_LinkList(LinkList list, void(* myForeach)(void *)){if (list == NULL){return;}struct LList* mylist = list;struct LinkNode* pCurrent = mylist->pHeader.next;//头结点数据域没必要访问for (int i = 0; i < mylist->m_size; i++){myForeach(pCurrent->data);pCurrent = pCurrent->next;}}//测试struct Person{char name[64];int age;};void myPrintPerson(void* data){struct Person* p = data;printf("姓名：%s，年龄：%d\n", p->name, p->age);}void test01(){//准备数据struct Person p1 = { "亚瑟", 18 };struct Person p2 = { "妲己", 20 };struct Person p3 = { "安其拉", 19 };struct Person p4 = { "凯", 21 };struct Person p5 = { "孙悟空", 899 };struct Person p6 = { "李白", 899 };//初始化链表LinkList mylist = init_LinkList();//插入数据insertinsert_LinkList(mylist, 0, &p1);insert_LinkList(mylist, 0, &p2);insert_LinkList(mylist, -1, &p3);insert_LinkList(mylist, 0, &p4);insert_LinkList(mylist, 1, &p5);insert_LinkList(mylist, 0, &p6);//李白 凯 孙悟空 妲己 亚瑟 安其拉//遍历foreach_LinkList(mylist, myPrintPerson);}int main(){test01();system("pause");return EXIT_SUCCESS;}

参考资料来源：

黑马程序员