1. 链表的种类
由上面的组合可以知道链表由2^3种类型
2. 最实用的两种链表类型
2.1 单向不带头不循环链表—（之前博客实现了）
2.2 双向带头循环链表
3. 实现双向带头循环链表
3.1 创建头节点
LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; }
3.2 实现双向循环功能—返回头指针
LTNode* ListInit() { LTNode* phead = BuyListNode(-1);//给头的data随便给个初始值 phead->next = phead; phead->prev = phead; return phead; }
3.3 尾插
void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; //ListInsert(phead, x); }
3.4 头插
void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* next = phead->next; phead newnode next phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; //ListInsert(phead->next, x); }
3.5 尾删
void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); //assert(!ListEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; //ListErase(phead->prev); }
3.6 头删
void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); ListErase(phead->next); }
4 实现两个重要接口函数
随机插入接口函数（ListInsert）可以实现头插、尾插，直接复用
随机删除接口函数（ListErase）可以实现头删、尾删，直接复用
4.1 随机插入
void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyListNode(x); // prve newnode pos prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
4.2 随机删除
void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }
5 顺序表和链表总结
