単一リンクリストノードの定義

LeetCodeでの単一リンクリストノードの定義は以下の通りです：

package com.wang.base.linkedList;

public class Demo01 {
    class ListNode{
        int val;
        ListNode next;
        ListNode(int x){
            val=x;
        }
    }
}

しかし、実際のプログラミング言語では、より複雑な構造が使われます：

package com.wang.base.linkedList;

public class Demo01 {
    class Node<E>{
        E val;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev,E element,Node<E> next){
            this.val=element;
            this.next=next;
            this.prev=prev;
        }
    }
}

主な違いは次の通りです：

1. プログラミング言語の標準ライブラリではジェネリクスが使用され、valフィールドを任意の型に指定できますが、LeetCodeの単一リンクリストノードのvalフィールドはint型のみです。
2. プログラミング言語の標準ライブラリでは双方向リンクリストが一般的です。単一リンクリストにはnextポインタのみがあり、双方向リンクリストにはprevとnextの2つのポインタがあります。

なぜリンクリストが必要なのか

リンクリストは連続したメモリ領域を必要とせず、メモリ内の異なる場所にある要素をノードのnextとprevポインタでつなげてリスト構造を作成します。理論上、リンクリストには容量制限がありません。

ただし、インデックスによって直接アクセスすることはできません。頭ノードから順番にnextポインタに従って探索する必要があります。

単一リンクリストの基本操作

リンクリストの作成

package com.wang.base.linkedList;

public class Demo02 {
    // 単一リンクリストを定義
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        // 配列をリンクリストに変換
        ListNode createLinkedList(int[]arr){
            // 配列が空の場合エラー
            if (arr==null||arr.length==0){
                return null;
            }
            ListNode head=new ListNode(arr[0]);
            ListNode cur=head;
            for (int i = 0; i < arr.length; i++) {
                cur.next=new ListNode(arr[i]);
                cur=cur.next;
            }
            return head;
        }
    }
}

検索/編集

package com.wang.base.linkedList;

public class Demo02 {
    // 単一リンクリストを定義
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        // 配列をリンクリストに変換
        ListNode createLinkedList(int[]arr){
            // 配列が空の場合エラー
            if (arr==null||arr.length==0){
                return null;
            }
            // リンクリストを作成
            ListNode head=createLinkedList(new int[]{1,2,3,4,5});
            // リンクリストを走査
            for(ListNode p=head;p!=null;p=p.next){
                System.out.println(p.val);
        }
        return head;
        }
    }
}

挿入

ヘッダに新しい要素を挿入

package com.wang.base.linkedList;

public class Demo02 {
    // 単一リンクリストを定義
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        // 配列をリンクリストに変換
        ListNode createLinkedList(int[]arr){
            // 配列が空の場合エラー
            if (arr==null||arr.length==0){
                return null;
            }
            // リンクリストを作成
            ListNode head=createLinkedList(new int[]{1,2,3,4,5});
            // ヘッダに新しいノードを追加
            ListNode newHead=new ListNode(0);
            newHead.next=head;
            head=newHead;
        return head;
        }
    }
}

テールに新しい要素を挿入

package com.wang.base.linkedList;

public class Demo02 {
    // 単一リンクリストを定義
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        // 配列をリンクリストに変換
        ListNode createLinkedList(int[]arr){
            // 配列が空の場合エラー
            if (arr==null||arr.length==0){
                return null;
            }
            // リンクリストを作成
            ListNode head=createLinkedList(new int[]{1,2,3,4,5});
            // テールに新しいノードを追加
            ListNode p=head;
            // 最後のノードまで移動
            while (p.next!=null){
                p=p.next;
            }
            // 新しいノードを追加
            p.next=new ListNode(6);
        return head;
        }
    }
}

中間に新しい要素を挿入

package com.wang.base.linkedList;

public class Demo02 {
        // 単一リンクリストを定義
        class ListNode {
            int val;
            ListNode next;

            ListNode(int x) {
                val = x;
            }
            // 配列をリンクリストに変換
            ListNode createLinkedList(int[] arr) {
                // 配列が空の場合エラー
                if (arr == null || arr.length == 0) {
                    return null;
                }
                // リンクリストを作成
                ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
                // 第三ノードの後に新しいノードを挿入
               ListNode p=head;
                for (int i = 0; i < 2; i++) {
                    p=p.next;
                }
                // 新しいノードを作成
                ListNode newNode=new ListNode(66);
                newNode.next=p.next;
                p.next=newNode;
                return head;
            }
        }
    }

削除

ヘッダから要素を削除

package com.wang.base.linkedList;

public class Demo02 {
        // 単一リンクリストを定義
        class ListNode {
            int val;
            ListNode next;

            ListNode(int x) {
                val = x;
            }

            // 配列をリンクリストに変換
            ListNode createLinkedList(int[] arr) {
                // 配列が空の場合エラー
                if (arr == null || arr.length == 0) {
                    return null;
                }
                // リンクリストを作成
                ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
                // ヘッダノードを削除
                head=head.next;
                return head;
            }
        }
    }

テールから要素を削除

package com.wang.base.linkedList;

public class Demo02 {
        // 単一リンクリストを定義
        class ListNode {
            int val;
            ListNode next;

            ListNode(int x) {
                val = x;
            }

            // 配列をリンクリストに変換
            ListNode createLinkedList(int[] arr) {
                // 配列が空の場合エラー
                if (arr == null || arr.length == 0) {
                    return null;
                }
                // リンクリストを作成
                ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
                // テールノードを削除
               ListNode p=head;
               // 前のノードを検索
               while (p.next.next!=null){
                   p=p.next;
               }
               // テールノードを削除
               p.next=null;
                return head;
            }
        }
    }

中間から要素を削除

package com.wang.base.linkedList;

public class Demo02 {
        // 単一リンクリストを定義
        class ListNode {
            int val;
            ListNode next;

            ListNode(int x) {
                val = x;
            }

            // 配列をリンクリストに変換
            ListNode createLinkedList(int[] arr) {
                // 配列が空の場合エラー
                if (arr == null || arr.length == 0) {
                    return null;
                }
                // リンクリストを作成
                ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});
                // 第四ノードを削除
               ListNode p=head;
                for (int i = 0; i < 2; i++) {
                    p=p.next;
                }
                // 第四ノードを削除
                p.next=p.next.next;
                return head;
            }
        }
    }

双方向リンクリストの基本操作

双方向リンクリストは2つのリンクを持つため、切断または接続を行う際には2つのステップが必要です

双方向リンクリストの作成

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        DoublyListNode head=new DoublyListNode(arr[0]);
        DoublyListNode cur=head;
        // forループで双方向リンクリストを作成
        for (int i = 1; i < arr.length; i++) {
            DoublyListNode newNode=new DoublyListNode(arr[i]);
            cur.next=newNode;
            newNode.prev=cur;
            cur=cur.next;
            
        }
        return head;
    }
}

検索/編集

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        DoublyListNode tail=null;
        // ヘッダからテールへ走査
        for (DoublyListNode p=head;p!=null;p=p.next){
            System.out.println(p.val);
            tail=p;
        }
        // テールからヘッダへ走査
        for (DoublyListNode p=tail;p!=null;p=p.prev){
            System.out.println(p.val);
        }
        return head;
    }
}

実際のアプリケーションでは、インデックスがヘッダに近いかテールに近いかに応じて適切な方向で走査することで、効率を向上させることができます。

挿入

ヘッダに新しい要素を挿入

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        // ヘッダに0を挿入
        DoublyListNode newHead=new DoublyListNode(0);
        newHead.next=head;
        head.prev=newHead;
        head=newHead;
        return head;
    }
}

テールに新しい要素を挿入

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        DoublyListNode tail=head;
        // 最後のノードまで移動
       while (tail.next!=null){
           tail=tail.next;
       }
       // テールに6を挿入
       DoublyListNode newNode=new DoublyListNode(6);
       tail.next=newNode;
       newNode.prev=tail;
       tail=newNode;
        return head;
    }
}

中間に新しい要素を挿入

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        // 第三ノードの後に66を挿入
        DoublyListNode p=head;
        for (int i = 0; i < 2; i++) {
            p=p.next;
        }
        // 新しいノードを準備
        DoublyListNode newNode=new DoublyListNode(66);
        newNode.next=p.next;
        newNode.prev=p;
        // 新しいノードを挿入
        p.next.prev=newNode;
        p.next=newNode;
        return head;
    }
}

削除

ヘッダから要素を削除

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        // ヘッダノードを削除
        DoublyListNode toDelete=head;
        head=head.next;
        head.prev=null;
        toDelete.next=null;
        return head;
    }
}

テールから要素を削除

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        // テールノードを削除
        DoublyListNode p=head;
        // テールノードを検索
        while (p.next!=null){
            p=p.next;
        }
        
        // テールノードを削除
        p.prev.next=null;
        p.prev=null;
        return head;
    }
}

中間に要素を削除

package com.wang.base.linkedList;

public class Demo03 {
    class DoublyListNode{
        int val;
        DoublyListNode next,prev;
        DoublyListNode(int x){val =x;}
    }
    DoublyListNode createDoublyLinkedList(int[]arr){
        if (arr==null||arr.length==0){
            return null;
        }
        // 双方向リンクリストを作成
        DoublyListNode head=createDoublyLinkedList(new int[]{1,2,3,4,5});
        // 第四ノードを削除
        // 第三ノードを検索
        DoublyListNode p=head;
        for (int i = 0; i < 2; i++) {
            p=p.next;
        }
        DoublyListNode toDelete=p.next;
        // toDeleteをリンクリストから分離
        p.next=toDelete.next;
        toDelete.next.prev=p;
        // toDeleteのポインタをnullに設定（オプション）
        toDelete.next=null;
        toDelete.prev=null;
        return head;
    }
}