片方向リスト

単方向リスト（Singly Linked List）は、線形データ構造の一種で、一連のノードで構成されます。各ノードはデータ部分と次のノードへのポインタの2つの部分を含みます。単方向リストの特徴は、各ノードが次のノードのみを指し、最後のノードのポインタが null を指してリストの終了を示すことです。

単方向リストの基本操作

1. リストの作成

リストを作成するには、ヘッドノードが必要です。ヘッドノードはデータを保存せず、最初のノードへのポインタのみを保存します。

2. ノードの追加

ノードはリストの先頭、末尾、または中間に追加できます。

3. ノードの削除

ノードはリストの先頭、末尾、または中間から削除できます。

4. ノードの検索

ノードの値に基づいてノードを検索できます。

5. リストの遍歴

ヘッドノードから始めて、各ノードを順番にアクセスします。

単方向リストの利点と欠点

利点

リストの長さは動的に増加でき、配列のように事前にメモリスペースを割り当てる必要がありません。
ノードの挿入と削除の時間計算量は O(1) で、他の要素を移動する必要がなく、効率が高いです。

欠点

リストのランダムアクセス効率は低く、時間計算量は O(n) で、各アクセスはヘッドから始める必要があります。
リストはポインタを保存するために追加のメモリスペースが必要で、メモリを多く消費します。

単方向リストの実装

SinglyLinkedListDemo.java

        class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + (next != null) +
                '}';
    }
}

class LinkedList {
    Node head;

    LinkedList() {
        this.head = null;
    }

    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    void delete(int data) {
        if (head == null) {
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    void print() {
        Node current = head;
        while (current.next != null) {
            System.out.print(current + " -> ");
            current = current.next;
        }
        System.out.println(current);
    }

}

public class SinglyLinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        list.print();
        list.delete(3);
        list.print();
    }
}

出力結果：

bash

        Node{data=1, next=true} -> Node{data=2, next=true} -> Node{data=3, next=true} -> Node{data=4, next=true} -> Node{data=5, next=false}
Node{data=1, next=true} -> Node{data=2, next=true} -> Node{data=4, next=true} -> Node{data=5, next=false}