pythonで単方向リストを実装

## 目的
単方向リストとは何か，Pythonでの実装を通して理解を深めましょう．
この記事で実装した単方向リストは，以下のリポジトリから利用できます．
https://github.com/umihei/singlyLinkedListInPython

## 単方向リストとは
### 単方向リストの仕様
- ランダムアクセス不可
- Nodeが連結してできており，各Nodeは，次のNodeを示すポインタを持つ
- 要素は，インデックスを持たない
- Headは先頭の要素を示し，Tailは最後尾の要素を示すポインタ
- リストの長さを示すプロパティLengthをもつ

![singlyLinkedList](https://miro.medium.com/max/953/1*elJncKhH_P9oQglfI1aVQA.png)

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

```python
class SinglyLinkedList:

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

## 単方向リストの計算量，利点など
単方向リストは，先頭や末尾の要素のInsertionについては，O(1)の計算量です．
これが，listとの違いです．listは，先頭や末尾の要素が付け加わると，それぞれの要素に振られているインデックスを再計算する（re-index）必要があるため，たとえ先頭の要素の挿入であっても，O(N)の計算量となります．
Removalについては，先頭の要素であれば，O(1),それ以外はO(N)の計算量となります．先頭の要素の場合は，それを削除するとき，Headを付け替えるだけで済むからです．先頭でない要素の場合は，その要素までイテレーションをする必要がありますから，O(N)の計算量となります．
同様に，検索や要素へのアクセスはO(N)となります．
したがって，単方向リストは，先頭の要素に対する挿入や削除の操作が頻繁に要求されるケースにおいて，最適な選択肢です．
ただし，利用する際には，単方向リストそれ自体はインデックスが組み込まれていないことに留意しましょう．
また，単方向リストのような，Nodeで構成されるデータ構造は，スタックやキューといった他のデータ構造を理解する上での基礎となります．
これよりあとは，Pythonを使って単方向リストというデータ構造を実装しながら，PushやGetといった操作への理解を深め，それぞれの操作の計算量の肌感覚を掴みましょう．

## Nodeの仕様と実装

Nodeの仕様
- Nodeは次のNodeを示すポインタをもつ
- Nodeは値をもつ

Nodeの実装

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

## pushの仕様と実装
Pushは，リストの後尾に値を追加するメソッドです．
### Pushの仕様
- 値を受け取る
- 受け取った値で新しいNodeを作る
- Headプロパティが存在しないとき，HeadとTailを新しいNodeにする
- そうでないときは，TailのNextプロパティを新しいNodeにし，Tailプロパティを新しいNodeにする（※）
- リストの長さをインクリメントする
- 作ったリストを返す

※
TailのNextプロパティを新しいNodeにする　→ 今現在のTailのNextを新しいNodeに向けることで，新しいNodeと既存のNodeを結合する
ステップバイステップで書くと以下のようになる．

```
H = Head, T = Tail

1. 初期状態
４　→ ６　→ ８
H          T

2. 新しいNodeをつくる
４　→ ６　→ ８　２
H          T

3. 今のTailのNextを新しいNodeにする
４　→ ６　→ ８　→ ２
H          T

4. Tailを新しいNodeにする
４　→ ６　→ ８　→ ２
H               T
```

### Pushの実装例

```python
class SinglyLinkedList:

    def push(self, val):
        newNode = Node(val)

        if(not self.head):
            self.head = newNode
            self.tail = newNode

        else:

            self.tail.next = newNode
            self.tail = newNode

        self.length = self.length + 1

        return self
```

## Traversalの仕様と実装
Traversalは，単方向リストを走査するためのメソッドです．リストの内容を出力するために作成します．
### Traversalの仕様
- Headを変数（current）に格納する
- current.valを出力する．currentをcurrent.nextで更新する．currentがNoneになるまで続ける．

Traversalとは，ここでは，英語で，走査という意味です．

### Traversalの実装例

```python
class SinglyLinkedList:

    def traversal(self):
        current = self.head
        while(current):
            print(current.val)
            current = current.next
```

## Popの仕様と実装
Popは末尾の値を取り除きます．
### Popの仕様
- Nodeがひとつもなければ，Noneを返す
- Tailまでリストを走査する
- 最後のNodeの１つまえのNodeのNextプロパティをNoneにする
- Tailを最後のNodeのひとつまえのNodeにする
- Lengthをデクリメントする
- 取り除いたNodeを返す

```
H = Head, T = Tail

1. 初期状態
４　→ ６　→ ８　→ ２
H               T

2. 最後のNodeのひとつまえのNodeのNextプロパティをNoneにする
４　→ ６　→ ８　　２
H          　　　T

3. Tailを最後のひとつまえのNodeにする
４　→ ６　→ ８　 ２
H          T
```

### Popの実装例

```python
class SinglyLinkedList:

    def pop(self):

        if(not self.head):
            return None

        current = self.head
        newTail = current
        while(current.next):
            newTail = current
            current = current.next
        
        self.tail = newTail
        self.tail.next = None
        self.length = self.length + 1
        if (self.length == 0):
            self.head = None
            self.tail = None

        return current

```

nTとCの動きのステップバイステップ

```
H = Head, T = Tail
nT = newTail, c = current

1. 初期状態
４　→ ６　→ ８　→ ２
H               T
nT                
c

2. whileループがひとつすすむと，
４　→ ６　→ ８　→ ２
H               T
nT              
　　　c

3. whileループが終了した状態
４　→ ６　→ ８　→ ２
H               T
　　　　　　nT              
　　　　　　　　　　c

4. TailをNewTailにする
４　→ ６　→ ８　→ ２
H         T
　　　　　　nT              
　　　　　　　　　　c

5. TailのNextをNoneにする
４　→ ６　→ ８　　 ２
H         T
　　　　　　nT              
　　　　　　　　　　c
```

## Shiftの仕様と実装
Shiftは，先頭の要素を取り除きます．
### Shiftの仕様
- Nodeがひとつもなければ，Noneを返す
- 現在のHeadを変数（current）に格納する
- HeadプロパティをcurrentのNextプロパティに設定する
- Lengthをデクリメントする
- 取り除いたNodeを返す

```
H = Head, T = Tail, c = current

1. Headを変数Currentに格納する
４　→ ６　→ ８　→ ２
H               T                
c

2. 変数CurrentのNextプロパティをHeadにする
４　 ６　→ ８　→ ２
　　　H          T              
c
```

### Shiftの実装例

```python
def shift(self):

        if(not self.head):
            return None

        current = self.head
        self.head = current.next
        self.length = self.length - 1
        if(self.length == 0):
            self.tail = None

        return current
```

## Unshiftの仕様と実装
Unshiftは，先頭に要素を追加します．
### Unshiftの仕様
- 値を受け取る
- 受け取った値で新しいNodeをつくる
- Headプロパティがリストになければ，HeadとTailを新しいNodeにする
- そうでなければ，新しく作ったNodeのNextプロパティを現在のHeadにする
- Headプロパティを新しく作ったNodeにする
- Lengthをインクリメントする
- リストを返す

```
H = Head, T = Tail

1. 初期状態
４　→ ６　→ ８　→ ２
H               T                

２. 新しいNodeをつくる
１　　４　→ ６　→ ８　→ ２
　　　H　              T 

３.新しいNodeのNextを今のHeadにする 
１ →　４　→ ６　→ ８　→ ２
　　　 H　             T 

4.Headプロパティを新しく作ったNodeにする
１ →　４　→ ６　→ ８　→ ２
H      　             T
```

### Unshiftの実装例

```python
def unshift(self, val):

        newNode = Node(val)

        if(not self.head):
            self.head = newNode
            self.tail = newNode

        else:
            newNode.next = self.head
            self.head = newNode

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

## Getの仕様と実装
Getは指定されたインデックスの値を返します
### Getの仕様
- メソッドはインデックスを受け取ります
- インデックスが０より小さいまたはLengthと等しいかそれより大きいとき，Noneを返します
- リストを与えられたインデックスのNodeまで走査し，そのノードを返します

### Getの実装例

```python
def get(self, index):
        if ((index < 0) or (index >= self.length)):
            return None
        counter = 0
        current = self.head
        while(counter != index):
            current = current.next
            counter = counter + 1

        return current
```

## Set
Setは指定されたインデックスのNodeに値を設定します．
### Setの仕様
- メソッドは，値とインデックスを受け取ります
- Getメソッドを用いて指定されたNodeを見つけます
- Nodeが見つからなかった場合は，Falseを返します
- Nodeが見つかった場合は，Nodeの値を受け取った値にして，Trueを返します．


### Setの実装例

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

## Insert
Insertは特定の位置にNodeを挿入します．
### Insertの仕様
- メソッドは，値とインデックスを受け取ります
- インデックスが，０より小さいか，Lengthよりも大きいときはFalseを返します
- インデックスがLengthと同じときは，新しいノードを末尾にPushします．
- インデックスが０のときは，新しいノードをリストの先頭にUnshiftします．
- そうでないときは，Getメソッドをつかい，受け取ったインデックスよりもひとつ若いインデックスのノードにアクセスします
- そのNodeのNextプロパティを新しいNodeにします
- 新しいNodeのNextプロパティを先ほど発見したNodeのもともとのNextプロパティに設定されていたNodeにします
- Lengthをインクリメントします
- Trueを返します

```
H = Head, T = Tail
index = 2, val = 7

1. 初期状態
４　→ ６　→ ８　→ ２
H               T                

２. 新しいNodeをつくる
４　→ ６　→ ８　→ ２
H　      7       T 

３.(index - 1)のNodeのNextプロパティを新しいノードにします 
４　→ ６ →　7   ８　→ ２
H　                  T 

4.新しいNodeのNextを，（index -1)のNodeが持っていたNextと同じものにします
４　→ ６ →　7 →  ８　→ ２
H　                   T 
```

### Insertの実装例

```python
def insert(self, index, val):
        if ((index < 0) or (index > self.length)):
            return False

        elif (index == self.length):
            return bool(self.push(val))

        elif (index == 0):
            return bool(self.unshift(val))

        else:
            newNode = Node(val)
            backNode = self.get(index - 1)
            frontNode = backNode.next
            backNode.next = newNode
            newNode.next = frontNode
            return True
```

## Remove
Removeは特定のインデックスのNodeを取り除きます．
### Removeの仕様
- メソッドはインデックスを受け取ります．
- インデックスが０より小さいか，Lengthと同じまたは，よりも大きい場合，Noneを返します
- インデックスが，Lengthと同じ場合，Popメソッドを使います
- インデックスが，0の場合，Shiftメソッドを使います
- そうでなければ，Getメソッドを使い，受け取ったインデックスよりひとつ若いインデックスのNodeにアクセスします．
- そのNodeのNextプロパティを，そのNodeの次の次のNodeにします
- Lengthをデクリメントします
- 取り除いたNodeを返します

### Removeの実装例

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

        elif (index == (self.length - 1)):
            return self.pop()

        elif (index == 0):
            return self.shift()

        else:
            backNode = self.get(index - 1)
            targetNode = backNode.next
            backNode.next = targetNode.next
            self.length = self.length - 1
            return targetNode
```

## Reverse
Reverseは，リストを逆転させます．
### Reverseの仕様
- HeadとTailを入れ替えます
- Nextという変数を用意します
- Prevという変数を用意します
- Nodeという変数を用意し，それをHeadプロパティで初期化します
- リストを走査して以下を繰り返します
- NodeのNextプロパティをNext変数に格納します
- Prev変数に今走査しているNodeをいれます
- Nodeをひとつ進めます
- NodeのNextプロパティをPrevで置き換えます

```
H = Head, T = Tail

1. 初期状態
４　→ ６　→ ８　→ ２
H               T                

２. HとTを入れ替える
４　→ ６　→ ８　→ ２
T　              H 

３.ループで，左端から順番にNodeの参照する向きを逆にしていく
next = node.next 
４　← ６ →　８　→ ２
T　              H
no   ne

node.next = prev (prevの初期値はNone）
４　  ６ →　８　→ ２
T　              H
no   ne

prev = node
４　  ６ →　８　→ ２
T　              H
no   ne
p

node = next
４　  ６ →　８　→ ２
T　              H
     no
p    ne

next = node.next
４　  ６ →　８　→ ２
T　              H
     no
p          ne

node.next = prev　（ここでNodeの向きが変わる）
４　← ６ 　　８　→ ２
T　              H
     no
p          ne

prev = node
４　← ６ 　　８　→ ２
T　              H
     no
     p     ne

node = next
４　← ６ →　８　→ ２
T　              H
           no
     p     ne

next = node.next
４　← ６ →　８　→ ２
T　              H
           no
     p          ne

node.next = prev
４　← ６ ←　８　　 ２
T　              H
           no
     p          ne

prev = node
４　← ６ ←　８　→ ２
T　              H
           no
           p    ne

node = next
４　← ６ ←　８　→ ２
T　              H
                no
           p    ne

next = node.next
４　← ６ ←　８　→ ２
T　              H
                no
           p    (ne = None)

node.next = prev
４　← ６ ←　８　← ２
T　              H
                no
           p    (ne = None)

prev = node
４　← ６ ←　８　← ２
T　              H
                no
                p    (ne = None)

node = next
４　← ６ ←　８　← ２
T　              H
                (no = None)
                p    (ne = None)


4.ループが最後まで回ったあと
４　← ６ ←　８　← ２
T　              H
```

### Reverseの実装例

```python
def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node
        next = None
        prev = None
        for ii in range(0, self.length - 1):
            next = node.next
            node.next = prev
            prev = node
            node = next

        return self
```