リスト構造は順序を持ち、ノード単位で連結されるが、メモリ上では必ずしも連続していない。

• 各ノードはデータ領域と次のノードへの参照を持つ
• 先頭ノード（ヘッド）は実データを持たず、リストの起点として機能する
• ノードの配置は物理的に連続している必要はない
• ヘッドノード有り／無しの設計は用途に応じて選択可能

基本操作：追加・更新・削除・逆転

public class NodeManager {
    private ListNode head = new ListNode(0, "", "");

    static class ListNode {
        int id;
        String title;
        String alias;
        ListNode next;

        ListNode(int id, String title, String alias) {
            this.id = id;
            this.title = title;
            this.alias = alias;
        }

        @Override
        public String toString() {
            return "Node{id=" + id + ", title='" + title + "', alias='" + alias + "'}";
        }
    }

    public void append(ListNode node) {
        ListNode cursor = head;
        while (cursor.next != null) cursor = cursor.next;
        cursor.next = node;
    }

    public void modify(ListNode updated) {
        ListNode cursor = head.next;
        while (cursor != null && cursor.id != updated.id) cursor = cursor.next;
        if (cursor != null) {
            cursor.title = updated.title;
            cursor.alias = updated.alias;
        } else {
            System.out.printf("ID %d のノードが見つかりません%n", updated.id);
        }
    }

    public void remove(int targetId) {
        ListNode cursor = head;
        while (cursor.next != null && cursor.next.id != targetId) cursor = cursor.next;
        if (cursor.next != null) {
            cursor.next = cursor.next.next;
        } else {
            System.out.printf("ID %d のノードは存在しません%n", targetId);
        }
    }

    public void display() {
        ListNode cursor = head.next;
        while (cursor != null) {
            System.out.println(cursor);
            cursor = cursor.next;
        }
    }

    public static void reverse(ListNode start) {
        if (start == null || start.next == null) return;
        
        ListNode current = start.next;
        ListNode reversedHead = new ListNode(0, "", "");
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = reversedHead.next;
            reversedHead.next = current;
            current = nextTemp;
        }
        start.next = reversedHead.next;
    }
}

双方向リストの特徴と操作

双方向リストは前後両方向へのトラバースが可能で、自己削除が実現できる点が単方向リストとの大きな違いです。

class BidirectionalList {
    private DListNode root = new DListNode(0, "", "");

    static class DListNode {
        int id;
        String label;
        String codename;
        DListNode next;
        DListNode prev;

        DListNode(int id, String label, String codename) {
            this.id = id;
            this.label = label;
            this.codename = codename;
        }

        @Override
        public String toString() {
            return "DNode{id=" + id + ", label='" + label + "', codename='" + codename + "'}";
        }
    }

    public void insert(DListNode node) {
        DListNode tail = root;
        while (tail.next != null) tail = tail.next;
        tail.next = node;
        node.prev = tail;
    }

    public void erase(int targetId) {
        DListNode cursor = root.next;
        while (cursor != null && cursor.id != targetId) cursor = cursor.next;
        if (cursor != null) {
            cursor.prev.next = cursor.next;
            if (cursor.next != null) cursor.next.prev = cursor.prev;
        } else {
            System.out.printf("削除対象 ID %d が見つかりません%n", targetId);
        }
    }
}

循環リストとヨセフス問題

n人が円形に並び、k番目からm人ごとに除外していくという古典的アルゴリズム問題。循環リストで自然にモデル化できる。

実装のポイント：

• 最後のノードが最初のノードを指すように接続
• カウンタを用いてmステップごとにノードを削除
• 削除後は次のノードから再カウントを開始