雙向循環(huán)鏈表demo

#include
#include

typedef struct node
{
int data; //"數(shù)據(jù)域" 保存數(shù)據(jù)元素
struct node * next; //保存下一個(gè)數(shù)據(jù)元素的地址
struct node * prev; //保存上一個(gè)數(shù)據(jù)元素的地址
}Node;

//創(chuàng)建表頭表示鏈表
Node* creatList()
{
Node * HeadNode = (Node )malloc(sizeof(Node));
//初始化，自己指向自己
HeadNode->next = HeadNode->prev = HeadNode;
return HeadNode;
}
//創(chuàng)建節(jié)點(diǎn)
Node creatNode(int data)
{
//C語(yǔ)言：malloc + free
//C++：new + delete
Node* newNode = (Node *)malloc(sizeof(Node));
//初始化
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
//遍歷鏈表
void printList(Node *headNode)
{
//雙向鏈表不光可以用 next 打印，也可以用 prev 進(jìn)行打印
//next指針打印：先進(jìn)后出
//prev指針打印：先進(jìn)先出
Node *p = headNode -> next;
while(p != headNode){
printf("%dt",p->data);
p = p -> next;
}
printf("n");
}

//插入節(jié)點(diǎn)：頭插法
void insertNodebyHead(Node *headNode,int data)
{
//創(chuàng)建插入的節(jié)點(diǎn)
Node newNode = creatNode(data);
//注意順序，賦值會(huì)改變指針指向，因此要先連后斷
/
headNode -> next = newnode;
newnode -> prev = headNode;
newnode -> next = headNode -> next;
headNode ->next->prev = newNode;
*/
// 從上面調(diào)整順序，得到下面
newNode -> prev = headNode;
newNode -> next = headNode -> next;
headNode ->next->prev = newNode;
headNode -> next = newNode;
}

//插入節(jié)點(diǎn)：尾插法
void insertNodebyTail(Node *headNode,int data)
{
//創(chuàng)建插入的節(jié)點(diǎn)
Node *newNode = creatNode(data);

//找到最后一個(gè)節(jié)點(diǎn)
Node *lastNode = headNode;
while(lastNode->next != headNode)
{
lastNode = lastNode->next;//往下走
}

//注意順序
headNode->prev = newNode;
newNode->next = headNode;
lastNode->next = newNode;
newNode->prev = lastNode;

}

//刪除節(jié)點(diǎn)
void deleteNodebyAppoin(Node *headNode,int posData)
{
// posNode 想要?jiǎng)h除的節(jié)點(diǎn)，從第一個(gè)節(jié)點(diǎn)開始遍歷
// posNodeFront 想要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
Node *posNode = headNode -> next;
Node *posNodeFront = headNode;

if(posNode == NULL)
printf("鏈表為空，無(wú)法刪除");
else{
while(posNode->data != posData)
{
//兩個(gè)都往后移，跟著 posNodeFront 走
posNodeFront = posNode;
posNode = posNodeFront->next;
if (posNode->next == headNode)
{
printf("沒有找到，無(wú)法刪除");
return;
}
}
//找到后開始刪除
posNodeFront->next = posNode->next;
posNode->next->prev = posNodeFront;
free(posNode);
}
}

int main()
{
Node* List = creatList();

insertNodebyHead(List,1);
insertNodebyHead(List,2);
insertNodebyHead(List,3);
printList(List);

insertNodebyTail(List,0);
printList(List);

deleteNodebyAppoin(List,2);
printList(List);

return 0;
}

結(jié)果：

雙鏈表的創(chuàng)建、遍歷和單鏈表差不多，只是頭插法、尾插法、刪除操作多了幾個(gè)步驟。