目的
単方向リストとは何か，Pythonでの実装を通して理解を深めましょう．
この記事で実装した単方向リストは，以下のリポジトリから利用できます．
https://github.com/umihei/singlyLinkedListInPython
単方向リストとは
単方向リストの仕様
- ランダムアクセス不可
- Nodeが連結してできており，各Nodeは，次のNodeを示すポインタを持つ
- 要素は，インデックスを持たない
- Headは先頭の要素を示し，Tailは最後尾の要素を示すポインタ
- リストの長さを示すプロパティLengthをもつ
単方向リストの骨組みの実装
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の実装
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の実装例
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の実装例
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の実装例
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の実装例
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の実装例
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の実装例
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の実装例
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の実装例
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の実装例
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の実装例
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