這篇文章是關于利用C++模板的方式實現的雙向鏈表以及雙向鏈表的基本操作沟沙，在之前的博文C語言實現雙向鏈表中河劝，已經給大家分析了雙向鏈表的結構，并以圖示的方式給大家解釋了雙向鏈表的基本操作矛紫。本篇文章利用C++實現了雙向鏈表的基本操作赎瞎，其中包括：
雙向鏈表的基本操作C++語言實現
| 雙向鏈表 | 實現的功能 |
|---|---|
| 頭部插入結點建立鏈表 | 尾部插入結點建立鏈表 |
| 實現指定位置插入結點 | 查找給定數值是否存在 |
| 刪除指定位置的結點 | 修改指定位置的結點 |
| 雙向鏈表的長度 | 打印雙向鏈表 |
定義雙向鏈表的結點
因為雙向鏈表的結點由三部分構成，用于指向當前節(jié)點的直接前驅節(jié)點的指針域,用于存儲數據元素數據域颊咬，以及用于指向當前節(jié)點的直接后繼節(jié)點的指針域务甥。
因此，首先我們需要封裝一個結點類,定義了結點的三個要素喳篇，并利用構造函數實現初始化敞临，另外，考慮到在雙向鏈表中要用到結點類麸澜，所以將雙向鏈表類定義為結點的友元類挺尿。
class doubleLinkedListNode
{
private:
doubleLinkedListNode<T> *prior;//雙向結點前驅指針指向該結點的前驅結點
T data;//儲存結點數據
doubleLinkedListNode<T> *next;//雙向結點的后驅指針指向該結點的后繼結點
//將雙向鏈表類定義為結點的友元類
friend class doubleLinkedList<T>;
public:
//結點的無參構造函數,將結點指針域初始化為NULL
doubleLinkedListNode()
{
prior = NULL;
next = NULL;
}
//結點的有參構造函數，初始化指針域和數據域
doubleLinkedListNode(T _data,doubleLinkedListNode<T> *_prior = NULL,doubleLinkedListNode<T> *_next = NULL)
{
prior = _prior;//初始化前驅指針
data = _data;//初始化數據域
next = _next;//初始化后繼指針
}
~doubleLinkedListNode()
{
prior = NULL;
next = NULL;
}
};
雙向鏈表的基本操作
實現了雙向鏈表頭部插入結點， 尾部插入結點票髓，指定位置插入結點建立鏈表， 查找給定數值的指定位置铣耘，刪除指定位置的結點洽沟，修改指定位置的結點，雙向鏈表的長度蜗细，打印雙向鏈表裆操，接下來逐一進行講解實現：
頭部插入結點建立鏈表
帶頭結點實現的雙向鏈表，實現頭部插入結點可分為兩種情況炉媒，一種是只有一個頭結點的時候踪区，只需要使head和newNode的兩個指針關聯上即可，另外的兩個指針依舊是NULL狀態(tài)吊骤。另一種情況便是有結點的情況缎岗，這個時候跟在中間結點插入相似，需要調整四個指針,首先是讓newNode與后繼結點關聯白粉，最后讓newNode與head結點關聯传泊。
因此，頭部插入結點實現如下：
template<class T>
bool doubleLinkedList<T>::insertNodeByhead(T item)
{
//創(chuàng)建一個新的結點
doubleLinkedListNode<T>* newNode = new doubleLinkedListNode<T>(item);
if (newNode == NULL){
cout << "內存分配失敗鸭巴，新結點無法創(chuàng)建" << endl;
return false;
}
//分兩種情況眷细，head的next是否為NULL,然后處理四個指針
if(head->next == NULL)
{
head->next = newNode;
newNode->prior = head;
return true;
}
else{
newNode->next = head->next;
head->next->prior = newNode;
newNode->prior = head;
head->next = newNode;
return true;
}
}
尾部插入結點建立鏈表
在尾部插入結點，當然第一步需要找到最后一個結點鹃祖，然后在其后進行插入溪椎，雙向鏈表因為兩端的指針都是指向NULL的，所以在尾部插入也只需要調整兩個指針就ok.
template<class T>
bool doubleLinkedList<T>::insertNodeBytail(T item)
{
//創(chuàng)建一個新的結點
doubleLinkedListNode<T>* newNode = new doubleLinkedListNode<T>(item);
if (newNode == NULL){
cout << "內存分配失敗恬口，新結點無法創(chuàng)建" << endl;
return false;
}
//首先找到最后一個結點
doubleLinkedListNode<T>* lastNode = head;
while(lastNode->next != NULL)
{
lastNode = lastNode->next;//沒找到就一直循環(huán)
}
//找到調整指針
lastNode->next = newNode;
newNode->prior = lastNode;
return true;
}
實現指定位置插入結點
在指定位置插入只需要兩步走校读，首先也是找到指定的位置，然后就是插入新結點的指針的調整祖能，中間插入是最復雜的地熄，都逃不過調整四個指針，但是首先依舊是讓新結點和后繼結點建立上相關性芯杀，最后讓新結點與前繼結點建立關系端考，實現新結點的插入。
bool doubleLinkedList<T>::insertNode(T item,int n)
{
if(n<1){
cout<<"輸入的非有效位置揭厚！"<<endl;
return false;
}
doubleLinkedListNode<T>* pMove = head;//創(chuàng)建一個新的指針却特，設置為游標指針
//首先找到插入位置
for(int i=1;i<n;i++)
{
pMove = pMove->next;
if(pMove == NULL&& i<=n)
{
cout<<"插入位置無效！"<<endl;
return false;
}
}
//創(chuàng)建一個新的結點
doubleLinkedListNode<T>* newNode = new doubleLinkedListNode<T>(item);
if (newNode == NULL){
cout << "內存分配失敗筛圆，新結點無法創(chuàng)建" << endl;
return false;
}
//插入新的結點
newNode->next = pMove->next;
if (pMove->next != NULL)
{
pMove->next->prior = newNode;
}
newNode->prior = pMove;
pMove->next = newNode;
return true;
}
查找給定數值是否存在
查找給定元素裂明，也就是一個遍歷鏈表的過程，從頭結點的下一個結點開始遍歷太援，畢竟第一個頭結點是沒有儲存數據項的闽晦。
template<class T>
bool doubleLinkedList<T>::findData(T item)
{
doubleLinkedListNode<T> *pMove = head->next; //設置游標指針
if(pMove == NULL)//鏈表為空
{
return false;
}
while(pMove)//遍歷鏈表
{
if(pMove->data == item){
return true;
}
pMove = pMove->next;
}
return false;
}
刪除指定位置的結點
刪除指定的結點扳碍，第一步查找到刪除的結點，需要定義一個刪除指針臨時指向將要刪除的結點仙蛉，最后指針處理刪除之后別忘了釋放該結點空間笋敞。
template<class T>
bool doubleLinkedList<T>::deleteData(int n)
{
if (n<1||n>getLength())
{
cout << "輸入非有效位置" << endl;
return false;
}
doubleLinkedListNode<T> * pMove = head;//設置游標指針
doubleLinkedListNode<T> * pDelete;
//查找刪除結點的位置
for (int i = 1; i <= n; i++)
{
pMove = pMove->next; //游標指針后移
}
//刪除結點
pDelete = pMove;
pMove->prior->next = pDelete->next;
pMove->next->prior = pDelete->prior;
delete pDelete;//釋放空間
return true;
}
修改指定位置的結點
修改指定位置的結點數據，當然還是得找到指定位置荠瘪，然后對其進行修改夯巷，修改之后將原來的數據以引用的形式返回，具體的用法在測試函數中寫到了的哀墓，不會的可以作為參考趁餐。
template<class T>
bool doubleLinkedList<T>::changeListElements(int n,T item,T &x)
{
if (n<1||n>getLength())
{
cout << "輸入非有效位置" << endl;
return false;
}
doubleLinkedListNode<T> *pMove = head->next; //設置游標指針
for(int i=1;i<n;i++)//找到指定位置1
{
pMove = pMove->next;
}
x = pMove->data;
pMove->data = item;
return true;
}
雙向鏈表的長度
計算雙向鏈表的長度的函數，在雙向鏈表的私有成員封裝了一個變量length,以此來記錄雙向鏈表的長度篮绰，遍歷雙向鏈表后雷，逐一進行計算結點數就是雙向鏈表的長度。
template<class T>
int doubleLinkedList<T>::getLength()
{
doubleLinkedListNode<T> *pMove = head->next; //設置游標指針
int length=0;
//遍歷鏈表吠各，計算結點數
while(pMove!=NULL)
{
pMove = pMove->next; //游標指針后移
length++; //計算length
}
return length;
}
打印雙向鏈表
打印雙向鏈表喷面，從第二個結點開始遍歷鏈表，因為第一個為頭結點是不含數據的走孽，打印的過程也就是一個遍歷的過程惧辈。
template<class T>
void doubleLinkedList<T>::printLinkedlist()
{
//從第二個結點開始打印，表頭不含數據
doubleLinkedListNode<T>* pMove = head->next;
while(pMove)
{
cout<<pMove->data<<" ";
pMove = pMove->next;//移動指針
}
cout<<endl;
}
以上就是本次博文與大家分享的利用C++語言實現雙向鏈表磕瓷，在用C語言寫了之后盒齿，感覺寫起來就比較輕松，唯一不同的就是要利用類來進行封裝困食。完整的代碼边翁，以及測試代碼我已經Push到Github,喜歡的小伙伴歡迎Star! C++語言實現雙向鏈表Github地址，如果還想要了解其他的數據結構實現的小伙伴也可以來我的Myblog,我們一起討論硕盹，如果有寫的不好的地方還請多多擔待符匾，也歡迎大家在評論區(qū)留言，我加以改正瘩例，共同進步啊胶！
