文章目录
带头结点的双向循环链表和单链表的区别
相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是O(1),也不需要增容,浪费空间换取时间,但是需要申请和释放空间。
面试题:写一个双向链表
思路
主要实现函数ListInsert,ListFind,ListErase,其他的函数如头插,尾插,头删,尾删等函数可以用以上几个关键的函数代替实现。
代码实现
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* node = (ListNode*)malloc(sizeof(ListNode*));
node->val = x;
ListNode* next = head->next;
node->next = next;
head->next = node;
next->prev = node;
node->prev = head;
}
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != head);
ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
}
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != head);
ListNode* node = phead->next;
ListNode* next = node->next;
head->next = next;
next->prev = head;
free(node);
}
void ListInsert(ListNode* phead, LTDataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
ListNode posPrev = pos->prev;
posPrev->next = newNode;
newNode->next = pos;
pos->prev = newNode;
newNode->prev = posPrev;
}
void ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
retrun cur;
}
cur = cur->next;
}
return NULL;
}
void ListErase(ListNode* pos)
{
assert(pos);
//pos不能是phead,否则头结点没了
//assert(pos != phead);
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
void ListDestory(ListNode* phead)
{
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
ListErase(cur);
cur = next;
}
free(phead);0
}