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

【出典】[「新・明解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/6c3b8f5c67f459318673)

# 8-3カーソルによる線形リスト
前回で学習した線形リストは「ノードの挿入や削除を、データの移動を伴わずに行える」という特徴があったようで…。(学習不足感)
挿入や削除のたびにノード用インスタンスの生成とは気が内部的に行われるため、記憶域の確保・解放に要するコストは決して小さくないのだとか…。(記憶域の確保とか解放とかいまいちわからないですが…。)
今回学ぶカーソルによる線形リストは、後続ポインタ(ノード内のnextに当たるところ)を後続ノードが格納されている要素の添字とします。ここでは、添字によってあらわすポインタのことをカーソルと呼びます。

ポインタ式(前回)の線形リストでは、追加削除を行う際には、データを詰めるような動作がありましたが、カーソル式ではフリーリスト(削除した部分のリスト)を生成して対応します。
詳しく理解はできていないのですが、ポインタ式で詰めたりする作業があったのに対して、カーソル式ではリストを生成する(別で記録する？)ため、詰める分の計算量が減るといったところでしょうか。

さて、今回も前回と同じようなシステムのプログラムを組むようです。

```python:list8-3,array_list.py
#線形リスト(配列カーソル版)

from __future__ import annotations
from typing import Any, Type

Null = -1

class Node:
    """線形リスト用ノードクラス(配当カーソル版)"""
    
    def __init__(self, data = Null, next = Null, dnext = Null):
        """初期化"""
        self.data = data #データ
        self.next = next #リストの後続ポインタ
        self.dnext = dnext #フリーリストの後続ポインタ
        
class ArrayLinkedList:
    """線形リストクラス(配列クラス)"""
    
    def __init__(self, capacity: int):
        """初期化"""
        self.head = Null #先頭ノード
        self.current = Null #着目ノード
        self.max = Null #利用中の末尾レコード
        self.deleted = Null #フリーリストの先頭ノード
        self.capacity = capacity #リストの容量
        self.n = [Node()] * self.capacity #リスト本体
        self.no = 0
        
    def __len__(self) -> int:
        """線形リスト上のノード数を返却する"""
        return self.no
    
    def get_insert_index(self):
        """次に挿入するレコードの添字を求める"""
        if self.deleted == Null:
            if self.max < self.capacity:
                self.max += 1
                return self.max
            else:
                return Null
        else:
            rec = self.deleted
            self.deleted = self.n[rec].dnext
            return rec
    
    def delete_index(self, idx: int) -> None:
        """レコードidxをフリーリストに登録"""
        if self.deleted == Null:
            self.deleted = idx
            self.n[idx].dnext = Null
        else:
            rec = self.deleted
            self.deleted = idx
            self.n[rec].dnext = rec
    
    def search(self, data: Any) -> int:
        """dataと等価なノードを探索"""
        cnt = 0
        ptr = self.head
        while ptr != Null:
            if self.n[ptr].data ==data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = self.n[ptr].next
        return Null
    
    def __contains__(self, data: Any) -> bool:
        """線形リストにデータは含まれているか"""
        return selff.search(data) >= 0
    
    def add_first(self, data: Any):
        """先頭にノードを挿入"""
        ptr = self.head
        rec = self.get_insert_index()
        if rec != Null:
            self.head = self.current = rec
            self.n[self.head] = Node(data, ptr)
            self.no += 1
    
    def add_last(self, data: Any) -> None:
        """末尾にノードを挿入"""
        if self.head == Null:
            self.add_first(data)
        else:
            ptr = self.head
            while self.n[ptr].next != Null:
                ptr = self.n[ptr].next
            rec = self.get_insert_index()
            if rec != Null:
                self.n[ptr].next = self.current = rec
                self.n[rec] = Node(data)
                self.no += 1
                
    def remove_first(self) -> None:
        """先頭ノードを削除"""
        if self.head != Null:
            ptr = self.n[self.head].next
            self.delete_index(self.head)
            self.head = self.current = ptr
            self.no -= 1
    
    def remove_last(self) -> None:
        """末尾ノードを削除"""
        if self.head != Null:
            if self.n[self.head].next == Null:
                self.remove_first()
            else:
                ptr = self.head
                pre = self.head
                while self.n[ptr].next != Null:
                    pre = ptr
                    ptr = self.n[ptr].next
                self.n[pre].next = Null
                self.delete_index(pre)
                self.current = pre
                self.no -= 1
                
    def remove(self, p: int) -> None:
        """レコードpを削除"""
        if self.head != Null:
            if p == self.head:
                self.remove_first()
            else:
                ptr = self.head
                while self.n[ptr].next != p:
                    ptr = self.n[ptr].next
                    if ptr == Null:
                        return
                self.n[ptr].next = Null
                self.delete_index(ptr)
                self.n[ptr].next = self.n[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 != Null:
            self.remove_first()
        self.current = Null
    
    def next(self) -> bool:
        """着目ノードを一つ後方に進める"""
        if self.current == Null or self.n[self.current].next == Null:
            return False
        self.current = self.n[self.current].next
        return True
    
    def print_current_node(self) -> None:
        """着目ノードを表示"""
        if self.current == Null:
            print("""着目ノードはありません""")
        else:
            print(self.n[self.current].data)
        
    def print(self) -> None:
        """全ノードを表示"""
        ptr = self.head
        
        while ptr != Null:
            print(self.n[ptr].data)
            ptr = self.n[ptr].next
            
    def dump(self) -> None:
        """配列をダンプ"""
        for i in self.n:
            print(f'[{i}]{i.data}{i.next}{i.dnext}')
    
    def __iter__(self) -> ArrayLinkedListIterator:
        """イテレータを返却"""
        return ArrayLinkedListIterator(self.n, self.head)
    
class ArrayLinkedListIterator:
    """クラスArrayLinkedListIteratorのイテレータ用クラス"""
    
    def __init__(self, n: int, head: int):
        self.n = n
        self.current = head
        
    def __iter__(self) -> ArrayLinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current == Null:
            raise StopIteration
        else:
            data = self.n[self.current].data
            self.current = self.n[self.current].next
            return data
```

```python:list8-4,array_list_test.py

#配列版線形リストクラスArrayLinkedListの利用例

from enum import Enum
from array_list import ArrayLinkedList

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 = ArrayLinkedList(100)

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
```

|**コラム8-2　論理演算子**|
|-|

今まで、andなどの演算子について深く考えて使ったことはなかったのですが、どうやら、真偽判定が行われているようですね。
（そもそも演算子だったことを意識していませんでした。）
確かに、プログラムなので何かしらの真偽判定が行われているんですよね…。(逆を言えば真偽の作り方をマスターするといろいろ考えれる幅が増えそうですね。)

ちなみに優先順位があるようで　not>and>or　の順らしいです。

さて、and,or,notについて次のようにまとめられていたのでご参考までに

and演算子

|x|y|x and y|
|-|-|-|
|真|真|y（真）|
|真|偽|y（偽）|
|偽|真|x（偽）|
|偽|偽|x（偽）|



or演算子

|x|y|x or y|
|-|-|-|
|真|真|x（真）|
|真|偽|x（真）|
|偽|真|y（真）|
|偽|偽|y（偽）|

こちらも偽が連続したときは

not演算子

|x|not x|
|-|-|
|真|False|
|偽|True|


#おまけ

```python:8-3,8-4を統合したものです。
#線形リスト(配列カーソル版)

from __future__ import annotations
from typing import Any, Type

Null = -1

class Node:
    """線形リスト用ノードクラス(配当カーソル版)"""
    
    def __init__(self, data = Null, next = Null, dnext = Null):
        """初期化"""
        self.data = data #データ
        self.next = next #リストの後続ポインタ
        self.dnext = dnext #フリーリストの後続ポインタ
        
class ArrayLinkedList:
    """線形リストクラス(配列クラス)"""
    
    def __init__(self, capacity: int):
        """初期化"""
        self.head = Null #先頭ノード
        self.current = Null #着目ノード
        self.max = Null #利用中の末尾レコード
        self.deleted = Null #フリーリストの先頭ノード
        self.capacity = capacity #リストの容量
        self.n = [Node()] * self.capacity #リスト本体
        self.no = 0
        
    def __len__(self) -> int:
        """線形リスト上のノード数を返却する"""
        return self.no
    
    def get_insert_index(self):
        """次に挿入するレコードの添字を求める"""
        if self.deleted == Null:
            if self.max < self.capacity:
                self.max += 1
                return self.max
            else:
                return Null
        else:
            rec = self.deleted
            self.deleted = self.n[rec].dnext
            return rec
    
    def delete_index(self, idx: int) -> None:
        """レコードidxをフリーリストに登録"""
        if self.deleted == Null:
            self.deleted = idx
            self.n[idx].dnext = Null
        else:
            rec = self.deleted
            self.deleted = idx
            self.n[rec].dnext = rec
    
    def search(self, data: Any) -> int:
        """dataと等価なノードを探索"""
        cnt = 0
        ptr = self.head
        while ptr != Null:
            if self.n[ptr].data ==data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = self.n[ptr].next
        return Null
    
    def __contains__(self, data: Any) -> bool:
        """線形リストにデータは含まれているか"""
        return selff.search(data) >= 0
    
    def add_first(self, data: Any):
        """先頭にノードを挿入"""
        ptr = self.head
        rec = self.get_insert_index()
        if rec != Null:
            self.head = self.current = rec
            self.n[self.head] = Node(data, ptr)
            self.no += 1
    
    def add_last(self, data: Any) -> None:
        """末尾にノードを挿入"""
        if self.head == Null:
            self.add_first(data)
        else:
            ptr = self.head
            while self.n[ptr].next != Null:
                ptr = self.n[ptr].next
            rec = self.get_insert_index()
            if rec != Null:
                self.n[ptr].next = self.current = rec
                self.n[rec] = Node(data)
                self.no += 1
                
    def remove_first(self) -> None:
        """先頭ノードを削除"""
        if self.head != Null:
            ptr = self.n[self.head].next
            self.delete_index(self.head)
            self.head = self.current = ptr
            self.no -= 1
    
    def remove_last(self) -> None:
        """末尾ノードを削除"""
        if self.head != Null:
            if self.n[self.head].next == Null:
                self.remove_first()
            else:
                ptr = self.head
                pre = self.head
                while self.n[ptr].next != Null:
                    pre = ptr
                    ptr = self.n[ptr].next
                self.n[pre].next = Null
                self.delete_index(pre)
                self.current = pre
                self.no -= 1
                
    def remove(self, p: int) -> None:
        """レコードpを削除"""
        if self.head != Null:
            if p == self.head:
                self.remove_first()
            else:
                ptr = self.head
                while self.n[ptr].next != p:
                    ptr = self.n[ptr].next
                    if ptr == Null:
                        return
                self.n[ptr].next = Null
                self.delete_index(ptr)
                self.n[ptr].next = self.n[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 != Null:
            self.remove_first()
        self.current = Null
    
    def next(self) -> bool:
        """着目ノードを一つ後方に進める"""
        if self.current == Null or self.n[self.current].next == Null:
            return False
        self.current = self.n[self.current].next
        return True
    
    def print_current_node(self) -> None:
        """着目ノードを表示"""
        if self.current == Null:
            print("""着目ノードはありません""")
        else:
            print(self.n[self.current].data)
        
    def print(self) -> None:
        """全ノードを表示"""
        ptr = self.head
        
        while ptr != Null:
            print(self.n[ptr].data)
            ptr = self.n[ptr].next
            
    def dump(self) -> None:
        """配列をダンプ"""
        for i in self.n:
            print(f'[{i}]{i.data}{i.next}{i.dnext}')
    
    def __iter__(self) -> ArrayLinkedListIterator:
        """イテレータを返却"""
        return ArrayLinkedListIterator(self.n, self.head)
    
class ArrayLinkedListIterator:
    """クラスArrayLinkedListIteratorのイテレータ用クラス"""
    
    def __init__(self, n: int, head: int):
        self.n = n
        self.current = head
        
    def __iter__(self) -> ArrayLinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current == Null:
            raise StopIteration
        else:
            data = self.n[self.current].data
            self.current = self.n[self.current].next
            return data
        
#配列版線形リストクラスArrayLinkedListの利用例

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 = ArrayLinkedList(100)

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
```