双向链表的复杂操作、内核链表、栈

双向链表的复杂操作

一、插入

1、头插法

int HeadInsertDouList(LinkNode *pHead, DataType TmpData)
{LinkNode *pNewNode = NULL;pNewNode = malloc(sizeof(LinkNode));if (NULL == pNewNode){return -1;}pNewNode->Data = TmpData;pNewNode->pNext = pHead->pNext;pNewNode->pPre = pHead;pHead->pNext = pNewNode;if (pNewNode->pNext != NULL){pNewNode->pNext->pPre = pNewNode;}return 0;
}

2、尾插法

int TailInsertDouList(LinkNode *pHead, DataType TmpData)
{LinkNode *pLastNode = NULL;LinkNode *pTmpNode = NULL;pLastNode = pHead;while (pLastNode->pNext != NULL){pLastNode = pLastNode->pNext;}pTmpNode = malloc(sizeof(LinkNode));if (NULL == pTmpNode){return -1;}pTmpNode->Data = TmpData;pTmpNode->pNext = NULL;pTmpNode->pPre = pLastNode;pLastNode->pNext = pTmpNode;return 0;
}

二、删除

int DeleteDouList(LinkNode *pHead, DataType TmpData)
{LinkNode *pTmpNode = NULL;LinkNode *pNextNode = NULL;int cnt = 0;pTmpNode = pHead->pNext;while (pTmpNode != NULL){if (pTmpNode->Data == TmpData){pNextNode = pTmpNode->pNext;pTmpNode->pPre->pNext = pTmpNode->pNext;if (pTmpNode->pNext != NULL){pTmpNode->pNext->pPre = pTmpNode->pPre;}      free(pTmpNode);pTmpNode = pNextNode;cnt++;}else {pTmpNode = pTmpNode->pNext;}}return cnt;
}

其余的一些操作，比如正向遍历，反向遍历，查找，替换，销毁的代码与单向链表没有什么区别 

内核链表

一、插入

1、头插法

list_add (struct list_head *new, struct list_head *head)
{new->prev = head;new->next = head->next;new->prev->next = new;new->next->prev = new;
}

2、尾插法

list_add_tail (struct list_head *new, struct list_head *head)
{new->next = head;new->prev = head->prev;new->prev->next = new;new->next->prev = new;
}

二、删除 

list_del (struct list_head *old)
{old->prev->next = old->next;old->next->prev = old->prev;old->next = (void *)0xbabebabe;old->prev = (void *)0xcafecafe;
}

三、遍历 

#define list_for_each(pos, head)                                        \for (pos = (head)->next; pos != (head); pos = pos->next)

栈 

一、原则

FILO：先进后出，后进先出 

二、概念

1、栈顶：允许入栈出栈的一端称为栈顶
2、栈底：不允许入栈和出栈的一端称为栈底
3、入栈（压栈）：将数据元素放入栈顶
4、出栈（弹栈）：将数据元素从栈顶位置取出

三、分类

1、空增栈
2、空减栈
3、满增栈
4、满减栈

栈的基本操作也都可以通过内核链表实现