3.4 双向链表的实现
带头双向循环链表增删查改实现
定义类型和结构体
typedef int LTdatatype; typedef struct LTlistnode { struct LTlistnode* prev; struct LTlistnode* next; LTdatatype data; }LTnode;
链表初始化
//链表初始化 LTnode* LTnodeinit(); LTnode* LTnodeinit() { LTnode* guard = (LTnode*)malloc(sizeof(LTnode)); if (guard == NULL) { perror("LTnodeinit fail"); return; } guard->next = guard; guard->prev = guard; return guard; }
链表尾插
与单链表类似，插入数据，创建一个新的节点，由于新节点的创建不止出现一次，为了方便，将其独立为函数
LTnode* Buynewnode(LTdatatype x) { LTnode* newnode = (LTnode*)malloc(sizeof(LTnode)); if (newnode == NULL) { perror("Buynewnode fail"); return; } newnode->prev = NULL; newnode->next = NULL; newnode->data = x; return newnode; }
尾插
//尾插 void LTnodepushback(LTnode* phead,LTdatatype x); void LTnodepushback(LTnode* phead,LTdatatype x) { assert(phead); LTnode* newnode = Buynewnode(x); LTnode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
头插
//头插 void LTnodepushfront(LTnode* phead, LTdatatype x); void LTnodepushfront(LTnode* phead, LTdatatype x) { assert(phead); LTnode* newnode = Buynewnode(x); LTnode* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
计算链表长度
这里使用size_t较为合适，如果使用char类型来记录链表长度，当链表长度超过128时，便会出错
//计算链表长度 size_t LTsize(LTnode* phead); size_t LTsize(LTnode* phead) { assert(phead); LTnode* cur = phead->next; size_t n = 0; while (cur != phead) { n++; cur = cur->next; } return n; }
判断链表是否为空
//判断链表是否为空 bool LTnodeempty(LTnode* phead); bool LTnodeempty(LTnode* phead) { assert(phead); //链表为空返回1，不为空返回0 return phead->next == phead; }
尾删
//尾删 void LTnodepopback(LTnode* phead); void LTnodepopback(LTnode* phead) { assert(phead); //链表不为空返回值为零，取反为真 assert(!LTnodeempty(phead)); LTnode* tail = phead->prev; LTnode* prev = tail->prev; phead->prev = prev; prev->next = phead; free(tail); tail=NULL; }
头删
//头删 void LTnodepopfront(LTnode* phead); void LTnodepopfront(LTnode* phead) { assert(phead); //链表不为空返回值为零，取反为真 assert(!LTnodeempty(phead)); LTnode* prev = phead->next; LTnode* next = prev->next; phead->next = next; next->prev = phead; free(prev); prev=NULL; }
链表查找
//链表查找 LTnode* LTnodefind(LTnode* phead,LTdatatype x); LTnode* LTnodefind(LTnode* phead,LTdatatype x) { assert(phead); LTnode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
链表插入，在pos前插入节点
//在pos前插入节点 void LTnodeinsert(LTnode* pos, LTdatatype x); void LTnodeinsert(LTnode* pos, LTdatatype x) { assert(pos); LTnode* prev = pos->prev; LTnode* newnode = Buynewnode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
删除pos位置的节点
//删除节点 void LTnodeerase(LTnode* pos); void LTnodeerase(LTnode* pos) { assert(pos); LTnode* prev = pos->prev; LTnode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
打印链表
//打印链表 void LTnodeprint(LTnode* phead); void LTnodeprint(LTnode* phead) { assert(phead); printf("phead<=>"); LTnode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
销毁链表
//销毁链表 void LTnodedestory(LTnode* phead); void LTnodedestory(LTnode* phead) { assert(phead); LTnode* cur = phead->next; while (cur != NULL) { LTnode* next = cur->next; free(cur); cur = next; } free(phead); }
4. 顺序表和链表的区别和联系
| 不同的 | 顺序表 | 链表 |
| 存储空间 | 物理上一定连续 | 逻辑上连续，物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插入或删除元素 | 可能需要挪动数据，效率低 | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够进行扩容 | 没有容量的概念 |
| 应用 | 元素高效存储+频繁访问 | 任意位置插入或删除 |
顺序表优点：
尾插尾删效率高
随机访问（下标访问）
顺序表缺点：
头部和中部插入或删除效率低 O(N)
扩容时，存在性能消耗和空间浪费
链表优点：
任意位置插入或删除效率高 O(1)
根据需求申请释放
链表缺点：
不支持随机访问
