連結リストとは

連結リストは、配列とは異なり連続したメモリ領域を必要としないデータ構造です。各ノードが次のノードへの参照（ポインタ）を持つことで、離散的なメモリブロックを連結します。

この特性により、要素の検索は先頭から順次走査する必要がありますが、挿入や削除は参照の付け替えだけで完結します。その結果、配列と比較して検索のコストが高く、挿入・削除のコストが低いという特徴を持ちます。

連結リストはノードによって構成されます。各ノードは最低限、データを格納するフィールドと次のノードへの参照を持ちます。

ノードクラスの実装

まず、連結リストを構成するノードを表すクラスを定義します。

public class ListNode {

    private int id;
    private Object value;
    private ListNode successor;

    public ListNode(int id, Object value) {
        this.id = id;
        this.value = value;
        this.successor = null;
    }

    public int getId() {
        return this.id;
    }

    public Object getValue() {
        return this.value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public ListNode getSuccessor() {
        return this.successor;
    }

    public void setSuccessor(ListNode node) {
        this.successor = node;
    }

    @Override
    public String toString() {
        return "ListNode{id=" + id + ", value=" + value + "}";
    }
}

単方向連結リストの実装

末尾への追加

リストの末尾に新しいノードを追加するには、最後のノードまで走査し、その参照を新ノードに設定します。

public class SinglyLinkedList {

    private ListNode headerNode;

    public SinglyLinkedList() {
        this.headerNode = new ListNode(0, null);
    }

    public void append(ListNode newNode) {
        ListNode current = this.headerNode;
        
        while (current.getSuccessor() != null) {
            current = current.getSuccessor();
        }
        
        current.setSuccessor(newNode);
    }
}

順序を維持した挿入

ID順にノードを挿入する場合、適切な挿入位置を見つける必要があります。

public void insertOrdered(ListNode newNode) {
    ListNode previous = this.headerNode;
    
    while (previous.getSuccessor() != null) {
        ListNode nextNode = previous.getSuccessor();
        
        if (nextNode.getId() > newNode.getId()) {
            newNode.setSuccessor(nextNode);
            previous.setSuccessor(newNode);
            return;
        }
        
        if (nextNode.getId() == newNode.getId()) {
            throw new IllegalArgumentException("IDが重複しています: " + newNode.getId());
        }
        
        previous = nextNode;
    }
    
    previous.setSuccessor(newNode);
}

全ノードの表示

リスト内の全ノードを走査して表示します。

public void displayAll() {
    if (this.headerNode.getSuccessor() == null) {
        System.out.println("リストは空です");
        return;
    }
    
    ListNode current = this.headerNode.getSuccessor();
    
    while (current != null) {
        System.out.println(current);
        current = current.getSuccessor();
    }
}

IDによる検索

指定したIDを持つノードを検索します。

public ListNode findById(int targetId) {
    if (this.headerNode.getSuccessor() == null) {
        throw new NoSuchElementException("リストは空です");
    }
    
    ListNode current = this.headerNode.getSuccessor();
    
    while (current != null) {
        if (current.getId() == targetId) {
            return current;
        }
        current = current.getSuccessor();
    }
    
    throw new NoSuchElementException("ID: " + targetId + " のノードが見つかりません");
}

ノードの更新

指定したIDのノードの値を更新します。

public void modifyNode(ListNode updatedNode) {
    if (this.headerNode.getSuccessor() == null) {
        throw new NoSuchElementException("リストは空です");
    }
    
    ListNode current = this.headerNode.getSuccessor();
    
    while (current != null) {
        if (current.getId() == updatedNode.getId()) {
            current.setValue(updatedNode.getValue());
            return;
        }
        current = current.getSuccessor();
    }
    
    throw new NoSuchElementException("更新対象のノードが見つかりません");
}

ノードの削除

単方向リストでは、削除対象のノードの前のノードを見つける必要があります。前のノードの参照を、削除対象の次のノードに付け替えます。

public void removeById(int targetId) {
    ListNode previous = this.headerNode;
    
    while (previous.getSuccessor() != null) {
        ListNode target = previous.getSuccessor();
        
        if (target.getId() == targetId) {
            previous.setSuccessor(target.getSuccessor());
            return;
        }
        
        previous = target;
    }
    
    throw new NoSuchElementException("削除対象のノードが見つかりません");
}

循環連結リスト

循環連結リストは、単方向連結リストの一種で、末尾ノードの参照が先頭ノードを指すことでリング状に構成されます。この構造は、周回処理が必要な問題（ヨセフスの問題など）の解決に適しています。