# # リスト構造 # - [Gist](https://gist.github.com/Cartman0/3ebb2e2669fa8da0daa0b92a6e1c577e) # - [nbviewer](http://nbviewer.jupyter.org/gist/Cartman0/3ebb2e2669fa8da0daa0b92a6e1c577e) # ## 単方向リスト # ポインタには次のセルの場所が位置付けられていて， # 一方向にだけたどるリスト構造． # # 特徴： # データの挿入，追加，削除がポインタ変更によって容易． # # 最後のセルはデータのみ持ち，ポインタはどこも指さない． # # # ``` # データアドレス次のポインタ # 30 (先頭セル) 50 # ↓ # 50 70 # ↓ # 70 110 # ↓ # 110 90 # ↓ # 90 NULL # ``` # # Fig.単方向リストのイメージ図 # ### 実装メモ # #### データの追加（add操作） # add操作： # ここでは，最後尾にデータを追加する． # # 線形リストの最後のセルを求めて，最後のセルの次のポインタに新しいセルを追加する． # # データが増えるたびに，最後尾まで求める必要があるので， # 処理量が増えていく． # # # - リストが空の場合：先頭ポインタを新しいセルへ更新する． # # ``` # Head -> newCell # ``` # # - それ以外 # # 最後尾のセルを求めて，最後尾のセルの次のポインタを新しいセルにする． # # ``` # Head -> Cell(1) -> Cell(2) -- -> Cell(n) -> newCell # ``` # # 参考 # - 平成26年応用情報処理技術者 p.79 # #### データの挿入（insert操作） # insert操作： # # 任意のindexを指定して，そこに新しいセルを挿入する． # # - 先頭へ挿入する場合 # # 「新しいセルの次ポインタ」に元々の先頭ポインタのセルを追加し， # 「先頭ポインタ」を新しいセルへ更新する． # # ``` # old Head -> Cell(1) -> Cell(2) -- -> Cell(n) # new Head -> newCell -> Cell(1) -> Cell(2) -- -> Cell(n) # ``` # # - indexへ挿入する場合： i-1番目のセルとi番目のセルを求めて， # - 「i-1番目のセルの次ポインタ」に新しいセルを指定． # - 「新しいセルの次ポインタ」にi番目のセルを指定 # # ``` # old Head -> Cell(1) --> Cell(i-1) -> Cell(i) -- -> Cell(n) # new Head -> Cell(1) --> Cell(i-1) -> newCell -> Cell(i) -- -> Cell(n) # ``` # # 参考 # - 平成26年応用情報処理技術者 p.79 # #### データの削除の場合（delete操作） # - 先頭を削除：Headを「先頭セルの次ポインタ」にする．先頭セルを削除する． # # ``` # old Head -> Cell(1) -> Cell(2) -> -- -> Cell(n) # new Head -> Cell(2) -> -- -> Cell(n) # del Cell(1) # ``` # # - i番目を削除： # 「i-1番目のセルの次ポインタ」をi+1番目のセルにする． # i番目のセルを削除する． # # ``` # old Head -> Cell(1) -> Cell(2) -> --> Cell(i-1) -> Cell(i) -> Cell(i+1) -- -> Cell(n) # new Head -> Cell(1) -> Cell(2) -> --> Cell(i-1) -> Cell(i+1) -- -> Cell(n) # del Cell(i) # ``` # # #### 単方向リストのcode # In[7]: class Cell: """ cell of one-way list """ def __init__(self, data): # コンストラクタ self.data = data self.next_pointer = None class OnewayList: ''' ''' def __init__(self): # コンストラクタ self.head = None def last(self): cell = self.head # 空の時 if not cell: return None # 空でないとき while not cell.next_pointer == None: # 次のポインタが空になるまで cell = cell.next_pointer return cell def get_index_cell(self, index): ''' if index=0, return head ''' cell = self.head for i in range(index): cell = cell.next_pointer return cell def add(self, data): added_cell = Cell(data) last_cell = self.last() if not last_cell: self.head = added_cell else: last_cell.next_pointer = added_cell def insert(self, index, data): ''' ''' added_cell = Cell(data) # 先頭へ追加する場合 if index == 0: added_cell.next_pointer = self.head self.head = added_cell return # indexへ追加する場合 if index > 0: pre_cell = self.get_index_cell(index-1) next_cell = pre_cell.next_pointer pre_cell.next_pointer = added_cell added_cell.next_pointer = next_cell def del_head(self): head_cell = self.head self.head = head_cell.next_pointer del head_cell def delete(self, index): ''' 削除対象がnullでない前提 ''' if index == 0: self.del_head() return if index > 0: pre_cell = self.get_index_cell(index-1) del_target_cell = pre_cell.next_pointer next_cell = del_target_cell.next_pointer pre_cell.next_pointer = next_cell del del_target_cell def to_list(self): cell = self.head arr = [] # 空でないとき while not cell == None: arr.append(cell.data) # 次のポインタが空になるまで cell = cell.next_pointer return arr def print(self): cell = self.head # 空でないとき while not cell == None: print(cell.data) cell = cell.next_pointer # In[12]: one_l = OnewayList() one_l.add(1) one_l.add(2) one_l.add(3) one_l.print() # In[13]: one_l.insert(0, 4) one_l.insert(2, 5) one_l.insert(5, 6) one_l.print() # In[14]: one_l.del_head() one_l.print() # In[15]: one_l.delete(0) one_l.print() # In[16]: one_l.delete(1) one_l.print() # In[17]: one_l.delete(2) one_l.print() # In[18]: one_l.to_list() # 参考： # # http://www.ced.is.utsunomiya-u.ac.jp/lecture/2011/prog/p2/kadai2/3_list_1.php # ## 双方向リスト(Doubly Linked List) # 平成22年基本情報技術者 p.133 # # 前のセルへのポインタと次のセルへのポインタといった2つのポインタを持たせ，前後に自由にリストを辿れる． # # 最後のセルは前のポインタのみ持っている． # # # ``` # データアドレスポインタ # 30 (先頭セル) pre:Null next:50 # ↑ ↓ # 50 pre:30 next:70 # ↑ ↓ # 70 pre:50 next:110 # ↑ ↓ # 110 pre:70 next:90 # ↓ ↓ # 90 pre:110 next:NULL # ``` # # Fig. 双方向リストのイメージ図 # ### 実装メモ # #### データを末尾へ追加（addLast） # addLast # # - 空の場合： # HeadとTailは，新しいセルを指すようにする． # # ``` # Head -> newCell <- Tail # ``` # # - 空でない場合： # (1)「元のTailのセルの次ポインタ」を新しいセルにする． # (2) Tailを新しいセルへ更新する． # # ``` # old: Head -> Cell1 <- Tail # new: Head -> Cell1 -> (1)newCell <- (2)Tail # ``` # #### データを先頭へ追加（addFirst） # addFirst:先頭へ追加 # # - 空の場合：`addLast`と同じ． # # ``` # Head -> newCell <- Tail # ``` # # - 空でない場合： # # (1)「元のHeadのセルの前ポインタ」を新しいセルにする． # (2) Headを新しいセルへ更新する． # # ``` # old: Head -> Cell1 <- Tail # # -> # new: Head(2) -> newCell Cell1 -> Tail # (1) <- # ``` # #### データの挿入 insert() # index目に挿入 # # - 先頭に挿入：addFirst # # - 末尾に挿入：addLast # # - index目に挿入： # # (1): index-1番目のセルと新しいセルを連結． # (2): 新しいセルとindex番目のセルを連結． # # ``` # --> -> # old: Head -> Cell1 Cell(i-1) Cell(i) <- Tail # <-- <- # # --> -> -> # old: Head -> Cell1 Cell(i-1) (1) newCell (2) Cell(i) <- Tail # <-- <- <- # ``` # #### 先頭データの削除 deleteFirst # deleteFirst:先頭データの削除 # # (1)先頭セルから「2番目のセルの前ポインタ」をNULLへ # (2)Headは2番目のセルを指すようにする． # (3)先頭セルの削除 # # ``` # -> # old: Head -> Cell1 Cell2 <- Tail # <- # # new: Head (2) -> Cell2 <- Tail # (1)NULL <- # (3) del Cell1 # ``` # #### 末尾データの削除(deleteLast) # (1)末尾セルから「2番目のセルの次ポインタ」をNULLへ # (2)Tailは2番目のセルを指すようにする． # (3)末尾セルの削除 # # ``` # --> -> # old: Head -> Cell1 Cell(n-1) Cell(n) <- Tail # <-- <- # --> # new: Head -> Cell1 Cell(n-1) <- (2) Tail # <-- -> (1)NULL # (3) del Cell(n) # ``` # #### データの削除 delete # データの削除 delete：任意のindexのデータを削除 # # - 先頭の場合：deleteFirst # - 末尾の場合：deleteLast # - それ以外： # # (1)「i-1番目のセル」と「i+1番目のセル」を連結． # (2) i番目のセルを削除する． # # ``` # --> -> -> # old Head -> Cell(1) Cell(i-1) Cell(i) Cell(i+1) -- -> Cell(n) <- Tail # <-- <- <- # # --> -> # new Head -> Cell(1) Cell(i-1) (1) Cell(i+1) -- -> Cell(n) # <-- <- # (2)del Cell(i) # ``` # # #### 双方向リストのcode # In[19]: class DoubleCell: """ cell of doubly-lnked list """ def __init__(self, data): # コンストラクタ self.data = data self.pre_pointer = None self.next_pointer = None class DoublyLinkedList: ''' ''' def __init__(self): # コンストラクタ self.head = None self.tail = None def get_index_cell(self, index): ''' index=0:return head ''' cell = self.head for i in range(index): cell = cell.next_pointer return cell def _update_doubly_linked_2cells(self, pre_cell, next_cell): pre_cell.next_pointer = next_cell next_cell.pre_pointer = pre_cell def _add_init(self, cell): self.tail = cell # update list.tail self.head = cell # update list.head def addLast(self, data): added_cell = DoubleCell(data) # 空の場合 if (not self.head) and (not self.tail): self._add_init(added_cell) return # not empty self._update_doubly_linked_2cells(self.tail, added_cell) self.tail = added_cell # update list.tail def addFirst(self, data): added_cell = DoubleCell(data) # 空の場合 if (not self.head) and (not self.tail): self._add_init(added_cell) return # not empty self._update_doubly_linked_2cells(added_cell, self.head) self.head = added_cell # update list.head def insert(self, index, data): ''' ''' added_cell = DoubleCell(data) # 先頭へ追加する場合 if index == 0: self.addFirst(data) return # index目に挿入 if index > 0: pre_cell = self.get_index_cell(index-1) # 最後に追加する場合 if pre_cell == self.tail: self.addLast(data) return # index目に挿入 next_cell = pre_cell.next_pointer self._update_doubly_linked_2cells(pre_cell, added_cell) self._update_doubly_linked_2cells(added_cell, next_cell) def deleteFirst(self): head_cell = self.head second_cell = head_cell.next_pointer if not second_cell == None: second_cell.pre_pointer = None self.head = second_cell del head_cell def deleteLast(self): last_cell = self.tail second_cell = last_cell.pre_pointer if not second_cell == None: second_cell.next_pointer = None self.tail = second_cell del last_cell def delete(self, index): ''' 削除対象がnullでない前提 ''' # 先頭の削除 if index == 0: self.deleteFirst() return # delete cell[index] if index > 0: pre_cell = self.get_index_cell(index-1) del_target_cell = pre_cell.next_pointer # 末尾の削除 if del_target_cell == self.tail: self.deleteLast() return # delete cell[index] next_cell = del_target_cell.next_pointer self._update_doubly_linked_2cells(pre_cell, next_cell) del del_target_cell def to_list(self): cell = self.head arr = [] # 空でないとき while not cell == None: arr.append(cell.data) # 次のポインタが空になるまで cell = cell.next_pointer return arr def print(self): cell = self.head # 空でないとき while not cell == None: print(cell.data) cell = cell.next_pointer def print_reverse(self): cell = self.tail # 空でないとき while not cell == None: print(cell.data) cell = cell.pre_pointer # In[20]: doubly_l = DoublyLinkedList() doubly_l.addLast(1) doubly_l.addFirst(2) doubly_l.addLast(3) doubly_l.print() print() doubly_l.print_reverse() # In[21]: doubly_l.insert(0, 4) doubly_l.insert(1, 5) doubly_l.insert(2, 6) doubly_l.insert(6, 7) doubly_l.print() print() doubly_l.print_reverse() # In[22]: doubly_l.deleteFirst() doubly_l.print() print() doubly_l.print_reverse() # In[23]: doubly_l.deleteLast() doubly_l.print() print() doubly_l.print_reverse() # In[24]: doubly_l.delete(0) doubly_l.delete(2) doubly_l.delete(1) doubly_l.print() print() doubly_l.print_reverse() # In[25]: doubly_l.to_list() # 参考 # # - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp # ## 循環リスト # 前へのポインタ，次へポインタといった2つのポインタを持ったリスト # # 双方向リストとの違いは，最後のセルの次ポインタに戦闘データのセルのアドレスを持つ． # 感情に連結したリストになる． # # ``` # データアドレスポインタ # 30 (先頭ポインタ) pre:Null next:50 # ↑ ↓ # 50 pre:30 next:70 # ↑ ↓ # 70 pre:50 next:110 # ↑ ↓ # 110 pre:70 next:90 # ↓ ↓ # 90 pre:110 next:30 # ``` # ### 実装メモ # 基本は，双方向リストと同じ． # # HeadとTailの更新があったとき，Tailのセルの次ポインタをHeadのセルに変更する． # #### データを末尾へ追加（addLast） # データを末尾へ追加（addLast）： # # 新しいデータが末尾へ来るので，次ポインタを先頭セルへ更新する． # # ``` # old: Head -> Cell1 <- Tail # # new: -> -> # Head -> Cell1 Cell2 newCell <- Tail # | -> -> | # |------------------- # ``` # # #### データを先頭へ追加（addFirst） # 新しいデータが先頭になるので，末尾セルの次ポインタを先頭セルへ更新する． # # ``` # old: Head -> Cell1 <- Tail # # new: -> -> # Head -> newCell Cell1 Cell2 <- Tail # | <- <- | # |-------------------- # ``` # #### データの先頭を削除 deleteFirst() # 先頭セルが2番目のセルに変わるので，末尾セルの次ポインタを2番目のセルへ変更する． # # ``` # -> -> # old: Head -> Cell1 Cell2 Cell3 <- Tail # | <- <- | # -------------------- # # -> # new: Head -> Cell2 Cell3 <- Tail # | <- | # <-------- # del Cell1 # ``` # #### データの末尾を削除(deleteLast()) # 末尾セルが（後ろから）2番目のセルに変わるので，2番目のセルの次ポインタを先頭セルへ変更する． # # ``` # --> -> # old: Head -> Cell1 Cell(n-1) Cell(n) <- Tail # | <-- <- | # ------------------------- # # --> # new: Head -> Cell1 Cell(n-1) <- Tail # | <-- | # <---------- # del Cell(n) # ``` # #### 循環リストのcode # In[28]: class DoubleCell: """ cell of doubly-lnked list """ def __init__(self, data): # コンストラクタ self.data = data self.pre_pointer = None self.next_pointer = None class CircularList: ''' ''' def __init__(self): # コンストラクタ self.head = None self.tail = None def get_index_cell(self, index): ''' if index=0, return head ''' cell = self.head for i in range(index): cell = cell.next_pointer return cell def _update_doubly_linked_2cells(self, pre_cell, next_cell): pre_cell.next_pointer = next_cell next_cell.pre_pointer = pre_cell def _add_init(self, cell): self.tail = cell # update list.tail self.head = cell # update list.head cell.next_pointer = self.head # update chain def addLast(self, data): added_cell = DoubleCell(data) # 空の場合 if (not self.head) and (not self.tail): self._add_init(added_cell) return # not empty self._update_doubly_linked_2cells(self.tail, added_cell) self.tail = added_cell # update list.tail self.tail.next_pointer = self.head # update chain def addFirst(self, data): added_cell = DoubleCell(data) # 空の場合 if (not self.head) and (not self.tail): self._add_init(added_cell) return # not empty self._update_doubly_linked_2cells(added_cell, self.head) self.head = added_cell # update list.head self.tail.next_pointer = self.head # update chain def insert(self, index, data): ''' ''' added_cell = DoubleCell(data) # 先頭へ追加する場合 if index == 0: self.addFirst(data) return # index目に挿入 if index > 0: pre_cell = self.get_index_cell(index-1) # 最後に追加する場合 if pre_cell == self.tail: self.addLast(data) return # index目に挿入 next_cell = pre_cell.next_pointer self._update_doubly_linked_2cells(pre_cell, added_cell) self._update_doubly_linked_2cells(added_cell, next_cell) def deleteFirst(self): head_cell = self.head second_cell = head_cell.next_pointer self.head = second_cell if not second_cell == None: second_cell.pre_pointer = None self.tail.next_pointer = self.head # update chain del head_cell def deleteLast(self): last_cell = self.tail second_cell = last_cell.pre_pointer self.tail = second_cell if not self.tail == None: self.tail.next_pointer = self.head # update chain del last_cell def delete(self, index): ''' 削除対象がnullでない前提 ''' # 先頭の削除 if index == 0: self.deleteFirst() return # delete cell[index] if index > 0: pre_cell = self.get_index_cell(index-1) del_target_cell = pre_cell.next_pointer # 末尾の削除 if del_target_cell == self.tail: self.deleteLast() return # delete cell[index] next_cell = del_target_cell.next_pointer self._update_doubly_linked_2cells(pre_cell, next_cell) del del_target_cell def to_list(self): cell = self.head last_cell = self.tail arr = [] # 空でないとき while not cell == last_cell: arr.append(cell.data) # 次のポインタが空になるまで cell = cell.next_pointer arr.append(cell.data) return arr def print(self): cell = self.head last_cell = self.tail # 空でないとき while not cell == last_cell: print(cell.data) cell = cell.next_pointer print(cell.data) def print_reverse(self): cell = self.tail first_cell = self.head # 空でないとき while not cell == first_cell: print(cell.data) cell = cell.pre_pointer print(cell.data) def trace(self, n): cell = self.head for i in range(n): print(cell.data) cell = cell.next_pointer # In[29]: circular_l = CircularList() circular_l.addLast(1) circular_l.addFirst(2) circular_l.addLast(3) circular_l.print() print() circular_l.print_reverse() # In[30]: circular_l.insert(0, 4) circular_l.insert(1, 5) circular_l.insert(2, 6) circular_l.insert(6, 7) circular_l.print() print() circular_l.print_reverse() # In[31]: circular_l.deleteFirst() circular_l.print() print() circular_l.print_reverse() # In[32]: circular_l.deleteLast() circular_l.print() print() circular_l.print_reverse() # In[33]: circular_l.delete(0) circular_l.delete(2) circular_l.delete(1) circular_l.print() print() circular_l.print_reverse() # In[34]: circular_l.trace(5)