目录
一、链表
二、单向链表与双向链表的区别
三、单链表的实现
四、双向(循环)链表的实现
链表所需要的功能:
初始化创建新节点插入删除查询链表的销毁(释放包括头结点在内的空间)链表的清空（释放除了头结点以外的空间）链表的优缺点：
优点：链表不需要初始化容量，可以任意加减元素，并且添加与删除元素十分快捷，只需要改变指针域指向的内容即可，内存利用率高，缺点：查找元素，需要通过遍历链表来查找，十分耗时适用于：需要频繁添加或者删除操作的场景单向链表与双向（循环）链表的区别：
在存储空间方面：单链表需要的存储空间比双向链表的要少，因为双向链表不仅保存有指向下一个节点的指针，还保存有指向上一个节点的指针，需要较大的空间来存储双向链表的指针域。在处理时间方面：双向链表的插入与删除操作比单链表的时间要快很多。在最末尾插入的时候，单链表需要找到需要插入位置的前一个节点，需要遍历整个链表，时间复杂度为O（n），而双向链表只需要head->tail,就可以得到最后一个节点的位置，然后就可以进行插入操作，时间复杂度为O（1）。在删除操作方面，单链表需要遍历到需要删除的节点的前一个节点，双向链表需要遍历到需要删除的节点，时间复杂度同为O(n)。一个提高单链表尾部插入效率的小方法：
定义一个指针tail，专门指向单链表的最末尾。如图所示注意：在处理单链表的插入的时候，优先处理新节点！
链表的定义 /*结构体*/ typedef int datatype; typedef struct node { datatype data; struct node *next; }node,*list; /*单链表的尾指针*/ struct node *tail; 链表的初始化 /* 创建头节点 */ list initNode() { list head = malloc(sizeof(node)); if(head != NULL) { head->next = NULL; } tail = head;//尾指针指向头结点 return head; } 创建新的节点 /* 创建新节点 */ list newNode(datatype n) { list new = malloc(sizeof(node)); if(new != NULL) { new->data = n; new->next = NULL; } return new; } 尾插法：插入节点 /* 尾插法，添加节点（包含尾指针） 插入需要注意：优先处理新节点、不先动旧的链表 */ bool insertNode_tail(list new) { /*判断新的节点是否为空*/ if (new == NULL) { printf("new point to NULL\n"); return false; } new->next = NULL; tail->next = new; tail = new;//tail指向最后一个节点 return true; } /* 不含有尾指针 */ bool insertNode_tail(list new,list head) { /*判断新的节点是否为空*/ if (new == NULL) { printf("new point to NULL\n"); return false; } list p = head; while(p->next != NULL)//搜索到最后的节点 { p = p->next; } new->next = NULL;//优先处理新节点 p->next = new; return true; } 删除节点 /* 删除节点：输入对应数字的负数形式，则会删除对应数字 */ bool delNode(datatype data, list head) { //数据处理 data = -data; list p = head; while(p->next != NULL)//找到要删除的节点的前一个节点 { if(p->next->data == data)break; p = p->next; } list del_p = p->next;//要删除的节点 p->next = del_p->next; free(del_p);//释放空间 tail = head;//将tail指针指向最末尾 while(tail->next != NULL) { tail = tail->next; } return true; } 查询链表 /* 查询节点 */ void showNode(list head) { list p = head->next; do { printf("%d\t", p->data); p = p->next; }while(p != NULL); printf("\n"); } 销毁与清空链表销毁链表：释放包括头节点的所有空间清空链表：释放除了头节点的其他节点空间 /* 销毁整个链表 */ void destoryAllNode(list head) { list p = head; list next_p = NULL; while(p != NULL) { next_p = p->next;//存储下一个节点指针 free(p);//释放当前节点 p = next_p;//指向销毁后的下一个节点 } } /* 清空链表 */ void clearNode(list head) { list p = head->next;//p指向第一个节点 list next_p = NULL; while(p != NULL) { next_p = p->next; free(p); p = next_p; } }
