Implémentation d'une structure de données Java avec liste doublement chaînée

Liste doublement chaînée

Qu'est-ce qu'une liste doublement chaînée ?

Une liste doublement chaînée est également appelée liste doublement chaînée. Il s'agit d'un type de liste chaînée. Chaque nœud de données a deux pointeurs, pointant respectivement vers le successeur direct et le prédécesseur direct. Par conséquent, à partir de n’importe quel nœud de la liste doublement chaînée, vous pouvez facilement accéder à ses nœuds prédécesseur et successeur.

La principale différence entre une liste chaînée bidirectionnelle et une liste chaînée unidirectionnelle :

Direction de recherche : Le sens de recherche d'un La liste chaînée unidirectionnelle ne peut être qu'une seule direction, et les listes chaînées doublement peuvent effectuer une recherche vers l'avant ou vers l'arrière.
Supprimer : La suppression d'une liste chaînée unidirectionnelle nécessite l'aide de pointeurs auxiliaires. Recherchez d'abord le prédécesseur du nœud à supprimer, puis supprimez-le.
temp.next = temp.next.next;(temp est un pointeur auxiliaire)
La liste doublement chaînée peut se supprimer.

Les avantages et les inconvénients des listes chaînées bidirectionnelles et des listes chaînées unidirectionnelles :

Avantages : La structure de la liste chaînée double est plus avantageuse que la structure de liste à lien unique.

Inconvénients : Du point de vue de la structure de stockage, la liste doublement chaînée a un pointeur de plus que la liste chaînée unidirectionnelle, nécessitant une utilisation de mémoire supplémentaire et linéaire. (Un pointeur fait 4 octets dans les systèmes d'exploitation 32 bits et 8 octets dans les systèmes d'exploitation 64 bits).

Illustration de la structure logique d'une liste doublement chaînée :

Opérations spécifiques de une liste doublement chaînée : #+ 🎜#Illustration :

Code :

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

Modification :

侃侃 : C'est en fait la même chose que la suppression d'une liste chaînée unique.

Code :

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

Exemple de liste à double lien :

Utilisez une liste à double lien pour créer un système de gestion des informations sur les étudiants afin de compléter l'ajout et la suppression des informations sur les élèves.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!