# [資演] 7-Linked List (IV): Doubly Linked List 上的操作
###### tags: `資演`
## 創建一個 doubly linked list
比起前面的singly linked list，doubly linked list的每一個節點都多了一個`prev`屬性，用來儲存前一個節點的位址。如此一來，在巡訪時不僅可以向後巡訪，也可以向前巡訪。


因此，用於創建doubly linked list的節點和DoublyLinkedList類別可以設計如下：

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

要創建一個只有一個節點的Doubly linked list，首先，我們必須先建立一個空的`DoublyLinkedList`物件，這個物件含有兩個屬性：`head`和`tail`。接著，我們建立一個空節點。因為這個`DoublyLinkedList`只有一個節點，我們必須將該節點的`prev`和`next`都設為`None`。接著，我們將先前建立的`DoublyLinkedList`物件的`head`和`tail`都設為該節點。如此一來便完成了一個只有一個節點的`DoublyLinkedList`物件的創建。

::: spoiler 如此我們便可以在DoublyLinkedList類別實作create方法。（試試看！）

class CircularLinkedList:
...

def create(self, nodeValue):
node = Node(nodeValue)
node.prev = None
node.next = None
self.head = node
self.tail = node

:::

## Doubly linked list 的插入操作
和singly linked list類似地，我們可以畫出插入操作的流程圖：

::: spoiler 並在DoublyLinkedList類別實作insert方法。（試試看！）

class CircularLinkedList:
...

def insert(self, nodeValue, location):
newNode = Node(nodeValue)
if self.head is None:
self.head = newNode
self.tail = newNode
else:
if location == 0:
newNode.prev = None
newNode.next = self.head
self.head.prev = newNode
self.head = newNode
else:
tempNode = self.head
index = 0
while index < location - 1:
tempNode = tempNode.next
index += 1
newNode.next = tempNode.next
newNode.prev = tempNode
newNode.next.prev = newNode
tempNode.next = newNode
:::

## 巡訪 doubly linked list
Doubly linked list 的巡訪和singly linked list的完全相同，故在此不再重複介紹。

## 反向巡訪 doubly linked list
因為每個節點都有`prev`這個屬性，所以我們可以連到前一個節點，這樣就可以從`tail`出發，進行反向巡訪了。
:::spoiler 其實作也和一般的巡訪非常類似，只是方向完全相反。

def reverse_traversal(self):
if self.head is None:
print("The list is empty.")
else:
tempNode = self.tail
while tempNode:
print(tempNode.value)
tempNode = tempNode.prev

:::

## Doubly linked list 的刪除操作
和前面一樣，我們可以畫出刪除操作的流程圖：
:::spoiler 程式碼實作
def deleteNode(self,location):
if self.head is None:
print("There is not any element in DLL")
else:
if location == 0:
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
else:
curNode = self.head
index = 0
while index < location - 1:
curNode = curNode.next
index += 1
curNode.next = curNode.next.next
curNode.next.prev = curNode
:::

## 例題
* [把一個doubly linked list的順序倒過來](https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem)
:::spoiler 解答
最直覺的方式就是把所有的prev和next顛倒過來，再對head和tail作適當的處理。

def reverse(head):
curr = new_head = head
while curr:
curr.prev, curr.next = curr.next, curr.prev
new_head = curr
curr = curr.prev
return new_head
:::
* [插入一個已排序好的doubly linked list](https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/problem)
給定一個已經由小到大排序好的doubly linked list的head，我們想要寫一個函式，這個函式可以把一個新的值`insertVal`插入這個已經排序好的doubly linked list裡面，並且讓它保持為一個排序好的doubly linked list。如果給定的是一個空的list，則創建一個新的doubly linked list，並回傳那個插入的節點。

:::spoiler 解答
這題非常簡單，只要一直next直到找到比給定的`insertVal`大的元素，並插入在那個元素之前就好。

def SortedInsert(head, data):
node = Node(data,None,None)
if (head == None):
return node
elif (data < head.data):
node.next = head
head.prev = node
return node
else:
node = SortedInsert(head.next, data)
head.next = node
node.prev = head
return head
:::