雙向清單
雙向連結清單是每個結點除後繼指針外還有一個前驅指針。和單連結清單類同，雙向連結清單也有帶頭結點結構和不帶頭結點結構兩種，帶頭結點的雙向連結清單更為常用；另外，雙向連結清單也可以有循環和非循環兩種結構，循環結構的雙向連結清單更為常用。
雙向連結清單相當于兩個單向循環連結清單,雙連結清單節點結構如下圖示：
雙連結清單節點比單連結清單多一個前驅指針域。
如下圖是帶頭結點的雙向循環連結清單的圖示結構。雙向循環連結清單的next和prior各自構成自己的單向循環連結清單：
在雙向連結清單中，有如下關系：設對象引用p表示雙向連結清單中的第i個結點，則p->next表示第i+1個結點，p->next->prior仍表示第i個結點，即p->next->prior == p；同樣地，p->prior表示第i-1個結點，p->prior->next仍表示第i個結點，即p->prior->next == p。下圖是雙向連結清單上述關系的圖示：
雙向循環連結清單的插入過程：
下圖中的指針p表示要插入結點的位置，s表示要插入的結點，①、②、③、④表示實作插入過程的步驟：
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
循環雙向連結清單的删除過程：
下圖中的指針p表示要插入結點的位置，①、②表示實作删除過程的步驟：
p->prior->next = p->next;
p->next->prior = p->prior;
下面用C++ 代碼實作雙向連結清單：
頭檔案：
#include<iostream>
using namespace std;
#ifndef TT_DU_LINK_LIST
#define TT_DU_LINK_LIST
#define TT_OK 1
#define TT_ERROR 0
namespace tt
{
class DuLinkList
{
public:
typedef int ElemType;
typedef void Status;
public:
struct DulNode
{
ElemType m_data; //資料域
DulNode *m_prior; //指向前驅結點的指針
DulNode *m_next; //指向後繼結點的指針
};
public:
DuLinkList();
~DuLinkList();
ElemType insertAt(ElemType i, ElemType elem);
ElemType removeAt(ElemType i, ElemType &elemOut);
ElemType getAt(ElemType i, ElemType &elemOut);
ElemType getIndexElemAt(ElemType &i, ElemType elemOut);//查找與elem相等的元素，傳回第一個與elem相等元素在連結清單中的序号
ElemType getLength()const;
ElemType isEmpty()const;
ElemType destroy();
ElemType clear();
Status show();
Status traverseBack();
ElemType priorElemAt(ElemType cur_e, ElemType &pri_e);//若cur_e是連結清單的資料元素，且不是第一個，則用pre_e傳回它的前驅
ElemType nextElemAt(ElemType cur_e, ElemType &Nex_e); //若cur_e是連結清單的資料元素,且不是最後一個,則用next_e傳回它的後繼，
Status createTail(ElemType *datas, ElemType length);//建立長度為length的連結清單，資料通過數組指定，這裡采用尾插法
private:
DulNode *m_heap;
};
inline DuLinkList::ElemType DuLinkList::isEmpty()const
{
return ((m_heap->m_next == m_heap) && (m_heap->m_prior == m_heap));
}
}
#endif //TT_DU_LINK_LIST
源檔案：
#include"MyDuLinkList.h"
namespace tt
{
DuLinkList::DuLinkList()
{
m_heap = new DulNode;
if (!m_heap)
{
cout << "錯誤，記憶體配置設定失敗！" << endl;
system("pause");
exit(0);
}
/*m_heap->m_next = m_heap;
m_heap->m_prior = m_heap;*/
m_heap->m_next = m_heap->m_prior = m_heap;
cout << "\n********************雙向的循環連結清單初始化成功！************************" << endl;
}
DuLinkList::~DuLinkList()
{
this->destroy();
}
DuLinkList::Status DuLinkList::createTail(ElemType *datas, ElemType length)//建立長度為length的連結清單，資料通過數組指定，這裡采用尾插法
{
DulNode *m = m_heap;
for (int i = 0; i < length; ++i)
{
DulNode *p = new DulNode;
if (!p)
{
cout << "錯誤，無法配置設定記憶體，建立連結清單失敗！" << endl;
system("pause");
exit(0);
}
p->m_data = datas[i];
m->m_next = p; //首先建立第一個節點的時候，頭結點的後繼節點是p
p->m_prior = m; //p的前驅節點是頭結點
p->m_next = m_heap; //然後第一個節點的後繼變成頭結點
m_heap->m_prior = p; //那麼頭結點的前驅變成p， 這樣就會形成一個首尾相接的雙向循環連結清單
m = p; //最後把第一個節點變成m， 就這樣按以上步驟循環
}
}
DuLinkList::ElemType DuLinkList::insertAt(ElemType i, ElemType elem)
{
if ((i < 1) || (i > getLength() + 1))
{
return TT_ERROR;
}
DulNode* p = m_heap; //p指向頭結點
int j = 1;
while (j < i)
{
p = p->m_next;
++j;
}
DulNode *s = new DulNode;
s->m_data = elem; //把要存儲的資料放入資料域中
s->m_prior = p; //首先把p變成s的前驅結點
s->m_next = p->m_next; //在p的後繼節點變成s的後繼節點
p->m_next->m_prior = s; //把s變成p的後繼節點的前驅
p->m_next = s; //p的後繼節點是s
return TT_OK;
}
DuLinkList::ElemType DuLinkList::removeAt(ElemType i, ElemType &elemOut)
{
if ((i < 1) || (i >getLength()))
{
return TT_ERROR;
}
DulNode* p = m_heap; //p指向頭結點
int j = 1;
while (j <= i)
{
p = p->m_next;
j++;
}
elemOut = p->m_data;
p->m_prior->m_next = p->m_next; //把p的後繼節點變成p的前驅結點的後繼節點
p->m_next->m_prior = p->m_prior; //把p的前驅結點變成p的後繼節點的前驅結點
delete p; //釋放節點的記憶體
return TT_OK;
}
DuLinkList::ElemType DuLinkList::getAt(ElemType i, ElemType &elemOut)
{
if (i > getLength()) // 判斷i的位置是否超過連結清單的長度
{
return TT_ERROR;
}
DulNode* q = m_heap->m_next; //讓q指向連結清單的第一個節點
int j = 1;
while ((q != m_heap) && (j < i)) //如果q的後繼不是m_heap， 目前位置j=1小于要查找的位置，循環繼續
{ //删除第一個元素時，退出循環
q = q->m_next;
++j;
}
if (!(q != m_heap) || (j > i)) //删除第一個元素時， j并沒有比i大， q的後繼不是m_heap取逆， 直接退出循環
{
return TT_ERROR;
}
elemOut = q->m_data;
return TT_OK;
}
DuLinkList::ElemType DuLinkList::getIndexElemAt(ElemType &i, ElemType elemOut) //查找與elem相等的元素，傳回第一個與elem相等元素在連結清單中的序号
{
DulNode *p = m_heap->m_next; //從第一個結點開始周遊
int searchLocate = 1;
while ((p != m_heap) && (p->m_data != elemOut)) //p未到表頭時， p的指針域不等于要查找的元素
{
++searchLocate;
p = p->m_next;
}
if (!(p != m_heap))
{
return TT_ERROR;
}
i = searchLocate; //傳回要查找的元素的位置的序号
return TT_OK;
}
DuLinkList::ElemType DuLinkList::getLength()const
{
DulNode *p = m_heap->m_next; //p指向第一個結點
int i = 0;
while (p != m_heap) //p未到表頭時
{
++i;
p = p->m_next;
}
return i;
}
DuLinkList::ElemType DuLinkList::destroy()
{
DulNode *p = m_heap->m_next; //p指向第一個結點
while (p != m_heap) //p沒到表頭
{
DulNode *q = p->m_next; //第一次循環，把第二個元素變成q
delete p; //第一次循環， 釋放第一個元素
p = q; //第一次循環， 把第二個元素變成p， 那麼現在p就是第一個元素
}
delete m_heap; //所有元素删除完後， 因為上面是從第一個節點開始删除的， 頭結點沒有删除， 所有這個要删除頭結點
m_heap = nullptr;
return TT_OK;
}
DuLinkList::ElemType DuLinkList::clear()
{
DulNode *p = m_heap->m_next; //p指向第一個結點
while (p != m_heap) //p沒到表頭
{
DulNode *q = p->m_next;
delete p;
p = q;
}
m_heap->m_next = m_heap->m_prior = m_heap; //頭結點的兩個指針域均指向自身
return TT_OK;
}
DuLinkList::Status DuLinkList::show()
{
if (isEmpty())
{
cout << "目前的連結清單沒有元素，無法顯示！" << endl;
}
else
{
DulNode *p = m_heap->m_next; //p指向第一個結點
int temp(0); //用來顯示連結清單中的個數
cout << "輸出雙向循環連結清單中的所有元素：";
while (p != m_heap) //p未到表頭
{
++temp;
cout << (p->m_data) << " ";
p = p->m_next;
}
cout << "\n目前雙向循環連結清單中的元數個數為：" << temp << endl;
}
}
DuLinkList::Status DuLinkList::traverseBack() //逆序輸對外連結表的所有元素
{
if (isEmpty())
{
cout << "目前的連結清單沒有元素，無法顯示！" << endl;
}
else
{
DulNode *m = m_heap->m_prior; //把m指向最後一個元素
cout << "逆序輸出雙向連結清單中的所有元素：";
while (m != m_heap)
{
cout << (m->m_data) << " ";
m = m->m_prior; //輸出元素後，m向前前進
}
cout << endl;
}
}
DuLinkList::ElemType DuLinkList::priorElemAt(ElemType cur_e, ElemType &pri_e)//若cur_e是連結清單的資料元素，且不是第一個，則用pre_e傳回它的前驅
{
DulNode *p = m_heap->m_next->m_next; //p指向第二個元素
while (p != m_heap)
{
if (p->m_data == cur_e) //p指向結點的資料與cur_e值進行比較判斷
{
pri_e = p->m_prior->m_data; //将p的前驅結點的值賦給pre_e，pre_e儲存傳回
return TT_OK;;
}
p = p->m_next;
}
return TT_ERROR;
}
DuLinkList::ElemType DuLinkList::nextElemAt(ElemType cur_e, ElemType &Nex_e) //若cur_e是連結清單的資料元素,且不是最後一個,則用next_e傳回它的後繼，
{
DulNode *p = m_heap->m_next->m_next; //指向第二個元素， 如果指向第一個元素的話，獲得最後一個元素的後繼，就會輸出垃圾值
while (p != m_heap)
{
if (p->m_prior->m_data == cur_e)
{
Nex_e = p->m_data; //将p所指結點的值賦給Nex_e，Nex_e儲存傳回
return TT_OK;
}
p = p->m_next;
}
return TT_ERROR;
}
}
// MyDuLinkList 的測試函數
void testMyDuLinkList()
{
tt::DuLinkList MyDuLinkList;
int myLength(0); //連結清單的整表建立,尾插法
cout << "想建立多少資料的連結清單？";
cin >> myLength;
int *myDatas = new int[myLength];
cout << "請依次輸入這" << myLength << "個資料，中間以回車符隔開：" << endl;
for (int i = 0; i < myLength; ++i)
{
cin >> myDatas[i]; //輸入要存儲的資料的值
}
MyDuLinkList.createTail(myDatas, myLength); //調用createTail函數 建立單連結清單
MyDuLinkList.show();
while (true)
{
{
cout << "\n*************************************************************" << endl
<< "******************* 雙向循環連結清單基本功能展示 *******************" << endl
<< "*****************************************************************" << endl
<< "******************** 選擇1——資料插入. **********************" << endl
<< "******************** 選擇2——資料删除. **********************" << endl
<< "******************** 選擇3——擷取元素. **********************" << endl
<< "******************** 選擇4——查找元素. **********************" << endl
<< "******************** 選擇5——是否為空. **********************" << endl
<< "******************** 選擇6——擷取連結清單長度. **********************" << endl
<< "******************** 選擇7——清空元素. **********************" << endl
<< "******************** 選擇8——輸出所有元素. ************************" << endl
<< "******************** 選擇9——銷毀連結清單. ************************" << endl
<< "********************* 選擇10——獲得元素的前驅. *****************" << endl
<< "********************* 選擇11——獲得元素的後繼. *****************" << endl
<< "********************* 選擇12——逆序輸出所有元素. *****************" << endl
<< "******************** 選擇13——清屏！ ************************" << endl
<< "******************** 選擇0——退出程式！ ************************" << endl
<< "***********************************************************************" << endl
<< "***********************************************************************" << endl;
}
cout << "\n******************* 請輸入你想要使用的雙向循環連結清單功能的序号 ***************" << endl;
cout << "請輸入你的選擇：";
int userChoice(0);
cin >> userChoice;
if (userChoice == 0)
{
cout << "程式已退出，感謝您的使用!" << "\n" << endl;
break;
}
switch (userChoice)
{
case 1:
{ //插入元素
int pushLocate(0);
int pushElement;
cout << "請輸入想添加元素的位置：";
cin >> pushLocate;
cout << "請輸入想添加的元素：";
cin >> pushElement;
if (MyDuLinkList.insertAt(pushLocate, pushElement))
{
cout << "資料" << pushElement << "插入成功！" << endl;
MyDuLinkList.show();
}
else
cout << "插入的位置不合理，資料" << pushElement << "插入失敗！" << endl;
break;
}
case 2:
{ //删除元素
int cancelElem(0); //要删除的元素
int cancelLocate(0); //要删除的位置
cout << "請輸入想要删除的位置：";
cin >> cancelLocate;
if (MyDuLinkList.removeAt(cancelLocate, cancelElem))
{
cout << "資料" << cancelElem << "删除成功！" << endl;
MyDuLinkList.show();
}
else
cout << "删除的位置不合理或者連結清單中沒有元素，資料删除失敗！" << endl;
break;
}
case 3: //擷取元素
{
int getLocate(0);
int getElem(0);
cout << "請輸入想要擷取的位置：";
cin >> getLocate;
if (MyDuLinkList.getAt(getLocate, getElem))
{
cout << "擷取的元素為：" << getElem << endl;
MyDuLinkList.show();
}
else
{
cout << "擷取的位置不合理或者連結清單中沒有元素，擷取資料失敗！" << endl;
MyDuLinkList.getLength();
}
break;
}
case 4:
{ //查找元素
int getLocate(0);
int findElem(0);
cout << "請輸入你想要查找的元素的值：";
cin >> findElem;
if (MyDuLinkList.getIndexElemAt(getLocate, findElem))
{
cout << "找到了元素" << findElem << "，其在表中的索引值為：" << getLocate << "\n" << endl;
MyDuLinkList.show();
}
else
{
cout << "連結清單中不存在所需找的值！" << "\n" << endl;
MyDuLinkList.show();
}
break;
}
case 5:
if (MyDuLinkList.isEmpty())
{
cout << "目前雙向循環連結清單為空！" << endl;
MyDuLinkList.getLength();
}
else
{
cout << "目前的雙向循環連結清單非空！" << endl;
MyDuLinkList.show();
}
break;
case 6:
{ //擷取長度
int temp = MyDuLinkList.getLength();
cout << "雙向循環連結清單目前的長度為：" << temp << endl;
break;
}
case 7:
if (MyDuLinkList.clear())
{
cout << "雙向循環連結清單已被清空！" << endl;
MyDuLinkList.show();
}
else
{
cout << "雙向循環連結清單清空失敗！" << endl;
MyDuLinkList.show();
}
break;
case 8:
MyDuLinkList.show();
break;
case 9:
{
cout << "你确定要銷毀該雙向循環連結清單嗎？(若銷毀請輸入輸入(Y/y))";
char yesOrNo;
cin >> yesOrNo;
if ((yesOrNo == 'Y') || (yesOrNo == 'y'))
{
if (MyDuLinkList.destroy())
{
cout << "雙向循環連結清單已被銷毀." << "\n" << endl;
}
else
cout << "雙向循環連結清單銷毀失敗." << "\n" << endl;
}
break;
}
case 10:
{
int frontElem(0);
int getElem(0); //傳回的是要獲得哪一個元素的前驅的元素
cout << "輸入你想要獲得哪一個元素的前驅？（注意：不能擷取第一個元素的）：";
cin >> frontElem;
if (MyDuLinkList.priorElemAt(frontElem, getElem))
{
cout << "資料元素" << frontElem << "的，前驅元素是：" << getElem << endl;
MyDuLinkList.show();
}
else
{
cout << "擷取前驅元素失敗，不能擷取第一個元素的前驅或者連結清單中沒有你輸入的元素！" << endl;
MyDuLinkList.show();
}
break;
}
case 11:
{
int rearElem(0);
int getElem(0);
cout << "輸入你想要獲得哪一個元素的後繼？（注意：不能擷取最後一個元素的）：";
cin >> rearElem;
if (MyDuLinkList.nextElemAt(rearElem, getElem))
{
cout << "資料元素" << rearElem << "的，後繼元素是：" << getElem << endl;
MyDuLinkList.show();
}
else
{
cout << "擷取後繼元素失敗！不能擷取最後一個元素的後繼或者連結清單中沒有你輸入的元素！" << endl;
MyDuLinkList.show();
}
break;
}
case 12:
MyDuLinkList.traverseBack();
break;
case 13:
system("cls");
cout << "螢幕已經清屏，可以重新輸入!" << "\n" << endl;
break;
default:
cout << "輸入的序号不正确，請重新輸入!" << "\n" << endl;
}
}
delete[]myDatas;
myDatas = nullptr;
}
int main()
{
testMyDuLinkList();
system("pause");
return 0;
}
下面用C#代碼實作雙向清單：
namespace DateStructure
{
interface ILinkedList
{
void insertAt(int pos, int elem);
int removeAt(int pos);
int getAt(int pos);
int locationElemAt(int value);
int getLength();
bool isEmpty();
void clear();
void show();
void createTail(params int[] arrElem); //尾插法
}
class Node
{
public int m_Data { set; get; } = 0;
public Node m_Next { set; get; } = null;
public Node m_Prev { set; get; } = null;
}
class DoubleLink : ILinkedList
{
private Node m_Head;
public DoubleLink()
{
m_Head = new Node();
Debug.Assert(m_Head != null, "頭結點建立失敗！");
m_Head.m_Prev = m_Head.m_Next = m_Head;
}
public void createTail(params int[] arrElem) // 雙向清單的頭插法
{
m_Head.m_Data = arrElem.Length;
Node temp = m_Head;
for (int i = 0; i != arrElem.Length; ++i)
{
Node newNode = new Node();
Debug.Assert(newNode != null, "整表建立雙向連結清單失敗！");
newNode.m_Data = arrElem[i];
temp.m_Next = newNode;
newNode.m_Prev = temp;
newNode.m_Next = m_Head;
m_Head.m_Prev = newNode;
temp = newNode;
}
}
public void insertAt(int pos, int elem)
{
if ((pos < 1) || (pos > ((m_Head.m_Data) + 1))) //i位置不合理時，傳回false
{
WriteLine("插入元素失敗，插入的位置不正确！");
return;
}
Node temp = m_Head;
int locitionPos = 1;
while (locitionPos < pos)
{
temp = temp.m_Next;
++locitionPos;
}
Node newNode = new Node();
Debug.Assert(newNode != null, "插入節點配置設定記憶體失敗！");
newNode.m_Data = elem;
newNode.m_Next = temp.m_Next;
temp.m_Next.m_Prev = newNode;
temp.m_Next = newNode;
newNode.m_Prev = temp;
++m_Head.m_Data;
}
public void clear()
{
m_Head.m_Data = 0;
m_Head.m_Prev = m_Head.m_Next = m_Head;
}
public int getLength()
{
return m_Head.m_Data;
}
public bool isEmpty()
{
return m_Head.m_Data == 0;
}
public int getAt(int pos)
{
if (pos < 1 || m_Head.m_Data == 0 || pos > m_Head.m_Data)
{
WriteLine("擷取元素的位置不正确，或者該該連結清單為空！");
return -1;
}
Node temp = m_Head;
int locitionPos = 1;
while (locitionPos < pos)
{
temp = temp.m_Next;
++locitionPos;
}
return temp.m_Next.m_Data;
}
public int removeAt(int pos)
{
if (pos < 1 || m_Head.m_Data == 0 || pos > m_Head.m_Data)
{
WriteLine("删除的位置不正确，或者該連結清單是個空表，沒有元素可以删除！");
return -1;
}
Node temp = m_Head;
int locitionPos = 1;
while (locitionPos < pos)
{
temp = temp.m_Next;
++locitionPos;
}
var removeElem = temp.m_Next.m_Data;
temp.m_Next = temp.m_Next.m_Next;
temp.m_Next.m_Next.m_Prev = temp;
--m_Head.m_Data;
return removeElem;
}
public int locationElemAt(int value)
{
if (m_Head.m_Data == 0)
{
WriteLine("該連結清單為空,無法進行查找！");
return -1;
}
Node temp = m_Head;
for (int i = 0; i != m_Head.m_Data; ++i)
{
temp = temp.m_Next;
if (temp.m_Data == value)
{
return i + 1;
}
}
return -1;
}
public void show()
{
if (m_Head.m_Data == 0)
{
WriteLine("該雙向清單中沒有資料，無法顯示！");
return;
}
else
{
Node temp = m_Head;
Write("輸出此時雙向清單中所有的元素：");
for (int i = 0; i != m_Head.m_Data; ++i)
{
temp = temp.m_Next;
Write($"{temp.m_Data},");
}
WriteLine();
}
}
}
class Program
{
static void Main(string[] args)
{
DoubleLink myList = new DoubleLink();
const int arraySize = 5;
int[] myIntArray = new int[arraySize] { 0, 22, 33, 44, 55 };
myList.createTail(myIntArray);
myList.show();
WriteLine("請輸入你想要查找的元素的值：");
int locationPosElem = Convert.ToInt32(Console.ReadLine());
int tempElem = myList.locationElemAt(locationPosElem);
if (0 <= tempElem)
{
WriteLine($"該元素的位置序号是：{tempElem}");
myList.show();
}
else
{
WriteLine("該元素不再連結清單中！");
}
WriteLine("請輸入你想擷取連結清單中哪一個位置的元素：");
int getArrElem = Convert.ToInt32(Console.ReadLine());
WriteLine($"該位置的元素是：{myList.getAt(getArrElem)}");
myList.show();
WriteLine("請輸入你想删除哪一個位置的元素：");
int removePos = Convert.ToInt32(Console.ReadLine());
int temp = myList.removeAt(removePos);
if (temp >= 0)
{
WriteLine($"被删除的元素為：{temp}");
}
WriteLine($"\n擷取目前連結清單的總個數：{myList.getLength()}");
myList.show();
WriteLine("請輸入你想插入的元素值：");
int pushElem = Convert.ToInt32(Console.ReadLine());
WriteLine("請輸入你想插入的位置：");
int pushLocition = Convert.ToInt32(Console.ReadLine());
myList.insertAt(pushLocition, pushElem);
WriteLine($"\n擷取目前連結清單的總個數：{myList.getLength()}");
myList.show();
if (myList.isEmpty())
{
WriteLine("目前的連結清單為空！");
}
else
WriteLine("目前的連結清單非空！");
WriteLine($"\n擷取目前連結清單的總個數：{myList.getLength()}");
myList.clear();
WriteLine($"擷取目前連結清單的總個數：{myList.getLength()}");
}
}
}