双向链表的实现及头尾插入删除

一.双向链表的初始化

ListNode* LTInit()
{ListNode* Phead = ListCreate(-1);Phead->next = Phead;Phead->prev = Phead;return Phead;
}

二.创建返回链表的头结点

ListNode* ListCreate(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fial");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;
}

三.双向链表销毁

void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != NULL){ListNode* next = cur->next;free(cur);cur = next;}free(pHead);//pHead = NULL;
}

四. 双向链表打印

void ListPrint(ListNode* pHead)
{assert(pHead);printf("哨兵位");ListNode* cur = pHead->next;while (cur != pHead){printf("%d >> ", cur->data);cur = cur->next;}printf("\n");
}

五.双向链表尾插

void ListPushBack(ListNode* pHead, LTDataType x)
{ListNode* tail = pHead->prev;ListNode* newnode = ListCreate(x);newnode->prev = tail;newnode->next = pHead;pHead->prev = newnode;tail->next = newnode;}

六. 双向链表尾删

void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);//ListNode* tail = pHead->prev;//ListNode* tailprev = tail->prev;//free(tail);//tailprev->next = pHead;//pHead->prev = tailprev;ListErase(pHead->prev);
}

七. 双向链表头插

void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = ListCreate(x);newnode->next = pHead->next;pHead->next->prev = newnode;newnode->prev = pHead;pHead->next = newnode;
}

八.双向链表头删

void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);//ListNode* first = pHead->next;//ListNode* second = first->next;//pHead->next = second;//second->prev = pHead;//free(first);//first = NULL;ListErase(pHead->next);}

九.双向链表的查找

ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

十.双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = ListCreate(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

十一. 双向链表删除pos位置的节点

void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posprev = pos->prev;posprev->next = posNext;posNext->prev = posprev;free(pos);pos = NULL;}