pythonで双方向リスト

## 目的
双方向リストとは何か，Pythonでの実装を通して理解を深めましょう．
この記事で実装した双方向リストは，以下のリポジトリから利用できます．
(TBU)

## 双方向リストとは

### 双方向リストの仕様
- ランダムアクセス不可
- Nodeが連結してできており，各Nodeは，次のNodeを示すポインタと，**前のNodeを示すポインタ**を持つ
- Headは先頭の要素を示すポインタ，Tailは末尾の要素を示すポインタである
- リストの長さを表すLengthプロパティをもつ

![doublyLinkedList](https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/03/DLL1.png)

### 双方向リストの各種メソッドの計算量
先頭，末尾の要素に対するInsertion，RemovalはO(1)となります．SinglyLinkedListは，末尾の要素の削除はO(N)でしたから，それにくらべると，計算量小さいです．Searching，AccessはO(N)となります．Technicalには，探すインデックスがLengthの半分より大きいか小さいかで場合を分けるので，計算量はO(N/2)ですが，以前としてO(N)のオーダにとどまります．
双方向リストは，単方向リストに比べ，Previousのポインタを持つことで便利になっています．Searchingは半分の時間で行うことが可能です．しかしながら，Previousポインタをもつことにより，メモリの使用量は増します．

### 双方向リストの骨組みの実装例

```python
class Node:
    def __init__(self, val):
        val = self.val
        next = None
        prev = None

class DoublyLinkedList:
    def __init__(self):
        head = None
        tail = None
        length = 0
```

## Push

- 新しいNodeをつくる
- HeadプロパティがNoneであるならば，HeadとTailを新しく作ったNodeにする
- そうでないならば，TailのNextプロパティを新しく作ったNodeにする
- 新しく作ったNodeのPrevプロパティを元のTailにする
- Lengthをインクリメントする
- リスト全体を返す

```python
    def push(self,val):
        newNode = Node(val)
        if (not self.head):
            self.head = newNode
            self.tail = self.head
        else:
            self.tail.next = newNode
            newNode.prev = self.tail
            self.tail = newNode

        self.length = self.length + 1
        return self
```

## Pop

- Headが存在しなければ，Noneを返す
- のちに返却するため，現在のTailを変数に保存する
- Lengthが１のとき，HeadとTailをNoneにする
- TailをひとつまえのNodeにする
- 新しいTailのNextをNoneにする
- Lengthをデクリメントする
- 取り除いたNodeを返す

```python
    def pop(self):
        if(not self.head):
            return None

        currentTail = self.tail
        if (self.length == 1):
            self.tail = None
            self.head = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
            currentTail.prev = None

        self.length = self.length - 1
        return currentTail
```

## shift

- lengthが０ならば，Noneをかえす
- 現在のHeadを変数に保存する（OldHead）
- Lengthが１のとき，HeadをNoneにし，TailをNoneにする
- HeadをOldHeadのNextにする
- Legthをデクリメントする
- 取り除いたNodeを返す

```python
    def shift(self):
        if (self.length == 0):
            return None
        oldHead = self.head
        if (self.length == 1):
            self.head = None
            self.tail = None
        else:
            self.head = oldHead.next

        self.length = self.length - 1
        return oldHead
```

## unshift

- 受け取った値でNodeをつくる
- もし，Lengthが０ならば，Headを新しいNodeにし，Tailも新しいNodeにする
- HeadのPrevを新しいNodeにする
- 新しいNodeのNextをHeadにむける
- Headを新しいNodeにする
- Lengthをインクリメントする
- リストを返却する

```python
    def unshift(self, val):
        newNode = Node(val)
        if (self.length == 0):
            self.head = newNode
            self.tail = newNode
        else:
            self.head.prev = newNode
            newNode.next = self.head
            self.head = newNode
        self.length = self.length + 1
        return self
```

## get

- インデックスが０より小さいか，Lengthと等しいまたはより大きい場合，Noneを返す
- インデックスがLengthの半分よりも小さいまたは等しい場合，Headからリストを順にたどり，指定されたインデックスのNodeを返す
- インデックスがLengthの半分よりも大きい場合，Tailからリストを順にたどり，指定されたインデックスのNodeを返す

```python
    def get(self, index):
        if ((index < 0) or (index > self.length)):
            return None

        halfOfLength = self.length // 2
        if (index <= halfOfLength):
            counter = 0
            current = self.head
            while(counter != index):
                current = current.next
                counter = counter + 1
            return current
        elif (index > halfOfLength):
            counter = self.length - 1
            current = self.tail
            while(counter != index):
                current = current.prev
                counter = counter - 1
            return current
```
## set

- 受け取ったインデックスのGetメソッドの結果を変数に格納する
- 結果がValidであれば，受け取った値をそのNodeのValueとする
- Trueをかえす
- そうでなければFalseを返す

```python
    def set(self, index, val):
        targetNode = self.get(index)
        if(targetNode):
            targetNode.val = val
            return True
        else:
            return False
```

## insert

- インデックスが０より小さいか，Lengthより大きい場合，Falseを返す
- インデックスが０のとき，Unshiftする
- インデックスがLengthと同じ時，Pushする
- 受け取ったインデックスより１小さいNodeをGetメソッドで得る
- 受け取った値でNodeをつくる
- index - 1のNodeのNextを新しいNodeにし，新しいNodeのPrevをindex - 1のNodeにする．index + 1のNodeのPrevを新しいNodeにし，新しいNodeのNextをindex + 1のNodeにする
- Lengthをインクリメントし，Trueを返す

```python
    def insert(self, index, val):
        if((index < 0) or (index > self.length)):
            return False
        if (index == 0):
            self.unshift(val)
        if (index == self.length):
            self.push(val)
        prevNode = self.get(index - 1)
        newNode = Node(val)
        nextNode = prevNode.next
        prevNode.next = newNode
        newNode.prev = prevNode
        nextNode.prev = newNode
        newNode.next = nextNode
        self.length = self.length + 1

        return True
```

## remove

- indexが０より小さいか，Lengthより大きいか，Lengthとおなじ時はNoneを返す
- Indexが０ならば，Shiftする
- IndexがLength-1と等しいならば，Popする
- とりのぞくNodeをGetメソッドを使って得る
- 見つかったNodeのNextをひとつまえのNodeのNextにし，PrevをひとつあとのNodeのPrevにする
- 見つかったNodeのNextとPrevをNoneにする
- Lengthをデクリメントする
- 取り除いたNodeを返す

```python
    def remove(self, index):
        if((index < 0) or (index >= self.length)):
            return None
        if (index == 0):
            self.shift()
        if (index == self.length - 1):
            self.pop()
        removedNode = self.get(index)
        removedNode.prev.next = removedNode.next
        removedNode.next.prev = removedNode.prev
        removedNode.next = None
        removedNode.prev = None

        self.length = self.length - 1
        return removedNode
```


## reverse

- リストのHeadとTailを入れ替える
- リストを走査し，各NodeのNextをPrevに，PrevをNextに置き換える

```python
    def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node

        tmpPrev = None
        tmpNext = None
        while(node):
            tmpPrev = node.prev
            tmpNext = node.next
            node.next = tmpPrev
            node.prev = tmpNext
            node = node.prev

        return self
```