線形リストは2種類の格納形式に分けられます：順序格納と連結格納

順序格納：

順序格納では、線形リストのノードは論理順に連続したアドレスのメモリ領域に格納されます。この方法で格納された線形リストを順序リストと呼びます。2つの特徴があります：1. 論理順序と物理順序が一致している；2. データ要素間の関係はコンピュータ内での「物理的な位置の隣接」によって表現されます。順序リストの各要素のデータ型が同じであると仮定し、n個のメモリ領域が必要で、各要素がL個のメモリ領域を占めるとします。最初の要素が占めるメモリアドレスをデータ要素の開始位置として、順序リストのi+1番目のデータ要素の格納位置Loc(i+1)とi番目のデータ要素の格納位置Loc(i)は以下の関係を満たします：Loc(i+1)=Loc(i)+L。

1. 順序リストの初期化：

def __init__(self, max_size):
    self.max_size = max_size    # 順序リストの最大容量
    self.current_size = 0    
    self.elements = [None for _ in range(self.max_size)]
    
# seq_list = SequentialList(100) のように、100がmax_sizeに渡されます

2. インデックスによる要素の検索：

def get_element(self, index):
    # 指定されたインデックスの要素を取得
    if index < 0 or index >= self.current_size:
       raise IndexError('インデックスが不正です')
    else:
       return self.elements[index]

3. インデックス位置の要素の更新：

def set_element(self, index, value):
   if index < 0 or index >= self.current_size:
       raise IndexError('インデックスが不正です')
   else:
       self.elements[index] = value

4. 順序リストが空かどうかの判定：

def is_empty(self):
    return self.current_size == 0

5. リストの末尾に要素を追加：

def add_element(self, value):
   if self.current_size == self.max_size:
      return False
   else:
      self.elements[self.current_size] = value
      self.current_size += 1
      return True

6. 順序リストの任意の位置に要素を挿入：

'''まずインデックスが有効かどうかを確認し、無効であれば例外を投げます。
有効であれば、インデックス位置およびそれ以降の要素を一つ後ろに移動し、
インデックス位置に要素を追加します。実装は以下の通りです：'''
def insert_element(self, index, value):
    if index < 0 or index > self.current_size:
       raise IndexError('インデックスが不正です')
    if index == self.current_size:  # インデックスがリストの末尾の場合
       self.add_element(value)
    else:
       # 要素を後ろにずらすためのスペースを作成
       self.elements.append(None)
       # 後ろから前に向かって要素を一つずつ後ろに移動
       for i in range(self.current_size, index, -1):
            self.elements[i] = self.elements[i-1]
       # 新しい要素を挿入
       self.elements[index] = value
       self.current_size += 1
    return self.elements

7. リストの末尾要素の削除：

def remove_last(self):
    if self.is_empty():
       return None
    self.current_size -= 1
    # 最後の要素を削除
    last_element = self.elements[self.current_size]
    self.elements = self.elements[:self.current_size]
    return last_element

ヒント：深いコピーと浅いコピー

不変オブジェクト：ほとんどのPython組み込みデータ型：数値、文字列、タプル
ID以外の状態は変更される可能性があります。可変オブジェクト：リスト、セット、辞書

lst = []
print("変更前のID:", id(lst))
 
lst.append(132)
print("変更後のID:", id(lst))
print(lst)

# 出力されるIDは同じです

num = 1
print("変更前のID:", id(num))
 
num = 4
print("変更後のID:", id(num))  # IDが変わっているため、データの変更は元のメモリ上ではなく、
                              # 新しくメモリを確保して新しい値を保存していることを示します
print(num)

# 出力されるIDは異なります

深いコピーと浅いコピー：

original = [1,2,3]
shallow_copy = original
shallow_copy[0] = 8
print(shallow_copy)
'''ここでshallow_copyも[8,2,3]になっていることがわかります。
なぜなら「shallow_copy = original」は浅いコピーであり、新しいメモリ領域を割り当てていないため、
shallow_copyが指すアドレスの内容を変更することと同じだからです'''

import copy
deep_copy = copy.deepcopy(original)
deep_copy[0] = 9
print(deep_copy)
'''
ここでoriginalがdeep_copyの変更によって変わっていないことがわかります。
なぜならdeepcopyは深いコピーであり、deep_copy用に新しいメモリ領域を確保しているからです
'''

8. 任意の位置の要素の削除：

def delete_element(self, index):
   if self.is_empty() or index >= self.current_size:
       raise IndexError('インデックスが不正です')
   # 削除された要素を返す
   deleted_element = self.elements[index]
   # 削除位置以降の要素を前に詰める
   for i in range(index, self.current_size - 1):
       self.elements[i] = self.elements[i+1]
   self.current_size -= 1
   return deleted_element

9. 順序リストの長さの取得：

def get_length(self):
    return self.current_size

10. 順序リストを走査して各要素を表示：

def traverse(self):
    for element in self.elements[:self.current_size]:
        print(element)

順序リストの実装例：

#!/usr/bin/python3
# 線形リストは順序リストと連結リストに分けられます

# 順序リストの実装
class SequentialList:
    def __init__(self):
        self.elements = []

    def check_empty(self):
        if len(self.elements) == 0:
            print('空です')
        else:
            print('空ではありません')

    def create_list(self, size):
        if len(self.elements) == 0:
           for i in range(0, size):
                self.elements.append(i)
        return self.elements

    def get_length(self):
        return len(self.elements)

    def insert_at(self, position, element):
        length = len(self.elements)
        # スペースを確保するために一時的に要素を追加
        self.elements.append(None)
        # 後ろから前に向かって要素を移動
        for j in range(length, position, -1):
            self.elements[j] = self.elements[j-1]
        # 新しい要素を挿入
        self.elements[position] = element
        print(f'位置 {position} に要素 {element} を挿入しました')
        return self.elements

    def delete_at(self, position):
        length = len(self.elements)
        # 削除される要素を保存
        deleted = self.elements[position]
        # 削除位置以降の要素を前に詰める
        for j in range(position, length - 1):
            self.elements[j] = self.elements[j+1]
        # リストの最後の要素を削除
        self.elements.pop()
        return self.elements, deleted

    def create_sample(self):
        self.elements.append('apple')
        self.elements.append('banana')

    def find_element(self, target):
        for i in range(0, len(self.elements)):
            if self.elements[i] == target:
                print(f'見つかりました。インデックス: {i}')


if __name__ == "__main__":  # インポート時に実行されないように保護
    my_list = SequentialList()
    my_list.create_sample()
    print(my_list.insert_at(0, 'pear'))
    my_list.find_element('apple')