データ構造とアルゴリズム(リンクリスト) 単方向リンク

単方向リンク

画像のように、データを一列に持っているデータ構造で、リンクの一番後ろにデータをどんどん追加したり、一番最初にデータを追加したりということを行う。

appendでデータ構造の一番後ろに新しくNodeを追加できるようにしている。 insertではデータのHEADに新しいNodeを追加できるようにしている。

append

def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        # last_node.nextでどんどんノードを後ろにみていき.nextがfalseになったら
        # それ以上ノードがないということなので、そこで新しくデータを追加する
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

new_node = Node(data) - ここで追加したい数字をNodeクラスのインスタンスとしてインスタンス化する - if self.head is None:self.headがなかったらデータ構造の中に何もないということなのでデータをHEADに追加して終了(return) - それ以外の場合はwhile last_node.next:の部分でlast_node(self.head)の次に何もデータがないかどうかをみていき、データがなければnew_node_を.nextで最後に追加してあげるようにする。

insert

# こちらは単純に一番頭に新しいnew_nodeを追加する
    def insert(self, data: Any) -> None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node  

これはあまり複雑ではなく、新しくデータが入力されたらNodeインスタンスを作成してそれをnew_nodeという変数に置き換える。self.headをnew_nodeの次に配置して、self.head = new_nodeで一番最初にnew_nodeを入れてあげるとinsertが完了する

remove

def remove(self, data: Any) -> None:
      current_node = self.head
      if current_node and current_node.data == data:
        self.head = current_node.next
        current_node = None
        return
      
      previous_node = None
      while current_node and current_node.data != data:
        previous_node = current_node
        current_node = current_node.next

      if current_node is None:
        return 

      previous_node.next = current_node.next
      current_node = None

これがわりと複雑。。。

current_node = self.head
if current_node and current_node.data == data:
self.head = current_node.next
current_node = None
return

まずこの部分。 self.headをcurrent_nodeとして、current_nodeがなければそのまま終了なのでreturn そして、current_node.data = data => current_node(head)が削除対象データであれば、self.head = current_node.nextでheadを上書きすることでheadが消える。

※この時点で読んでいて気付いたのだが、nextでデータをどのように持つかということは、配列として全ての要素がどこにあるか管理しているわけではなくて、それぞれのデータが自分の次のデータの要素がなんであるかという情報を持っているのでそれで.nextが使えるというわけか 上の理由からself.head = current_node.nextとするとself.headが次のデータで置き換えられるので、それ以降は置き換えられたself.headのデータは見れなくなる。

ということはcurrent_node = current_node.nextでもいいのかな？

先頭にあるものが、削除対象であればそのまま削除する。そして、データがなければ削除するデータそのものがないのでその時点で終了する。

  previous_node = None
  while current_node and current_node.data != data:
    previous_node = current_node
    current_node = current_node.next
    
  if current_node is None:
    return 

  previous_node.next = current_node.next
  current_node = None

次にこの部分。

previous_nodeで一個前のノードを保存していく while current_node and current_node.data != data: current_nodeに値が存在していて、かつ、そのデータがremove対象のデータでなければwhileを続けていく。 （ここでは、current_node.dataをどんどん右側に遡っていき、削除対象のデータにぶつかるまでリニアーサーチみたいな感じで探していく。）

current_node.data != data:の部分が引っ掛かったらwhileループは抜けるので current_nodeには削除対象のデータが入っており、previous_nodeにはcurrent_nodeのひとつ前のデータが入っている状況になる。

そこで、previous_node.next = current_node.nextとしてあげることで、[3, 4, 5] => [3, 4, 5] => [3, 4]のような形で、削除対象のデータがcurrent_node.nextで上書きされるのでデータ構造からデータがremoveされる。

from __future__ import annotations
from typing import Any

class Node(object):
    def __init__(self, data: Any, next_node: Node = None):
        self.data = data
        self.next = next_node # next_nodeにはNode自信を入れる。
    
class LinkedList(object):
    def __init__(self, head=None) -> None:
        self.head = head

    def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        # last_node.nextでどんどんノードを後ろにみていき.nextがfalseになったらそれ以上ノードがないということなので、そこで新しくデータを追加する
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
    
    # こちらは単純に一番頭に新しいnew_nodeを追加する
    def insert(self, data: Any) -> None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node  
      
    def print(self) -> None:
      current_node = self.head
      while current_node:
        print(current_node.data)
        current_node = current_node.next

    def remove(self, data: Any) -> None:
      current_node = self.head
      if current_node and current_node.data == data:
        self.head = current_node.next
        current_node = None
        return
      
      previous_node = None
      while current_node and current_node.data != data:
        previous_node = current_node
        current_node = current_node.next

      if current_node is None:
        return 

      previous_node.next = current_node.next
      current_node = None


l = LinkedList()
l.append(1)
l.append(2)
l.append(3)
l.insert(0)
l.print()
l.remove(2)
print('#######################')
l.print()
# print(l.head.data)
# print(l.head.next.data)
# print(l.head.next.next.data)
# print(l.head.next.next.next.data)

0
1
2
3
#######################
0
1
3