前言

資料結構，一門資料處理的藝術，精巧的結構在一個又一個演算法下發揮著他們無與倫比的高效和精密之美，在為資訊技術打下堅實地基的同時，也令無數開發者和探索者為之著迷，

也因如此，它作為博主大二上學期最重要的必修課出現了，由于大家對于上學期C++系列博文的支持，我打算將這門課的筆記也寫作系列博文，既用于整理、消化，也用于同各位交流、展示資料結構的美，

此系列文章，將會分成兩條主線，一條“資料結構基礎”，一條“資料結構拓展”，“資料結構基礎”主要以記錄課上內容為主，“拓展”則是以課上內容為基礎的更加高深的資料結構或相關應用知識，

歡迎關注博主，一起交流、學習、進步，往期的文章將會放在文末，

這一節我們將開始總結一個常見的資料結構：線性表，
由于線性表的內容較多，本節只能總結部分內容，
主要為兩種基礎的線性表，陣列和鏈表，在簡單介紹其定義之后，重點會放在實作對其各種操作的簡單實作及封裝，
本節思維導圖如下:

鏈式存盤結構——鏈表

鏈表也是一種線性表，相較于陣列不同的是，鏈表中的元素的存盤結構是鏈接式的，

作為一種線性表，元素在邏輯上是連續的，有順序且呈線性排列；但在存盤上他們并不像順序表一般占據連續的空間，而是隨機分布在空間各處，每個結點通過指標來記錄后繼的地址形成鏈接，

從上面例子中也可看出，每個結點在其所占的空間中除了要存盤本身的資料外，還需要單獨使用一片空間存盤其后繼的指標，

所以一個結點可以大致表示成如下形式：

他們鏈接起來可以表示成：

可以注意到，鏈表的尾結點沒有后繼，所以其后繼指標需要指向空，且由于鏈表的內容是隨機分布在空間中的各處，所以為了便于訪問他們，我們需要保留頭結點的指標，也就是知道頭結點的位置，對于后面的元素便可以通過后繼節點依次訪問到他們，

鏈表的優點在于其空間上的靈活，鏈接式的存盤似的其長度可以任意改變，不像陣列的長度是定值，缺點就在于其失去了順序表中靜態訪問結點的能力，不能直接按照下標訪問某元素，使得訪問給定下標的元素必須遍歷鏈表，

單鏈表的實作

知道了鏈表的設計方案，下面我們就來將設計方案付諸實踐，變成代碼，

實際上正如上文所說，鏈表的內容相較于一般的節點來說只是多出了后繼指標，所以我們完全可以在一般的資料結點的基礎上加上后繼指標來得到鏈表元素，

單鏈表元素

//C
typedef struct _Node{
    int value;
    struct _Node * next;
}Node;
Node * head;

//Java
class Node{
	int value;
	Node next;
}
Node head;

單鏈表的遍歷

遍歷整個單鏈表，必不可少的條件就是獲得頭指標，有了頭指標就可以根據后繼指標依次訪問后面的元素，
那么什么時候鏈表遍歷結束呢？通過上文的例子不難發現，鏈表的尾結點的后繼指標為空，所以可以根據是否為空來判斷這一結點是否是有效結點，這樣既可以在遍歷過尾結點后準確而迅速的結束遍歷，也可以應對鏈表為空的情況（頭指標為空）

下面以遍歷鏈表獲得所有元素加和為例：

//C
int getSum(Node * head){
	int sum = 0;
	while(head){
		sum += head->value;
		head = head->next;
	}
	return sum;
}

//java
class LinkedList{
	Node head;
	public int getSum(){
		int sum = 0;
		Node cur = head;//不能直接使用頭參考進行遍歷
		while(cur != null){
			sum += cur.value;
			cur = cur.next;
		}
		return sum;
	}
}

復雜度：O(n)

插入元素

向鏈表的優秀之處在于其資料組織是動態的，插入一個元素可以不需要像陣列一樣將后面的元素向后移動，可以通過對后繼指標的操作來完成插入，

以將元素node插入下標為index(0 ≤ index ≤ len)的位置為例，該函式需要回傳操作后的頭指標：

//C
Node * insert(Node * head,Node * node,int index){
	int curIdx = 0;
	if(index == 0){//新元素位于隊首
		node->next = head;
		return node;
	}
	while(head){
		if(curIdx = index - 1 || head->next = NULL){
			node->next = head->next;
			head->next = node;
			break;
		}
		head = head->next;
		curIdx++;
	}
	return head; 
}

//Java
class LinkedList{
	Node head;
	public Node insert(Node node,int index){
		if(index == 0){//插入頭
			node.next = head;
			head = node;
		}
		int curIdx = 0;
		Node cur = head;
		while(cur != null){
			if(curIdx = index - 1 || cur.next == null){
				node.next = cur.next;
				cur.next = node;
				break;
			}
			cur = cur.next;
			curIdx++;
		}
		return head;
	}
}

上面的程式可以完成將指定元素插入到指定下標的操作，

需要注意的是，該程式特殊規定對于下標超出當前鏈表規模時會默認插入隊尾，

由于鏈表不能直接靜態的找到某下標的位置，所以遍歷尋找到該下標的位置還是不可避免的開銷，主要的復雜度就產生在這里，
復雜度：O(n)

哨位結點

注意到上面的插入操作中如果將元素插入隊首，那么頭指標需要更新成為新元素，那么為了避免頻繁的更改頭指標，我們可以引入哨位結點來解決這個問題，

哨位結點又稱哨兵結點，它是一個空節點，沒有實際意義，是人為規定的默認隊首，真正的隊首一定是哨兵節點的后繼節點，這樣一來，插入元素至隊首就變成了插入元素到哨兵節點后面，此時可以保證不論如何頭指標不會更改，

使用哨位節點，我們可以重新實作插入操作，此時頭指標不會發生改變，

//C
int insert(Node * head,Node node,int index){
	int curIdx = 0;
	while(head){
		if(curIdx == index || head->next == NULL){
			node->next = head->next;
			head->next = node;
			break;
		}
		head = head->next;
		curIdx++;
	}
	return 1;
}

//Java
class LinkedList{
	Node head;
	public boolean insert(Node node,int index){
		int curIdx = 0;
		Node cur = head;
		while(cur != null){
			if(curIdx = index || cur.next == null){
				node.next = cur.next;
				cur.next = node;
				break;
			}
			cur = cur.next;
			curIdx++;
		}
		return true;
	}
}

統一了插入隊首和插入隊中，美感增加了呢，
復雜度：O(n)

單鏈表的不足

單鏈表存在一個問題，其中的元素的只能單向訪問不能逆序遍歷，也就是說，我們僅知道一個節點的后繼節點卻不知道其前驅結點，

為了解決這個問題，我們需要引入回圈鏈表和雙向鏈表，

回圈鏈表

回圈鏈表指的是將一個單鏈表首尾相接，使尾結點的后繼為頭結點，使頭結點的前驅為尾結點，

在回圈鏈表中，為了方便對空鏈表的處理，最好要保留哨位結點，

因此，對于空鏈表，就是僅有哨位結點作為“頭結點”，其后繼指向它自身：

這也提示了我們如何創建并初始化一個回圈鏈表：就是初始化一個哨位結點，并使它的后繼指標指向自己：

創建/初始化回圈鏈表

通過上面的敘述不難發現，回圈鏈表僅是改變了尾結點的指標，并沒有改變結點本身的結構，所以我們可以沿用單鏈表的結點定義，

//c
Node * createCircularList(){
    Node * head = (Node *)malloc(sizeof(Node));
    head->next = head;
    return head;
}

//java
public class CircularList {
	class Node{
		int value;
		Node next;
	}
	
	Node head;
	
	public CircularList() {
		head = new Node();
		head.next = head;
	}
}

回圈鏈表尋找前驅

下面我們就來使用回圈鏈表來尋找一個元素的前驅，

思路非常的簡單，就是不斷的向后遍歷，直到尋找到一個元素的后繼等于詢問元素即可，

//c
Node * getPrecursor(Node * curr){
    Node * node = curr;
    while(node->next != curr){
        node = node->next;
    }
    return node;
}

//java
public class CircularList {
	class Node{
		int value;
		Node next;
	}
	
	Node head;
	
	
	public Node getPrecursor(Node curr) {
		Node node = curr;
		while(node.next != curr) {
			node = node.next;
		}
		return node;
	}
}

復雜度：O(n)
對于常規的增刪改查操作，回圈鏈表的操作基本上同單向鏈表沒有本質上的區別，

一個需要注意的地方就是回圈鏈表的遍歷，由于回圈鏈表的尾結點的后繼是頭結點，所以在判斷遍歷結束時條件需要更改為后繼節點是否為頭結點，其余操作這里就不再一一贅述了，

雙向鏈表

雙向鏈表是在單鏈表的基礎上修改結點結構得到的，在一個結點上不僅記錄該節點的后繼還記錄該節點的前驅，從而在結點之間形成雙向連接，

一個結點可以表示成這樣：

這樣就需要我們對資料結點的結構進行修改：

//C
typedef struct _DoublyNode{
    int value;
    DoublyNode * prev;
    DoublyNode * next;
}DoublyNode;

//java
public class DoublyList {
	class Node{
		int value;
		Node prev;
		Node next;
	}
	private Node head;
}

依據這樣的結構，他們連接起來可以表示成：

當然我們也可以給他們加上哨位結點并且使用環形結構：

雙向鏈表的操作相較于單鏈表會復雜不少，這里我們重新來封裝一下基于雙鏈表的增刪查，由于雙向鏈表需要同時維護前驅和后繼指標，所以為了便于插入和洗掉，我們有必要使用首位兩個哨位結點來控制，

初始化雙向鏈表

那么初始化或者創建一個雙向鏈表的作業就不同于單向鏈表了，需要初始化兩個哨位結點，并且將它們相連，

//c
DoublyNode * createDoublyList(){
	DoublyNode * head = (DoublyNode *)malloc(sizeof(DoublyNode));
	DoublyNode * tail = (DoublyNode *)malloc(sizeof(DoublyNode));
	
	head->next = tail;
	head->prev = NULL;
	tail->next = NULL;
	tail->prev = head;
	
	return head;
}

//java
public class DoublyList{
	private Node head;
	private Node tail;
	
	public DoublyList(){
		head = new Node();
		tail = new Node();

		head.next = tail;
		head.prev = null;
		tail.next = null;
		tail.prev = head;
	}
}

插入元素

向鏈表中插入一個元素，需要斷開原有的鏈接，重建兩次鏈接，

重建鏈接的程序會有一些繞，因為它涉及到后繼元素的前驅指標，這需要嵌套兩次，并且更改前驅和后繼節點的順序也有可能造成bug，

//C
int insert(DoublyNode * node,DoublyNode * head,int index){
	if(index < 0 || node == NULL)
		return 0;
	int curr = 0;
	while(head->next){
		if(curr == index || head->next->next == null){
			head->next->prev = node;
			node->next = head->next;
			node->prev = head;
			head->next = node;
			break;
		}
		curr++;
		head = head->next;
	}
	return 1;
}

//java
public class DoublyList{
	private Node head;
	public boolean insert(int index,Node node){
		if(index < 0 || node == null)
			return false;
		Node head = this.head;
		while(head.next != null){
			if(curr == index || head.next.next != null){
				head.next.prev = node;
				node.next = head.next;
				node.prev = head;
				head.next = node;
				break;
			}
			curr++;
			head = head.next;
		}
	} 
	return true;
}

查詢元素前驅

用雙向鏈表獲得前驅真的是最簡單的事情了，因為前驅就在結點中存盤著，直接回傳就好，

//c
DoublyNode * getPrecursor(DoublyNode * node){
	if(node)
		return node->prev;
	return NULL;
}

復雜度：O(1)
快速的時間復雜度來源于雙向鏈表在空間復雜度上面的妥協，可以說雙向鏈表的取錢去操作是空間換時間的典范

洗掉元素

洗掉元素，需要重建兩條邊并且洗掉結點，難點在于釋放元素的時機，和修改前驅結點的后繼以及修改后繼結點的前驅，

//c
int delete(DoublyNode * head,int index){
	if(index < 0)
		return  0;
	int curr = 0;
	head = head->next;//先向后跳一格，查看當前元素是否是待洗掉元素
	while(head->next){
		if(curr == index){
			head->prev->next = head->next;
			head->next->prev = head->prev;
			 
			 free(head);
			 return 1;
		}
	}
	return 0;
}

//java
public class DoublyList{
	private Node head;
	private Node tail;

	public boolean delete(int index){
		if(index < 0)
			return  false;
		int curr = 0;
		Node head = this.head;
		head = head.next;//先向后跳一格，查看當前元素是否是待洗掉元素
		while(head.next != null){
			if(curr == index){
				head.prev.next = head.next;
				head.next.prev = head.prev;
				 
				 return true;
			}
		}
		return false;
	}
}

三種鏈表的簡單總結

上面簡單介紹了三種鏈表的定義及各種操作以及鏈表中的哨位結點，

有些同學可能會納悶他們能否組合使用，還是說像是只有單鏈表才能組織成回圈鏈表的形式這種限制，

博主認為：鏈表回圈、哨位結點乃至雙向鏈表是鏈表結構的不同設計思想，并不專屬于某種設計，我們可以看到哨位結點在單向、回圈鏈表中的使用，也可以看到雙向的回圈鏈表，所有的結構都是為演算法或功能服務的，為了配合他們完成任務，可以使用各種合適的設計方案，

往期博客

• 【資料結構基礎】資料結構基礎概念
• 【資料結構基礎】線性資料結構——線性表概念 及 陣列的封裝

參考資料：

• 《資料結構》（劉大有，楊博等編著）
• 《演算法導論》（托馬斯·科爾曼等編著）
• 《圖解資料結構——使用Java》（胡昭民著）