Pelaksanaan struktur data Java senarai pautan berganda

Senarai pautan berganda

Apakah senarai pautan berganda?

Senarai terpaut berganda, juga dipanggil senarai terpaut berganda, ialah sejenis senarai terpaut Setiap nod datanya mempunyai dua penunjuk, masing-masing menunjuk kepada pengganti langsung dan pendahulu langsung. Oleh itu, bermula dari mana-mana nod dalam senarai berganda, anda boleh mengakses nod pendahulu dan nod penggantinya dengan mudah.

Perbezaan utama antara senarai terpaut berganda dan senarai terpaut sehala:

Arah carian: Arah carian senarai terpaut sehala hanya boleh dalam satu arah, manakala senarai berpaut dua kali boleh ke hadapan atau ke hadapan Lihat ke belakang.
Pemadaman: Pemadaman senarai terpaut sehala memerlukan penggunaan penuding tambahan, mula-mula cari pendahulu nod yang hendak dipadamkan, dan kemudian padamkannya.
temp.next = temp.next.next; (temp ialah penunjuk tambahan)
Senarai terpaut dua kali boleh memadamkannya sendiri.

Kebaikan dan keburukan senarai terpaut dua kali dan senarai pautan tunggal:

Kelebihan: Struktur senarai pautan dua kali lebih berfaedah daripada struktur senarai pautan tunggal.

Kelemahan: Dari perspektif struktur storan, senarai terpaut dua kali mempunyai satu penunjuk lebih daripada senarai pautan tunggal, yang memerlukan penggunaan memori linear tambahan. (Penunjuk ialah 4 bait dalam sistem pengendalian 32-bit dan 8 bait dalam sistem pengendalian 64-bit).

Ilustrasi struktur logik senarai pautan berganda:

Operasi khusus senarai pautan dua kali:

Tambah:
Ilustrasi:

Kod:

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

Padam:
Ilustrasi:

Kod :

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

Pengubahsuaian:
徃徃: Ia sebenarnya sama seperti memadam senarai pautan tunggal.

Kod:

//修改链表节点
    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);
    }

Contoh senarai pautan berganda:

Gunakan senarai pautan berganda untuk mencipta sistem pengurusan maklumat pelajar untuk melengkapkan penambahan, pemadaman dan pengubahsuaian maklumat pelajar.

rreeee

Atas ialah kandungan terperinci Pelaksanaan struktur data Java senarai pautan berganda. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!