【コンピュータサイエンス入門】初心者のためのデータ構造（連結リスト）

はじめに

そもそもデータ構造とは、問題をより効率的に解決し、複雑なアルゴリズムをより理解するのに役立つためコンピュータ科学者やソフトウェア開発者にとって非常に重要です。
今回はその内の下記のような連結リストについて、なるべくわかりやすく解説していきたい思います。

（画像引用）　https://programming-place.net/ppp/contents/algorithm/image/circularlist.png

連結リスト(Linked List)とは

リスト（配列）とはデータが順番に並べられたデータ構造であり、リスト内のデータはindexを使って検索することができます。（要するにリストではデータは連続してメモリに保存されるもの）
しかしここでデータが連続して格納されるのとは対照的に登場するのが連結リストです。
要するに連結リストとは、
データが連続したメモリ上に格納されないデータ構造のことを指しています。
）

連結リストでは、個々の要素をnode(ノード)と呼びます。
各ノードに関しては通常データ要素（図では省略）とポインタが含まれています。

つまり各ノードはポインタを通して、各ノードと繋がっています
なのでポインタをたどるだけであるノードから次のノードにいくことができます。

※ポインタとは、ここでは他の変数のメモリアドレスを格納する変数として定義します。

リストは常にどこかから始めないといけません。なので、連結リストの最初のノードは先頭、最後のノードを末尾と言います。

また次のノードにリンクされなくなったらそこにNULLを入れ、連結リストを終了させます。

配列と連結リストについて

配列と連結リストなら、どっちがいいの？という方もいるかも知れません。筆者自身も配列と連結リストどちらを使うか迷ったことがあります。
ただ、個人的意見としては、個人開発なら配列によるデータ構造で全然OKだと思います。
ただポートフォリオ作成等で自分のできることを表現したい場合などに用いてみるには大変有効的な手法だと思います。

アルゴリズム実装

class Node:
    def __init__():
    self.data = data
    self.next = None # このnextが上記の「ポインタ」にあたります　初期ではnullを入れます。
class LinkedList:
    def __init__(self, node):
        self.head = node # 先頭を定義します。上記でいうメモリアドレス2020のノードを指します。
# インスタンス化
#　この時点ではイメージ的には個々のnodeがバラバラに存在するイメージ
node1 = Node(1)
node2 = Node(32)
node3 = Node(4545)

#ここでLinkedlistをインスタンス化させ、各nodeを繋げていきます
#上記の図の各四角（node）に矢印を追加していくイメージ
numlist = Linkedlist(node1)
numlist.head.next = node2 
numlist.head.next.next = node3

#全てのnodeを繋げれましたので、これらを反復して表現していきます。

#適当な変数にheadを格納し、そこからwhileでnullになるまで追跡していくやり方
currentNode = numlist.head
while currentNode != None:
    # ここはdataをつける。print(currentNode)だけだとメモリアドレスが出力される（nextは値ではなくポインタのため）
    print(currentNode.data, end = )
    currentNode = currentNode.next

出力結果は

1
32
4545

となるはずです。

こんな形で追跡していくことができます。なので、配列のようにfor分を活用してたどるのではなく、
whileを使ってnullのところまで走らせるイメージで大丈夫だと思います。

静的型付け言語を見てみると各変数が何を表しているのか少しだけわかりやすいのではないかと思いますので、静的型付け言語でも記述しておきます。

class Node {
    public int data;
    public Node next;

    public Node (int data) {
        this.data = data;
    }
}

class SinglyLinkedList () {
    public Node head;

    public SinglyLinkedList (Node head) {
        this.head = head;
    }
}

class Main {
    public static void main (String[] args) {
        Node node1 = new Node(4);
        Node node2 = new Node(65);
        Node node3 = new Node(5);

        SinglyLinkedList numList = new SinglyLinkedList(node1);

        numList.head.next = node2;
        numList.head.next.next = node3;

        Node currentNode = numList.head;

        while (currentNode != null) [
            System.out.println(currentNode.data);
            currentNode = currentNode.next;
        ]
    }
}

最後に

いかがだったでしょうか？本当に簡単になんですけど、データ構造入門として連結リストに関して説明いたしました。
次回からqueueやstackなども解説していきたいなと考えております。
見ていただき大変ありがとうございました。