連結リストについてまとめてみた

こんにちは、未来電子テクノロジーでインターンをしている者です（2020年1月退社）。
今回は、連結リスト（Linked list）について勉強したので、連結リストについてまとめてみました。

連結リストとは？配列（リスト）との違いは？

連結リストとは、各要素が一つ後ろや前の要素へのリンクを持っているリストのことです。
ある一つの要素にアクセスする際、配列（リスト）の場合、その要素に直接アクセスできます。
しかし、連結リストの場合は、最初の要素から順にリンクを辿ってアクセスせねばなりません。
また、配列のデータは、各要素の値だけです。
それに対し、連結リストのデータは、各要素の値に加えて、後（前）の要素へのリンクもあります。
そのため、連結リストは、同じ要素数の配列に比べてメモリを多く消費します。
しかし、要素を挿入したり削除する際、配列では後ろの要素を全てずらす必要があるのに対し、連結リストでは、その箇所のリンクを繋ぎかえるだけで済むので、時間を短縮できます。

まとめると以下の表のようになります。

	メリット	デメリット
連結リスト	要素の追加や削除にかかる時間が短い	要素へのアクセスの際に順にリンクをたどる必要あり
配列	要素を指定するだけですぐにアクセスできる	要素の追加や削除に時間がかかる

連結リストの種類

連結リストには、単方向リスト（Singly-linked-list）、双方向リスト（Doubly-linked-list）、循環リスト（Circularly-linked list）の3種類があります。
それぞれのイメージは、以下の通りです。

• 単方向リスト：各要素が一つ後の要素へのリンクを持っているリストです。
  head→3→7→4→
  コードで書くと、

class Node():
    __init__(self, data, next=None):
        self.data = data
        self.next = next

    def set_next(self, next):
        self.next = next

class SinglyLinkedList():
    __init__(self, head=None):
        self.head = head

    def append(self, data):           #最後の要素の追加
        new_node = Node(data)
        if self.head is None:         #最初の要素の追加
            self.head = new_node
            return

        last_node = get_last_node()
        last_node.next = new_node

    def pop(self):                    #最後の要素の削除
        last_node = get_last_node()
        last_node = None

    def get_last_node(self):
        last_node = self.head
        while not last_node.next is None: #最後の要素のnextはNone
            last_node = last_node.next
        return last_node

といった感じでしょうか。

• 双方向リスト：各要素が一つ後と前の要素へのリンクを持っているリストです。
  head⇄3⇄7⇄4→

• 循環リスト：各要素が一つ後の要素へのリンクを持っており、最後の要素は最初の要素へのリンクを持っているリストです。
  3→7→4
  ↑←←↓

連結リストの用語

• node：要素の値（data part）と次の要素（や前の要素）へのリンク（address part）とをセットにしたものです。
• head：連結リストの一番最初のnodeへのリンクを表します。
• tail：連結リストの一番最後のnodeで、単方向リストと双方向リストでは、次のnodeへのリンクはnullになります。

まとめ

今回は、連結リストについてまとめました。
私はまだまだプログラミング初心者ですので、間違いがあるかもしれません。
もし間違いがありましたら、修正しますので、ご指摘の方よろしくお願いいたします。