Javaデータ構造二重リンクリストの実装-＆＃＆チュートリアル-php.cn

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

王林

リリース： 2023-05-06 19:04:06

転載

1166 人が閲覧しました

二重リンクリスト

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

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

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

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

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

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

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

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

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

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

追加:
イラスト:

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

コード:

//添加一个节点到最后
    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;
        }
    }

ログイン後にコピー

削除:
イラスト:

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

コード :

 //删除一个节点。
    //自我删除
    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);
    }

ログイン後にコピー