Javaデータ構造二重リンクリストの実装

二重リンクリスト

二重リンクリストとは何ですか?

二重リンク リスト (二重リンク リストとも呼ばれる) はリンク リストの一種で、各データ ノードには 2 つのポインタがあり、それぞれ直接後続ノードと直接先行ノードを指します。したがって、二重リンク リスト内の任意のノードから開始して、その先行ノードおよび後続ノードに簡単にアクセスできます。

二重リンク リストと一方向リンク リストの主な違い:

検索方向: 一方向リンク リストの検索方向は、次のとおりです。一方、二重リンクリストは前方または前方後方に見ることができます。
削除: 一方向リンク リストの削除には補助ポインタの使用が必要です。まず、削除するノードの先行ノードを見つけてから、それを削除します。
Temp.next = Temp.next.next; (TEMP は補助ポインタ)
双方向リンクリストは単独で削除することができます。

二重リンク リストと単一リンク リストの長所と短所:

利点: 二重リンク リスト構造は、単一リンク リスト構造よりも有利です。

欠点: ストレージ構造の観点から見ると、二重リンク リストには一方向リンク リストよりも 1 つ多くのポインタがあり、追加の線形メモリ使用量が必要になります。 (ポインターは、32 ビット オペレーティング システムでは 4 バイト、64 ビット オペレーティング システムでは 8 バイトです)。

二重リンク リストの論理構造の図:

二重リンク リストの具体的な操作:

追加:
イラスト:

コード:

//添加一个节点到最后
    public void add(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                // 当temp.next 为空时，证明temp为最后一个元素。
                temp.next = newNode; //temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //按学号顺序添加节点
    public void Sortadd(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //说明要添加的节点序号在当前链表中最大，因此直接添加在末尾。
                temp.next = newNode;//temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            } else if (temp.next.ID > newNode.ID) {
                //当前节点的下一位节点的编号大于 要添加的新节点，则证明新节点要添加在temp节点之后
                newNode.next = temp.next;//要添加节点的下一位 指向temp当前节点的下一位
                temp.next.pre = newNode;//temp当前节点的下一位的前一位 指向 新节点构成双向链表
                temp.next = newNode; // 再让当前节点的下一位指向 新节点
                newNode.pre = temp;//新节点的前一位 指向 当前节点temp
                //这样连接完成后就将  新节点插入 到 原本链表的temp节点与temp.next节点之间
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }

削除:
イラスト:

コード :

 //删除一个节点。
    //自我删除
    public void DoubleDelete(int id) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                System.out.printf("要删除的%d节点不存在\n", id);
                break;
            } else if (temp.ID == id) {
                //找到要删除节点
                // 此时temp 就代表将要被删除节点
                //temp.pre.next 指 当前要被删除节点 的前一位 的后一位
                // temp.next  指 当前要被删除节点的后一位
                temp.pre.next = temp.next;
                // （当前要被删除节点 的前一位 的后一位）指向 （当前要被删除节点的后一位）
                //这样就完成了 temp节点的删除操作
 
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                break;
            }
            temp = temp.next;
        }
    }

修正 :
Kankan: これは実際には、単一リンクされたリストを削除するのと同じです。

コード:

//修改链表节点
    public void DoubleUpdate(DoubleNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            } else if (temp.ID == newNode.ID) {
                //找到要修改的节点
                temp.name = newNode.name;
                temp.mark = newNode.mark;
                return;
            }
            temp = temp.next;
        }
        System.out.printf("要修改的%d节点不存在\n", newNode.ID);
    }

二重リンクリストの例:

二重リンクリストを使用して学生情報管理システムを作成し、学生情報の追加、削除、変更を完了します。

rree

以上がJavaデータ構造二重リンクリストの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。