「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#11


【出典】[「新・明解Pythonで学ぶアルゴリズムとデータ構造」](https://www.amazon.co.jp/%E6%96%B0%E3%83%BB%E6%98%8E%E8%A7%A3Python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%96%B0%E3%83%BB%E6%98%8E%E8%A7%A3%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%9F%B4%E7%94%B0%E6%9C%9B%E6%B4%8B/dp/4815603197/ref=sr_1_2?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=1BG3JS7CKMZA0&keywords=Python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0&qid=1644336329&sprefix=python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%2Caps%2C212&sr=8-2)
[前回の記事はこちら](https://qiita.com/kato_squalldeka/items/98013d7e1073ddf7747e)


3章を進めようとしたら、ハッシュ法の中に線形リストを使うものがあるみたいなので、先に8章を学ぶようにとのことでしたので急遽8章を学びます。

# 第8章 線形リスト
線形リストは、ノードと呼ばれる要素が連なってできています。
ノードはデータと後続のデータを示すポインタで構成できます。
とりあえず3章を進めるために今回、8章はさらっと流そうと思います。


さて、ここでは、線形リストに追加や削除などが行えるものを作ります。

```python:list8-1,linked_list.py
#list8-1は消してください
#線形リスト

from __future__ import annotations #アノテーション機能が本書では未実装だったため、追加しているらしい。
from typing import Any, Type

class Node: #ノードクラス
    """線形リストノードクラス"""
    
    def __init__(self, data: Any = None, next: Node = None):#pythonでは参照先を保持する機能があるため、初期化が必要になる(と捉えました。)
        """初期化"""
        self.data = data #データ 
        self.next = next #後続ポインタ
        
class LinkedList:
    """線形リストクラス"""
    
    def __init__(self) -> None:
        """初期化"""
        self.no = 0
        self.head = None
        self.current = None
        
    def __len__(self) -> int:#これによって線形リストをlen関数の引数として使うことができる
        """線形リスト上のノード数を返却する"""
        return self.no#len関数の引数としたときノード数を返す
    
    def search(self, data: Any) -> int:
        """dataと等価なノードを探索"""
        cnt = 0 #カウント(何番目のノードか示す)
        ptr = self.head #headを参照
        while ptr is not None: #ptrが空でないとき
            if ptr.data == data: #ptr.dataとdataが一致したとき
                self.current = ptr #self.currentはptrを参照する
                return cnt #cntを返す
            cnt += 1 #cntに+1して参照
            ptr = ptr.next #ptrはptr.nextを参照する(次のデータの値)
        return -1 #空だった時-1を返す
    
    def __contains__(self, data: Any) -> bool: #in演算子が適用できる
        """線形リストにdataは含まれているか"""
        return self.search(data) >= 0
    
    def add_first(self, data: Any) -> None:
        """先頭にノードを挿入"""
        ptr = self.head
        self.head = self.current = Node(data, ptr)
        self.no += 1
        
    
    def add_last(self, data: Any):
        """末尾にノードを挿入"""
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = self.current = Node(data, None)
            self.no += 1
            
    def remove_first(self) -> None:
        """先頭ノードを削除"""
        if self.head is not None:
            self.head = self.current = self.head.next
        self.no -= 1
    
    def remove_last(self):
        """末尾ノードを削除"""
        if self.head.next is None:
            self.remove_first()
        else:
            ptr = self.head
            pre = self.head
            
            while ptr.next is not None:
                pre = ptr
                ptr = ptr.next
            pre.next = None
            self.current = pre
            self.no -= 1
            
    def remove(self, p: Node) -> None:
        """ノードpを削除"""
        if self.head is not None:
            if p is self.head:
                self.remove_first()
            else:
                ptr = self.head
                
                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return
                    ptr.next = p.next
                    self.current = ptr
                    self.no -= 1
                    
    def remove_current_node(self) -> None:
        """着目ノードを削除"""
        self.remove(self.current)
    
    def clear(self) -> None:
        """全ノードを削除"""
        while self.head is not None:
            self.remove_first()
        self.current = None
        self.no = 0
        
    def next(self) -> bool:
        """着目ノードを一つ後方に進める"""
        if self.current is None or self.current.next is None:
            return False
        self.current = self.current.next
        return True
    def print_current_node(self) ->None:
        """着目ノードを表示"""
        if self.current is None:
            print('着目ノードはありません。')
        else:
            print(self.current.data)
        
    def print(self) -> None:
        """全ノードを表示"""
        ptr = self.head
        
        while ptr is not None:
            print(ptr.data)
            ptr = ptr.next
    
    def __iter__(self) -> LinkedListIterator:
        """イテレータ―を返却"""
        return LinkedListIterator(self.head)
    
class LinkedListIterator:
    """クラスLinkedListIteratorのイテレータ用クラス"""
    
    def __init__(self, head: Node):
        self.current = head
        
    def __iter__(self) -> LinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current is None:
            raise StopIteration
        else:
            data = self.current = self.current.next
            return data
```    
    




```python:list8-2
#線形リストクラスLinkedListの利用例

from enum import Enum
from Linked_list import LinkedList

Menu = Enum('Menu', ['先頭に挿入', '末尾に挿入', '先頭を削除', '末尾を削除', '着目を表示', '着目を進める', '着目を削除', '全削除', '探索', '帰属性判定', '全ノードを表示', '走査', '終了'])
#列挙型は、一意の定数値に束縛された識別名 (メンバー) の集合です。列挙型の中でメンバーの同一性を比較でき、列挙型自身でイテレートが可能です。

def select_Menu() -> Menu:
    """メニュー選択"""
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input('：'))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
lst = LinkedList()
while True:
    menu = select_Menu()
    
    if menu == Menu.先頭に挿入:
        lst.add_first(int(input('値：')))
    
    elif menu == Menu.末尾に挿入:
        lst.add_last(int(input('値：')))
    
    elif menu == Menu.先頭を削除:
        lst.remove_first()
    
    elif menu == Menu.末尾を削除:
        lst.remove_last()
        
    elif menu == Menu.着目を表示:
        lst.print_current_node()
        
    elif menu == Menu.着目を進める:
        lst.next()
        
    elif menu == Menu.着目を削除:
        lst.remove_current_node()
    
    elif menu == Menu.全削除:
        lst.clear()
        
    elif menu == Menu.探索:
        pos = lst.search(int(input('値：')))
        if pos >= 0:
            print(f':その値のデータは{pos + 1}番目にあります。')
        else:
            print('該当するデータはありません。')
        
    elif menu == Menu.帰属性判定:
        print('その値のデータは含まれま' + ('す。'if int(input('値：'))in lst else 'せん。'))
        
    elif menu == Menu.全ノードを表示: 
        lst.print()
        
    elif menu == Menu.走査:
        for e in lst:
            print(e)
    else:
        break
```
私はジュピターノートブックを使っているので、一応貼り付けてすぐ使える版もおいておきます。    

```python:一括で動かす用
#線形リスト

from __future__ import annotations
from typing import Any, Type

class Node:
    """線形リストノードクラス"""
    
    def __init__(self, data: Any = None, next: Node = None):
        """初期化"""
        self.data = data #データ
        self.next = next #後続ポインタ
        
class LinkedList:
    """線形リストクラス"""
    
    def __init__(self) -> None:
        """初期化"""
        self.no = 0
        self.head = None
        self.current = None
        
    def __len__(self) -> int:
        """線形リスト上のノード数を返却する"""
        return self.no
    
    def search(self, data: Any) -> int:
        """dataと等価なノードを探索"""
        cnt = 0
        ptr = self.head
        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1
    
    def __contains__(self, data: Any) -> bool:
        """線形リストにdataは含まれているか"""
        return self.search(data) >= 0
    
    def add_first(self, data: Any) -> None:
        """先頭にノードを挿入"""
        ptr = self.head
        self.head = self.current = Node(data, ptr)
        self.no += 1
        
        
    def add_last(self, data: Any):
        """末尾にノードを挿入"""
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = self.current = Node(data, None)
            self.no += 1
            
    def remove_first(self) -> None:
        """先頭ノードを削除"""
        if self.head is not None:
            self.head = self.current = self.head.next
        self.no -= 1
    
    def remove_last(self):
        """末尾ノードを削除"""
        if self.head.next is None:
            self.remove_first()
        else:
            ptr = self.head
            pre = self.head
            
            while ptr.next is not None:
                pre = ptr
                ptr = ptr.next
            pre.next = None
            self.current = pre
            self.no -= 1
            
    def remove(self, p: Node) -> None:
        """ノードpを削除"""
        if self.head is not None:
            if p is self.head:
                self.remove_first()
            else:
                ptr = self.head
                
                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return
                    ptr.next = p.next
                    self.current = ptr
                    self.no -= 1
                    
    def remove_current_node(self) -> None:
        """着目ノードを削除"""
        self.remove(self.current)
    
    def clear(self) -> None:
        """全ノードを削除"""
        while self.head is not None:
            self.remove_first()
        self.current = None
        self.no = 0
        
    def next(self) -> bool:
        """着目ノードを一つ後方に進める"""
        if self.current is None or self.current.next is None:
            return False
        self.current = self.current.next
        return True
    def print_current_node(self) ->None:
        """着目ノードを表示"""
        if self.current is None:
            print('着目ノードはありません。')
        else:
            print(self.current.data)
        
    def print(self) -> None:
        """全ノードを表示"""
        ptr = self.head
        
        while ptr is not None:
            print(ptr.data)
            ptr = ptr.next
    
    def __iter__(self) -> LinkedListIterator:
        """イテレータ―を返却"""
        return LinkedListIterator(self.head)
    
class LinkedListIterator:
    """クラスLinkedListIteratorのイテレータ用クラス"""
    
    def __init__(self, head: Node):
        self.current = head
        
    def __iter__(self) -> LinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current is None:
            raise StopIteration
        else:
            data = self.current = self.current.next
            return data
        
        
        
#線形リストクラスLinkedListの利用例

from enum import Enum


Menu = Enum('Menu', ['先頭に挿入', '末尾に挿入', '先頭を削除', '末尾を削除', '着目を表示', '着目を進める', '着目を削除', '全削除', '探索', '帰属性判定', '全ノードを表示', '走査', '終了'])

def select_Menu() -> Menu:
    """メニュー選択"""
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input('：'))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
lst = LinkedList()
while True:
    menu = select_Menu()
    
    if menu == Menu.先頭に挿入:
        lst.add_first(int(input('値：')))
    
    elif menu == Menu.末尾に挿入:
        lst.add_last(int(input('値：')))
    
    elif menu == Menu.先頭を削除:
        lst.remove_first()
    
    elif menu == Menu.末尾を削除:
        lst.remove_last()
        
    elif menu == Menu.着目を表示:
        lst.print_current_node()
        
    elif menu == Menu.着目を進める:
        lst.next()
        
    elif menu == Menu.着目を削除:
        lst.remove_current_node()
    
    elif menu == Menu.全削除:
        lst.clear()
        
    elif menu == Menu.探索:
        pos = lst.search(int(input('値：')))
        if pos >= 0:
            print(f':その値のデータは{pos + 1}番目にあります。')
        else:
            print('該当するデータはありません。')
        
    elif menu == Menu.帰属性判定:
        print('その値のデータは含まれま' + ('す。'if int(input('値：'))in lst else 'せん。'))
        
    elif menu == Menu.全ノードを表示: 
        lst.print()
        
    elif menu == Menu.走査:
        for e in lst:
            print(e)
    else:
        break
```
さて、なんだか、プログラミングやってるっぽいやつができてきましたね。
中身に関してはさっぱりな部分が多いので、追々解明していきたいと思います。
`__init__`←こういうやつとか、selfとかなかなかイメージがつかみづらいですね。
クラスに関しては、pythonを使いこなす山場の一つでもある気がするので、しっかり押さえたいです。

以上です。ありがとうございました。