带头双向循环链表的实现

1.结构体的创建以及类型重定义

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;

2.链表的初始化

这个函数用于创建节点，后面还会用到。

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;
}

---

链表的初始化

LTNode* ListInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

3.链表的头插以及尾插

头插

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* next = phead->next;phead->next = newnode;newnode->next = next;next->prev = newnode;newnode->prev = phead;
}

---

尾插

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->next = phead;phead->prev = newnode;newnode->prev = tail;
}

4.链表的打印

void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

5.链表的头删以及尾删

头删

void ListPopFront(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));LTNode* front = phead->next;LTNode* frontNext = phead->next->next;free(front);phead->next = frontNext;frontNext->prev = phead;
}

---

尾删

void ListPopBack(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = phead->prev->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}

注意：链表只剩下一个头的时候就不可以再删除了，所以需要多加

assert(ListEmpty(phead));

进行断言判断。

ListEmpty函数如下：

bool ListEmpty(LTNode* phead)
{assert(phead);return phead->next != phead;
}

6.在pos位置之前插入

void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->next = pos;pos->prev = newnode;newnode->prev = prev;
}

7.删除pos位置的节点

void ListErase(LTNode* pos)
{assert(pos);LTNode* next = pos->next;LTNode* prev = pos->prev;free(pos);prev->next = next;next->prev = prev;
}

8.头插尾插的简化以及头删尾删的简化

由于链表的头节点以及尾节点都可以归类为pos任意位置的节点，所以可以利用6和7的函数来进行简化，如下：

头插

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

---

尾插

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}

---

头删

void ListPopFront(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));ListErase(phead->next);
}

---

尾删

void ListPopBack(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));ListErase(phead->prev);
}

9.链表节点的数量计算

LTDataType ListSize(LTNode* phead)
{assert(phead);LTDataType size = 0;LTNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}

这个链表节点计数量计算的时间复杂度为O(N)，如果要实现O(1)的时间复杂度（与链表节点的插入和删除的时间复杂度保持一致）的话，那么可以这么写：

struct List()
{LTNode* phead;int size;
}

这样新定义了一个结构体后，前面的函数都要改一改了，所以可以直接写一个函数来计算链表的节点数量。

注意：不要用头节点来存储链表的节点数量，因为如果链表的节点数据类型不是int而是char的话，那么最高只能存储到127这个数了， 链表的长度可能要远远大于这个数。

10.链表的销毁

void ListDestroy(LTNode* phead)
{assert(phead);while (phead->next != phead){ListErase(phead->next);}free(phead);
}

---

顺序表与链表的比较：

顺序表的优点：通过下标可以随机访问任意一个数据，cpu高速缓存命中率高

顺序表的缺点：头部或者中间插入数据效率低下，扩容后可能存在一定的空间浪费

---

链表的优点：数据的插入和删除时间复杂度为O(1), 按需申请释放

链表的缺点：不能通过下标来进行访问，查询任意数据时时间复杂度为O(N)。