線形リストとは？意味をわかりやすく解説

公開：2024年8月29日更新：2024年8月29日

線形リストとは
線形リストの実装と応用
C++での線形リストの実装
線形リストの主要操作と時間複雑度
線形リストの実際のアプリケーション

線形リストとは

線形リストはデータ構造の一種で、要素が直線的に並んだ形式を持つものです。各要素は次の要素へのリンクを保持し、順序付けられたデータの管理に適しています。英名では「Linear List」と呼ばれ、プログラミングにおいて広く使用されている基本的なデータ構造のひとつです。

線形リストは配列と異なりメモリ上で連続した領域を必要としないため、要素の挿入や削除が容易で動的なデータ管理に向いています。また、単方向リストと双方向リストの2種類があり、それぞれ異なる特性を持っています。

プログラミングにおいて線形リストはさまざまな場面で活用されます。たとえばデータの順序を保持する必要がある場合や、頻繁に要素の追加・削除が行われる状況で効果的です。また、スタックやキューなどの抽象データ型の実装にも利用されることがあります。

Python基礎・実践(Django)

企業・法人向けのPython研修では、基礎から応用まで体系的に学べます。

Python研修の詳細

DX社員研修

企業・法人向けのDX研修では、実務に繋がるリスキリングでITレベルを向上させます。

DX研修の詳細

Javaエンジニア育成研修

企業・法人向けのJavaエンジニア育成研修では、Javaの基礎から応用まで確実に習得できます。

Java研修の詳細

新卒・新入社員向け研修

企業・法人に新入社員・新卒社員に向けたプログラミング研修を提供しています。

新入社員研修の詳細

コードキャンプのIT研修を全て見る

線形リストの実装と応用

線形リストの実装と応用に関して、以下3つを簡単に解説します。

C++での線形リストの実装
線形リストの主要操作と時間複雑度
線形リストの実際のアプリケーション

C++での線形リストの実装

C++で線形リストを実装する際は、構造体やクラスを使用してノードを定義します。各ノードはデータと次のノードへのポインタを持ち、これらを連結することで線形リストを構築します。以下は単方向リストの基本的な実装例です。

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}
    // メソッドの実装（挿入、削除、表示など）
};

上記のコードではNode構造体でリストの各要素を表現し、LinkedListクラスでリスト全体を管理しています。このクラスに挿入や削除、表示などのメソッドを追加することで完全な線形リストの実装が可能です。

実際の使用ではこのクラスをインスタンス化し、メソッドを呼び出すことでリストの操作を行います。たとえばLinkedList list;でリストを作成し、list.insert(5);で要素を追加するなどの操作が可能です。

おすすめのPython研修一覧

Python研修を提供しているおすすめの企業・法人を一覧で掲載しております。

Python研修の一覧を見る

おすすめのDX研修一覧

DX研修を提供しているおすすめの企業・法人を一覧で掲載しております。

DX研修の一覧を見る

おすすめのJava研修一覧

Java研修を提供しているおすすめの企業・法人を一覧で掲載しております。

Java研修の一覧を見る

おすすめのJavaScript研修一覧

JavaScript研修を提供しているおすすめの企業・法人を一覧で掲載しております。

JavaScript研修の一覧を見る

線形リストの主要操作と時間複雑度

線形リストの主要な操作には要素の挿入や削除、検索があります。これらの操作の時間複雑度は、リストの実装方法や操作の位置によって異なります。一般的に、先頭への挿入と削除はO(1)の時間複雑度を持ちます。

// 先頭への挿入
void insertAtHead(int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    head = newNode;
}

// 先頭の削除
void deleteAtHead() {
    if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}

上記のコードは先頭への挿入と削除の実装例です。これらの操作は常に一定の時間で実行できるため、O(1)の時間複雑度を持ちます。一方、末尾への挿入や特定位置での操作はO(n)の時間複雑度を持つことがあります。

検索操作も通常O(n)の時間複雑度を持ちます。これは最悪の場合、リスト全体を走査する必要があるためです。ただしソート済みのリストでは二分探索を適用できる場合があり、その場合はO(log n)まで改善できます。

線形リストの実際のアプリケーション

線形リストはさまざまな実際のアプリケーションで活用されています。たとえばスタックやキューの実装やブラウザの履歴管理、音楽プレイリストの管理などに使用されます。以下は、簡単な音楽プレイリスト管理の例です。

class Song {
public:
    string title;
    Song* next;
    Song(string t) : title(t), next(nullptr) {}
};

class Playlist {
private:
    Song* head;
public:
    Playlist() : head(nullptr) {}
    void addSong(string title) {
        Song* newSong = new Song(title);
        if (head == nullptr) {
            head = newSong;
        } else {
            Song* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newSong;
        }
    }
    // 他のメソッド（再生、削除など）
};