雙向鏈表實質(zhì)上是在單向鏈表的基礎(chǔ)上加上了一個指針指向后面地址

單向鏈表請參考http://t.csdn.cn/3Gxk9

物理結(jié)構(gòu)
首先我們看一下兩種鏈表的物理結(jié)構(gòu)

我們可以看到：雙向在單向基礎(chǔ)上加入了一個指向上一個地址的指針，如此操作我們便可以向數(shù)組一樣操作了，而且尾插也更加方便，復(fù)雜度從原來的O(n)變?yōu)镺(1)，并且查找也可以運用二分查找。

一些基礎(chǔ)操作

頭插

頭刪

尾插

尾刪

接下來我們來進行代碼實現(xiàn)

頭文件以及要實現(xiàn)的函數(shù)聲明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int LTDataType;
typedef struct Slist
{LTDataType val;struct Slist* next;struct Slist* random;
}ListNode;// 創(chuàng)建返回鏈表的頭結(jié)點.
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos);
// 擴容
ListNode* my_malloc(LTDataType x);

函數(shù)實現(xiàn)

#include "dslist.h"ListNode* my_malloc(LTDataType x)//由于后續(xù)要頻繁使用到擴容，所以我們直接創(chuàng)一個擴容函數(shù)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->val = x;newnode->random = NULL;newnode->next = NULL;return newnode;
}ListNode* ListCreate()  //創(chuàng)建一個雙向鏈表
{ListNode* head = (ListNode * )malloc(sizeof(ListNode));head->val = -1;    head->next= NULL;head->random = NULL;return head;
}void ListDestory(ListNode* pHead)  //銷毀這個雙線鏈表
{while (pHead)//將每個節(jié)點都free掉{ListNode* mid = pHead;pHead = pHead->next;mid->next = NULL;free(mid);}
}void ListPrint(ListNode* pHead)   //打印雙向鏈表
{ListNode* mid = pHead;while (mid)  //循環(huán)一個一個打印{printf("%d->", mid->val);mid = mid->next;}printf("NULL");
}void ListPushBack(ListNode* pHead, LTDataType x)    //尾插
{ListNode* newnode = my_malloc(x);if (pHead->next == NULL)       //判斷鏈表是否為空，如果為空則只需要插入一個。{newnode->random = pHead;    //由于循環(huán)鏈表，需要將頭節(jié)點的random指向插入元素  newnode->next = NULL;pHead->next = newnode;pHead->random = newnode;}else             //如果不為空則正常尾插{ListNode* mid = pHead->random;    //由于雙向  頭節(jié)點的random指針直接指向尾部，所以不需要循環(huán)找尾mid->next = newnode;newnode->random = mid;pHead->random = newnode;}
}void ListPopBack(ListNode* pHead)   //尾刪
{if (pHead->next == NULL)   //判斷是否為空{return;}else{ListNode* mid = pHead->random;   //正常尾刪pHead->random = mid->random;mid->random->next = NULL;free(mid);}
}void ListPushFront(ListNode* pHead, LTDataType x)    //頭插
{if (pHead->next == NULL) //如果為空  則相當(dāng)于尾插  調(diào)用尾插函數(shù)即可{ListPushBack(pHead, x);}else    //不為空正常頭插{ListNode* nownode = my_malloc(x);   nownode->next = pHead->next;     //將nownode  的next指向  phead的nextnownode->random = pHead;     //nownode的random指向  pheadpHead->next = nownode;          //phead的next指向nownodenownode->next->random = nownode;}
}void ListPopFront(ListNode* pHead)    //頭刪
{if (pHead->next == NULL){return;}else{if (pHead->next == pHead->random){ListPopBack(pHead);}else{ListNode* mid = pHead->next;pHead->next = mid->next;mid->next->random = pHead;free(mid);}}
}ListNode* ListFind(ListNode* pHead, LTDataType x)   //尋找元素
{ListNode* left = pHead->next;ListNode* right = pHead->random;while (left && right)    //二分查找{if (left->val == x){return left;}if (right->val == x){return right;}left = left->next;right = right->random;}return NULL;
}void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = my_malloc(x);ListNode* mid = pos->random;mid->next = newnode;pos->random = newnode;newnode->next = pos;
}void ListErase(ListNode* pos)
{ListNode* next = pos->next;ListNode* last = pos->random;next->random = last;last->next = next;free(pos);
}

有什么疑惑歡迎大家留言。