データ構造 - 連結リストについて

はじめに

コンピュータプログラムにおいて、データを効率的に扱うことは非常に重要です。そのためには、適切なデータ構造を選択することが不可欠です。
今回は、その中でも特に連結リストというデータ構造について詳しく解説していきます。

データ構造とは

データ構造とは、コンピュータ上でデータを効率的に格納し、組織化するための手法や方法のことです。
データを効率的に操作し、必要な情報を素早く取り出すためには、適切なデータ構造を選択する必要があります。

連結リストとは

多くのプログラマーが馴染みのある配列は、リスト内のすべての要素をインデックスを使って管理するデータ構造です。
一方、連結リストは、データがメモリ上の連続したブロックに格納されないという点が特徴です。

連結リストでは、各要素をノードと呼び、ノードにはデータと次のノードへの参照が格納されています。
この参照をたどることで、あるノードから次のノードへと順々にアクセスすることができます。

片方向リスト

連結リストの中でも最も基本的な形態の一つです。
各ノードはデータを格納する変数と、次のノードを指すポインタ変数から構成されています。
次のノードを指すポインタは、リストの最後尾に達した場合には null 値を格納するか、空のリストを指すこともあります。
以下に簡単な画像とソースコード(TypeScript)を記します。

class Item {
    data: number;
    next: Item | null;

    constructor(data: number) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    head: Item;

    constructor(item: Item) {
        this.head = item;
    }
}

let item1: Item = new Item(7);
let item2: Item = new Item(99);
let item3: Item = new Item(45);

item1.next = item2;
item1.next.next = item3;

let numList: SinglyLinkedList = new SinglyLinkedList(item1);

let currentItem: Item | null = numList.head;
while(currentItem !== null) {
    console.log(currentItem.data);
    currentItem = currentItem.next;
}

双方向リスト

連結リストの一つで、双方向の走査を可能にするものです。
双方向リストでは、各ノードはデータを格納する変数と、次のノードを指すポインタ変数だけでなく、前のノードを指すポインタ変数も含んでいます。
このため、リストを順方向と逆方向の両方で走査することができます。
片方向リストと同じく、次のノードを指すポインタは、リストの最後尾に達した場合には null 値を格納するか、空のリストを指すこともあります。
以下に簡単な画像とソースコード(TypeScript)を記します。

class Item {
    data: number;
    next: Item | null;
    prev: Item | null;

    constructor(data: number) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    head: Item;

    constructor(item: Item) {
        this.head = item;
    }
}

let item1: Item = new Item(7);
let item2: Item = new Item(99);
let item3: Item = new Item(45);

item1.next = item2;
item2.prev = item1;
item2.next = item3;
item3.prev = item2;

let numList: DoublyLinkedList = new DoublyLinkedList(item1);

let currentItem: Item | null = numList.head;
while(currentItem !== null) {
    console.log(currentItem.data);
    currentItem = currentItem.next;
}

まとめ

特徴	片方向リスト	双方向リスト
メモリ消費	少ない	多い
参照	一方向	両方向
挿入・削除	特定のノードの前への挿入は効率が悪い	特定のノードの前後への挿入・削除が効率的

今回は、データ構造の一つである連結リストについて簡単に解説しました。
連結リストは、配列とは異なる特徴を持つデータ構造であり、適切な場面で活用することで、より効率的なプログラムを作成することができます。