Algorithmためのデータ構造をPythonで実現しましょう。ーその3[linked list unorderedの実現]

タイトルの通り、今回はLinked list unorderedというData structureはpythonでどのように実現するのかを見ていきます。

linked list unorderedはなに？

今回はunordered、要するに順番に並ぶではなく、好きな場所で、数値の大きさと関係なく、自由に並んでいるLinked listのこと。

じゃLinked listはなんでしょう？
図で見てみます！

左の感じと右の感じを合わせて、Linked listと呼ばれています。

では、早速Linked list unorderedの要素を確認しましょう！

• Linked listには箱みたいなものがありまして、それはNodeと呼ばれます。
  • Nodeには保存されているデータ(値)と次のNodeを連結するための情報が含まれています。
  • 次のNodeを連結するための情報はNoneの場合、今の指しているNodeが最後となります。
• Head はLinked listの始まり(入口)で、EndはLinked listの最後を指します。

それほど難しく考えなくてもいいので、まとめると：
Linked listはNodeという箱は必須で、Nodeにはまた値と次のNodeに連結するための情報が含まれています。

Pythonで実現しよう！

class Node(object):
    def __init__(self, init_data):
        self.init_data = init_data
        self.next_data = None

    def getData(self):
        return self.init_data

    def getNext(self):
        return self.next_data

    def setData(self, new_data):
        self.init_data = new_data

    def setNext(self, new_Next_data):
        self.next_data = new_Next_data

class unorderedList(object):
    def __init__(self):
        self.head = None

    # insert data
    def insert(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    # calculate size
    @property
    def size(self):
        current_node = self.head
        count = 0
        while current_node:
            count += 1
            current_node = current_node.getNext()
        return count

    # search data
    def search(self, target):
        current_node = self.head
        found = False
        while current_node and not found:
            if current_node.getData() == target:
                found = True
            else:
                current_node = current_node.getNext()
        return found

    # remove data
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

remove methodについてちょっと補足します。
ある特定のNodeを削除したい場合、特定されたNodeの一個前のNodeを特定された一個後ろのNodeに関係を構築するば良いです。

では実物化してみます。(日本語は多分実物化かな...間違いたらごめん)

obj = unorderedList()
obj.insert(5)
obj.insert(8)
obj.insert(2)
obj.insert(11)
obj.insert(4)
print(obj.size)
print(obj.head.getData())
print(obj.remove(2))
print(obj.search(4))
print(obj.size)

出力>>>

5
4
None
True
4

うまくできました！5個の数値をlinked listに追加し、一個removeした後、4個の数値は残されました。