C++ "鍊鍊"不忘@必有回響之雙向連結清單

1. 前言

寫過一篇與

單連結清單

相關的博文

（https://blog.51cto.com/gkcode/5681771）

，實際應用中，雙向循環連結清單的功能更強大。

單連結清單中，查詢一個已知結點的後驅結點的時間複雜度為

O(1)

。因結點本身不存儲與前驅結點相關的位址資訊，查詢前驅結點需要從頭結點掃描一次，是以時間複雜度是

O(n)

。

雙向連結清單

在結點類型中增加了可以存儲前驅結點位址的指針位，如下圖所示：

如此，無論查詢已知結點的後驅結點還是前驅結點的時間複雜度都是

O(1)

，缺點是需要付出空間上的代價。

在權衡算法性能時，會優先考慮時間複雜度的優劣，往往會采用空間換時間的政策。

結點的類型定義：

typedef int dataType;
//結點
struct LinkNode {
	//資料成員
	dataType  data;
	//後驅結點的位址
	LinkNode *next;
	//前驅結點的位址
	LinkNode *pre;
	//構造函數
	LinkNode(dataType data) {
		this->data=data;
		this->next=NULL;
		this->pre=NULL;
	}
};
           

2. 雙向連結清單

雙向連結清單

中除了有存儲頭結點的

head

指針變量外，一般還會增加一個存儲尾結點的

tail

指針變量。這樣，可以實作從頭至尾或從尾至頭對連結清單進行周遊。

為了操作的友善，初始化連結清單時都會提供一個空白的頭結點作為辨別結點。

在

雙向連結清單

中，如果尾結點的後驅指針位存儲頭結點位址，頭結點的前驅指針位存儲尾結點位址，如此形成一個首尾相連的閉環，則稱此連結清單為

雙向循環連結清單

。

雙向連結清單需要提供對結點上的資料進行正常維護的操作，如：

• 連結清單初始化。
• 建立連結清單。
• 查找。
• 後插入、前插入。
• 删除。
• ……

算法的整體思路和單連結清單相似，因結點中多了一個前驅結點資訊，為各種操作帶來便利的同時，也多了需要關注的細節。

下文将介紹雙向連結清單中的幾個重要函數。

2.1 初始化

如果是雙向循環連結清單，初始化時：

• head

  和

  tail

  指向空白頭結點。
• 且

  head

  的前驅結點和

  tail

  的後驅結點也指向空白頭結點。這個過程也可以放到建立連結清單時實作。

class LinkList {
	private:
		//頭指針
		LinkNode *head;
    	//尾指針
		LinkNode *tail;
		//連結清單的長度
		int length;
	public:
        //構造函數
		LinkList() {
			this->initLinkList();
		}
		//初始化連結清單
		void  initLinkList() {
             //頭指針存儲空白頭結點位址
			this->head=new LinkNode(0);
			//尾指針和頭指針位置相同
			this->tail=this->head;
             //尾結點的後驅結點是頭結點
			this->tail->next=this->head;
             //頭結點的前驅結點是尾結點
			this->head->pre=this->tail; 
		}
       //……其它函數
           

2.2 建立連結清單

可以使用頭部插入或尾部插入算法建立連結清單，本文僅介紹尾部插入建立算法，頭部建立算法可自行了解。如下示範使用尾部建立法建構以數列

{7，3}

為資料的連結清單。

• 建立值為

  7

  的新結點

  n

  。

• 設定新結點

  n

  的前驅結點為原尾結點。

n->pre=tail;
           

• 設定新結點

  n

  的後驅結點為原尾結點的後驅結點。

n->next=tail->next;
           

• 設定原尾結點的後驅結點為新結點

  n

  。

tail->next=n;
           

• 新結點

  n

  成為新的尾結點。

tail=n;
           

• 設定頭結點的前驅結點為新的尾結點。

head->pre=tail;
           

重複上述流程，最終完成連結清單的建立過程。

是否可以無視上述建立流程中的順序？

全局而言，順序基本是要遵循上述的要求，原則是

新結點->尾結點->頭結點

。

• 新結點：先設定新結點的前驅和後驅結點的位址。新結點的相應存儲位都是空白的，先設定前驅還是後驅不影響結果。
• 尾結點：修改原尾結點的後驅結點位址為新結點，原尾結點的使命完成後，再指定新結點為新的尾結點。
• 頭結點：修改頭結點的前驅位址為新尾結點。

編碼實作：

//尾部插入方式建立連結清單
void createFromTail(int n) {
	LinkNode *newNode,*p,*tail;
	//頭結點位址
	p=this->head;
    //尾結點位址
    tail=this->tail;
    for(int i=0; i<n; i++) {
        //建構一個新結點
        newNode=new LinkNode(0);
        cout<<"請輸入結點資料"<<endl;
        cin>>newNode->data;
        //原來的尾結點成為新結點的前驅結點
        newNode->pre=tail;
        //新結點的後驅結點為原來的尾結點的後驅結點 
        newNode->next=tail->next;
        //原尾結點的後驅結點為新結點
        tail->next=newNode; 				
        //新結點成為新的尾結點
        tail=newNode;
        //頭結點的前驅為新尾結點
        head->pre=tail; 
    }
    this->head=p;
    this->tail=tail;
}
           

測試尾部建立：

int main(int argc, char** argv) {
	LinkList list {};
	list.createFromTail(2);
	//沒删除之前
	cout<<"顯示建立結果:"<<endl;
	LinkNode *head= list.getHead();
	cout<<"從頭結點向尾結點方向搜尋："<<endl;
	cout<<head->next->data<<endl;
	cout<<head->next->next->data<<endl;
	LinkNode *tail=list.getTail();
	cout<<"從尾結點向頭結點方向搜尋 ："<<endl;
	cout<<tail->data<<endl;
	cout<<tail->pre->data<<endl; 
	head=tail->next;
	cout<<"從尾結點的後驅資訊位得到頭結點資訊 ："<<endl;
	cout<<head->next->data<<endl;
	cout<<head->next->next->data<<endl;
	return 0;	
}
           

執行結果：

2.3 查找

因

雙向循環連結清單

的頭尾是相連的，其查詢方案可以有多種變化：

• 按位置查找： 按位置查找建議從頭結點開始。
• 按值查找： 按值查找可以從頭結點或從尾結點開始。
• 查詢所有： 查詢所有可以從頭結點也可以從尾結點開始。

2.3.1 按位置查找

設空白頭結點編号為

，從頭結點向尾結點掃描過程中，給掃描到的結點依次編号，當查詢到和指定參數相同的編号時停止。

//按位置查詢結點（從頭部掃描到尾部） 
LinkNode * findNodeByIndex(int index) {
    int j=0;
    LinkNode *p=this->head;
    if(index==j)
        //如果 index 值為 0 ，傳回空白頭結點
        return p;
    //第一個資料結點	
    p=p->next;
    //設定第一個資料結點的編号為 1 ，當然這不是絕對，可以根據自己的需要設定編号
    j=1;
    while(p!=this->head && j<index) {
        p=p->next;
        j++;
    }
    if(j==index)return p;
    else return NULL;
}
           

2.3.2 按值查找

按值查找可以有

2

種方案：

• 頭結點向尾結點方向查找。

//按值查詢結點
LinkNode * findNodeByVal(dataType val) {
    //從第一個資料結點開始查找
    LinkNode *p=this->head->next;
    //當 p 再次指向頭結點結束查找，這也空白結點存在的意義
    while(p!=this->head && p->data!=val ) {
        p=p->next;
    }
    if(p!=this->head) {
        return p;
    } else {
        return NULL;
    }
}
           

• 尾結點向頭結點方向查找。

LinkNode * findNodeByValFromTail(dataType val) {
    //從尾結點開始查找
    LinkNode *p=this->tail;
    while(p!=this->head && p->data!=val ) {
        //向頭結點方向
        p=p->pre;
    }
    if(p!=this->head) {
        return p;
    } else {
        return NULL;
    }
}
           

2.3.3 查詢所有

• 從頭結點向尾結點方向查詢所有結點。

void showSelf() {
    if(this->head==NULL)return;
    //得到第一個資料結點
    LinkNode *p=this->head->next;
    while(p!=this->head) {
        cout<<p->data<<"\t";
        p=p->next;
    }
}
           

• 從尾結點向頭結點方向查詢所有結點。

void showSelf_() {
    if(this->tail==NULL)return;
    LinkNode *p=this->tail;
    while(p!=this->head) {
        cout<<p->data<<"\t";
        p=p->pre;
    }
}
           

2.4 插入

插入有前插入和後插入

2

種方案，于雙向連結清單而言，其時間複雜度都為

O(1)

。

2.4.1 後插入

把新結點插入到已知結點的後面，稱為後插入，其插入流程如下所示：

• 找到已知結點

  p

  ，建立新結點

  n

  。

• 設定

  n

  結點的前驅結點為已知結點

  p

  ，設定其後驅結點為已知結點

  p

  的後驅結點。

n->pre=p;
n->next=p->next;
           

• 設定

  p

  結點的後驅結點為

  n

  結點。

p->next=n;
           

• 設定結點

  n

  為其後驅結點的前驅結點。

n->next->pre=n;
           

編碼實作：

//後插入
int instertAfter(dataType val,dataType data) {
    //按值查找到結點
    LinkNode *p=this->findNodeByVal(val);
    if (p==NULL) {
        //結點不存在，傳回 false
        return false;
    }
    //建立新結點
    LinkNode *n=new LinkNode(0);
    n->data=data;
    //設定 p 結點為新結點的前驅結點 
    n->pre=p;
    //新結點的後驅結點為已知結點 p 的後驅結點
    n->next=p->next;
    //已知結點的後驅結點為新結點
    p->next=n;  
    //已知結點的原後驅結點的前驅結點為新結點
    n->next->pre=n;
    return true;
}
           

測試後插入：

int main(int argc, char** argv) {
	LinkList list {};
	//建立 7,3 兩個結點
    list.createFromTail(2);
    //在結點 7 後面插入值為 9 的結點
	list.instertAfter(7,9);
	list.showSelf();
    return 0;
}
           

執行結果：

2.4.2 前插入

把新結點插入到已知結點的前面，稱為前插入，因結點有前驅結點的位址資訊，雙向連結清單的前或後插入都較友善。

• 找到已知結點

  p

  ，建立新結點

  n

  。

• 設定結點

  n

  的前驅結點為

  p

  的前驅結點，設定其後驅結點為

  p

  結點。

n->pre=p->pre;
n-next=p;
           

• 設定

  p

  結點的前驅結點的後驅結點為

  n

  。

p->pre->next=n;
或
n->pre->next=n;
           

• 設定

  p

  結點的前驅結點為

  n

  結點。

p->pre=n;
           

編碼實作：

//前插入
int insertBefore(dataType val,dataType data) {
    //按值查找到結點
    LinkNode *p=this->findNodeByVal(val);
    if (p==NULL)
        return false;
    //查找前驅結點
    LinkNode *p1=this->head;
    while(p1->next!=p) {
        p1=p1->next;
    }
    //建構新結點
    LinkNode *n=new LinkNode(0);
    n->data=data;
    //新結點的後驅為 p 結點
    n->next=p;
    //新結點的前驅為 p 的前驅
    n->pre=p->pre;
    //p 的前驅結點的後驅結點為 n
    p->pre->next=n;
    //p 的前驅結點為 n
    p->pre=n;
    return true;
}
           

測試前插入：

int main(int argc, char** argv) {
	LinkList list {};
	//建立 7,3 兩個結點
	list.createFromTail(2);
    //在值為 7 的結點前面插入值為 9 的結點
	list.insertBefore(7,9);
	list.showSelf();
    return 0;
}
           

執行結果：

2.5 删除

2.5.1 删除結點

删除已知結點的基本操作流程：

• 查找到要删除的結點

  p

  。

• 找到結點

  p

  的前驅結點，設定其後驅結點為

  p

  的後驅結點。

p->pre->next=p->next;
           

• 找到

  p

  結點的後驅結點，設定其前驅結點為

  p

  結點的前驅結點。删除

  p

  結點。

p->next->pre=p->pre;
delete p;
           

編碼實作：

int delNode(dataType data) {
    //按值查找到要删除的結點
    LinkNode *p= this->findNodeByVal(data);
    if (p==NULL)return false;		
    //設定 p 的前驅結點的後驅結點 
    p->pre->next=p->next;
    p->next->pre=p->pre;
    delete p;
    return true;
}
           

測試删除操作：

LinkList list {};
//建立 {7,3,9} 3個結點
list.createFromTail(3);
//LinkNode *res= list.findNodeByValFromTail(4);
list.delNode(3);
list.showSelf();
           

執行結果：

2.5.2 删除所有結點

編碼實作：

void delAll() {
    LinkNode *p=this->head->next;
    //臨時結點
    LinkNode *p1;
    while(p!=this->head) {
        //保留删除結點的後驅結點
        p1=p->next;
        delete p;
        p=p1;
    }
    this->head=NULL;
}
           

3. 算法案例

界定數列

的要求：對于一個無序數列，首先在數列中找出一個基數，然後以基數為分界點，把小于基數的數字放在基數前面，反之放在後面。

3.1 示範流程

使用

雙向循環連結清單

實作界定數列的流程。

• 已知的無序數列：

• 選擇基數。這裡選擇第一個數字

  7

  作為基數。儲存在臨時變量

  tmp

  中。聲明

  2

  個變量

  left

  、

  right

  ，分别指向第一個資料和最後一個資料。

• 從

  right

  位置開始掃描整個數列，如果

  right

  位置的數字大于

  tmp

  中的值，則繼續向左移動

  right

  指針直到遇到比

  tmp

  中值小的數字，然後儲存到

  left

  位置。

• 對

  left

  指針的工作要求：當所處位置的數字比

  tmp

  值小時，則向右邊移動直到遇到比

  tmp

  值大的數字，然後儲存至

  right

  。

• 重複上述過程，直到

  left

  和

  right

  指針重合。

• 最後把

  tmp

  中的值複制到

  left

  和

  right

  指針最後所指向的位置。最終實作以數字

  7

  界定整個數列。

3.2 算法實作

使用雙向連結清單實作上述需求：

• 初始化連結清單，并以尾部插入方式（保證數列的邏輯順序和實體順序一緻）建立數列

  {7,3,1,9,12,5,8}

  。

int main(int argc, char** argv) {
	LinkList list {};	
	list.createFromTail(7);
	//沒删除之前
	cout<<"顯示建立結果:"<<endl; 
	list.showSelf();
	return 0;
}
           

執行後結果：

• 編寫界定算法。

void  baseNumBound() {
    //第一個資料結點的資料作為界定數字
    int tmp=this->head->next->data;
    //左指針，指向第一個資料結點
    LinkNode *left=this->head->next;
    //右指針，指向尾結點
    LinkNode *right=this->tail;

    while(left!=right) {
        while(left!=right && right->data>tmp) {
            //右指針向左移動
            right=right->pre;
        }
        left->data=right->data;
        while(left!=right && left->data<tmp) {
            //左指針向右移動
            left=left->next;
        }
        right->data=left->data;
    }
    left->data=tmp;
}
           

測試代碼：

int main(int argc, char** argv) {
	LinkList list {};
	list.createFromTail(7);
	//沒删除之前
	cout<<"顯示連結清單的建立結果:"<<endl;
	list.showSelf();
	list.baseNumBound();
	cout<<"\n顯示界定後的數列："<<endl;
	list.showSelf();
	return 0;
}
           

4. 總結