鏈結串列

鏈結串列(Linked List)是使用Pointer(指標)串接資料，使用鏈結串列的好處是找到指定位置後，可以有效率地插入或刪除元素，陣列不適合在中間位置插入或刪除元素，因為需要花較多時間搬移元素，適合在兩端插入或刪除元素。鏈結串列不能隨機讀取指定位置的元素，只能從前往後一個一個走到指定的位置才能讀取，而陣列可以使用索引值(隨機)讀取陣列中指定位置的元素。陣列與鏈結串列各有優缺點，寫程式時需要善加利用每種資料結構的優點，避開或減少使用其缺點。

以下為一個簡單的鏈結串列，指標head指向鏈結串列的第一個元素5，元素5的指標指向下一個元素3，元素3的指標指向下一個元素2，元素2的指標指向下一個元素6，元素6的指標沒有下一個元素，使用「●」表示None，表示鏈結串列到達終點，如下圖。

類別LinkedList內，使用方法remove(self, x)刪除節點x，示意圖如下，假設鏈結串列為「5、3、6」，使用remove(3)刪除節點3，變數tmp從head往後找到節點3，過程中變數before指向tmp的前一個元素，如下圖。

此時tmp不等於self.head，執行「before.next = tmp.next」，就可以把變數tmp所指向的節點3從鏈結串列中刪除，如下圖。

接著執行remove(5)刪除節點5，此時tmp等於self.head。

此時tmp等於self.head，執行「self.head = self.head.next」，就可以把self.head所指向的節點6，節點5從鏈結串列中刪除，如下圖。

類別LinkedList內，使用方法printLinkedList (self)從self.head印出鏈結串列的每一個元素，程式碼如下。

建立好了鏈結串列類別LinkedList後，首先需要新增類別LinkedList的物件，接著使用方法insertHead建立鏈結串列的第一個元素，接著使用方法insert插入第2個以後的元素，使用方法remove刪除元素，過程中印出鏈結串列的每一個元素，程式碼如下。

程式執行結果如下圖。

類別CirLinkedList內，使用方法insertHead建立環狀鏈節串列的第一個節點，且head指向第一個節點，且head.next指向自己，如下圖，形成一個元素的環狀鏈節串列。

使用方法insert(self, y, x)將節點x插入到節點y的後面，示意圖如下，假設環狀鏈結串列為「5、3、6」，使用insert(3, 2)在節點3後面插入節點2，首先使用Node(2)新增節點2，設定給變數nodex，變數tmp從head往後找到節點3，如下圖。

使用「nodex.next = tmp.next」將nodex的指標next指向tmp的指標next，如下圖。

使用「tmp.next = nodex」將tmp的指標next指向nodex，如下圖，就完成環狀鏈結串列的插入。

類別CirLinkedList內，使用方法remove(self, x)刪除節點x，示意圖如下。

(一)刪除節點3

假設鏈結串列為「5、3、6」，使用remove(3)刪除節點3，變數tmp從head往後找到節點3，過程中變數before指向tmp的前一個元素，如下圖。

此時tmp不等於self.head，執行「before.next = tmp.next」，就可以把變數tmp所指向的節點3從鏈結串列中刪除，如下圖。

(二)刪除節點5

接著執行remove(5)刪除節點5，此時tmp等於self.head，但self.head.next不等於self.head，表示環狀鏈結串列目前有兩個以上的元素，before指向節點5的前一個元素節點6。

執行「self.head = self.head.next」，就可以把self.head所指向的節點6，如下圖。

執行「before.next = self.head」，就可以把before.next所指向self.head，如下圖。

(三)刪除節點6

接著執行remove(6)刪除節點6，此時tmp等於self.head，且self.head.next等於self.head，表示環狀鏈結串列目前只有一個的元素，執行「self.head = None」，環狀鏈結串列就被清空。

類別CirLinkedList內，使用方法len計算環狀鏈結串列的長度，示意圖如下。

執行「tmp = self.head.next」，tmp指向head的下一個元素。

此時tmp不等於self.head，執行「count = count + 1」，變數count遞增1，執行「tmp = tmp.next」，就可以把變數tmp所指向tmp的下一個元素，如下圖。

直到tmp等於head跳出迴圈，就可以計算出環狀鏈結串列的長度

類別CirLinkedList內，使用方法printLinkedList (self)從self.head印出鏈結串列的每一個元素，程式碼如下。

建立好了環狀鏈結串列類別CirLinkedList後，首先需要新增類別CirLinkedList的物件，接著使用方法insertHead建立鏈結串列的第一個元素5，接著使用方法insert插入第2個以後的元素(6、7、8、9)，使用方法remove刪除元素，過程中印出環狀鏈結串列的每一個元素，程式碼如下。

雙向鏈結串列(Double Linked List)是使用Pointer(指標)串接資料，使用雙向鏈結串列的好處是找到指定位置後，可以很有效率地插入或刪除元素，且很容易找到節點的前一個元素與下一個元素，陣列不適合在中間位置插入或刪除元素，因為需要花較多時間搬移元素，適合在兩端插入或刪除元素。雙向鏈結串列不能隨機讀取指定位置的元素，只能從前往後或從後往前一個一個走到指定的位置才能讀取，而陣列可以使用索引值讀取陣列中指定位置的元素。陣列與雙向鏈結串列都有其優缺點，寫程式時需要善加利用每種資料結構的優點，避開或減少使用其缺點。

以下為一個簡單的雙向鏈結串列，指標head指向鏈結串列的第一個元素5，每一個元素都指向前一個與下一個元素。元素5的指標next指向下一個元素3，元素5的指標pre指向前一個元素6；元素3的指標next指向下一個元素2，元素3的指標pre指向上一個元素5；元素2的指標next指向下一個元素6，元素2的指標pre指向前一個元素3；元素6的指標next指向下一個元素5，元素6的指標pre指向前一個元素2，如下圖。

4-3-1 建立雙向鏈結串列

雙向鏈結串列的每個節點需要兩個指標，指向上一個與下一個元素，Node用於建立節點，類別DoubleLinkedList用於實作雙向鏈結串列，程式碼如下，以下每一小節程式碼串接起來就是一個完整的雙向鏈結串列程式。

類別DoubleLinkedList內，使用方法insertHead建立雙向鏈節串列的第一個節點，且head指向第一個節點，head.next與head.pre都指向自己，如下圖，形成一個元素的雙向鏈節串列。

使用方法insert(self, y, x)將節點x插入到節點y的後面，示意圖如下，假設存在一個雙向鏈結串列，其資料依序為「5、3、6」，使用方法insert(3, 2)在節點3後面插入節點2，首先使用Node(2)新增節點2，設定給變數nodex，變數tmp從head往後找到節點3，如下圖。

使用「nodex.next = tmp.next」將nodex的指標next指向tmp的指標next，如下圖。

使用「nodex.pre = tmp」將nodex的指標pre指向tmp，如下圖。

使用「tmp.next.pre = nodex」將tmp的指標next的指標pre指向nodex，如下圖。

使用「tmp.next = nodex」將tmp的指標next指向nodex，如下圖，就完成雙向鏈結串列的插入。

類別DoubleLinkedList內，使用方法remove(self, x)刪除節點x，示意圖如下。

(一)刪除節點3

假設雙向鏈結串列為「5、3、6」，使用remove(3)刪除節點3，變數tmp從head往後找到節點3，變數tmp指向要刪除的節點3，如下圖。

此時tmp不等於self.head，執行「tmp.pre.next = tmp.next」後，如下圖。

接著執行「tmp.next.pre = tmp.pre」後，如下圖。如此就可以把變數tmp所指向的節點3從雙向鏈結串列中刪除

(二)刪除節點5

接著執行remove(5)刪除節點5，變數tmp指向要刪除的節點5，此時tmp等於self.head，但self.head.next不等於self.head，表示雙向鏈結串列目前有兩個以上的元素。

執行「self.head = tmp.next」，就可以把self.head所指向的節點6，如下圖。

接著執行「tmp.pre.next = tmp.next」，就可以把tmp.pre.next指向tmp.next，如下圖。

執行「tmp.next.pre = tmp.pre」，就可以把tmp.next.pre指向tmp.pre，如下圖。

(三)刪除節點6

接著執行remove(6)刪除節點6，此時tmp等於self.head，且self.head.next等於self.head，表示環狀鏈結串列目前只有一個的元素，執行「self.head = None」，環狀鏈結串列就被清空。

類別DoubleLinkedList內，使用方法len計算環狀鏈結串列的長度，示意圖如下。

此時tmp不等於self.head，執行「count = count + 1」，變數count遞增1，執行「tmp = tmp.next」，就可以把變數tmp所指向tmp的下一個元素，如下圖。

直到tmp等於head跳出迴圈，就可以計算出環狀鏈結串列的長度。

類別DoubleLinkedList內，使用方法printLinkedList從self.head印出雙向鏈結串列的每一個元素，程式碼如下。

建立好了雙向鏈結串列類別DoubleLinkedList後，首先需要新增類別DoubleLinkedList的物件，接著使用方法insertHead建立鏈結串列的第一個元素5，接著使用方法insert插入第2個以後的元素(6、7、8、9)，使用方法remove刪除元素，過程中印出雙向鏈結串列的每一個元素，程式碼如下。

4-4-1 插隊在任意位置

給定數字由1到n分別代表n個人的編號，請依照編號由小到大依序將這n個人加入排隊隊伍中，接著有m個指令，指令「s」服務目前最前面的人，輸出此人的編號，此人被服務完後會排到隊伍的最後，指令「p」表示將指定的人插入到隊伍中指定的位置，例如「p 100 2」，取出編號100的人後，插入到隊伍第2個位置，輸入的n值小於200且m值小於100。

輸入說明

輸入一個正整數n與m，表示有n個人在排隊，有m個指令等待輸入，接下來有m行，每一行都是指令，指令「s」表示顯示目前隊伍最前面的編號，並將該編號加入隊伍的最後，指令「p d1 d2」後面會接兩個數字，表示將編號d1取出來後，再插入到隊伍中d2的位置。

輸出說明

遇到指令s時，輸出隊伍中最前面的人的編號。

輸入範例

100 10

s

p 100 2

s

s

p 50 1

s

p 75 1

p 56 1

s

s

輸出範例

1

2

100

50

56

75

(a)解題想法

本題因為要從隊伍中間取出元素，並將元素插入到隊伍中任何位置，所以不適合使用陣列(Array)，最好使用鏈結串列(Linked List)插入與刪除元素。

第1到4行：類別Node用於儲存鏈結串列的節點，類別初始化方法(__init__)內宣告data用於儲存資料，data初始化為輸入參數x，指標next用於指向下一個元素，初始化為None。

第5到7行：類別LinkedList用於實作鏈結串列，定義類別初始化方法(__init__)內宣告head指向鏈結串列的第一個元素，初始化為None。

第8到9行：定義方法insertHead(self, x)，head指向鏈結串列的第一個元素x，x為方法insertHead的輸入值。

第10到22行：定義方法insertAt(self, x, pos)，在節點x插入在隊伍pos位置上。

第11到13行：設定變數tmp為self.head，變數nodex為數值x的節點，變數count為2。

第14到16行：若變數pos等於1，插入在第一個位置，設定nodex.next為tmp，設定self.head為nodex。

第17到22行：否則當變數count小於pos，表示還沒到達pos位置，設定變數tmp為tmp.next，變數count遞增1。找到位置pos後，設定nodex.next為tmp.next，設定tmp.next為nodex。

第23到33行：定義方法remove(self, x)，刪除節點x，設定變數tmp為self.head (第24行)。當變數tmp不等於None時，若tmp.data等於x，則使用break中斷迴圈。設定變數before為變數tmp，暫存上一個節點到變數before，變數tmp為tmp.next，指向下一個元素(第25到29行)。

第30到33行：若tmp等於self.head，則self.head指向self.head.next，否則before.next指向tmp.next。

第34到37行：定義方法serve，設定item為self.head，設定self.head為self.head.next，回傳item.data。

第38行：輸入n與m。

第39與40行：變數n與m轉換成整數。

第41行：設定物件li為類別LinkedList的物件。

第42行：插入元素1到鏈結串列物件li的第一個元素。

第43到44行：插入2到第2個位置，插入3第3位置，以此類推，直到插入2到n的每一個數字到鏈結串列。

第45到56行：使用迴圈執行m次，每次輸入一行到變數cmd(第46行)。若變數的第一個字元等於「s」，則呼叫方法serve取出第一個元素到變數x(第48行)，將x插入到第n個位置(第49行)，顯示x到螢幕上(第50行)，否則執行變數cmd的方法split，產生三個值到變數p、x與pos(第52行)，將變數x的字串轉換成整數(第53行)，從li中移除變數x(第54行)，將變數pos的字串轉換成整數(第55行)，呼叫方法insertAt將變數x插入到pos位置(第56行)。

(c)程式效率分析

執行第45到56行程式碼，是程式執行效率的關鍵，此程式會讀取m個指令，每個指令若是「s」需要O(n)，若是「p」，方法remove(x)與方法insertAt(x, pos)的演算法效率大約為O(n)，所以整體演算法效率大約為O(m*n)，m為輸入的指令個數，n為排隊的人數。

(d)程式結果預覽

執行結果顯示在螢幕如下。