Comment implémenter l'ajout, la suppression, la modification et la requête dans une liste doublement chaînée Java

1. Comprendre la liste doublement chaînée

La liste chaînée unidirectionnelle enregistre non seulement la valeur actuelle du nœud, mais enregistre également l'adresse du nœud suivant

La liste doublement chaînée enregistre non seulement la valeur du nœud actuel. nœud, mais enregistre également le nœud précédent. L'adresse du point et l'adresse du nœud suivant

Définir la classe de nœud d'une liste doublement chaînée :

Le nœud ne doit pas seulement sauvegarder la valeur du nœud. nœud actuel, mais aussi l'adresse et l'adresse du nœud prédécesseur de ce nœud. L'adresse du nœud successeur de ce nœud

class DoubleNode{
    public DoubleNode next;
    DoubleNode prev;
    int val;
    DoubleNode tail;

    public DoubleNode() {}

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(DoubleNode prev, int val, DoubleNode tail) {
        this.prev = prev;
        this.val = val;
        this.tail = tail;
    }
}

Définissez une classe de liste chaînée bidirectionnelle :

Cela peut être d'avant en arrière ou de l'arrière vers l'avant, donc dans cette classe, le nœud de tête et la queue sont enregistrés La valeur du nœud

public class DoubleLinkedList {
    private int size;
    private DoubleNode head;
    private DoubleNode tail;
}

2. Ajouter, supprimer, modifier et vérifier la liste doublement chaînée

1. Insérer

Insertion de la tête

Insérez un nœud en tête de la liste chaînée actuelle, de sorte que le nœud principal de la liste chaînée actuelle pointe vers le nœud à insérer, puis laissez le successeur du nœud pointer vers la tête, puis laissez head = nœud, laissez. node devient le nœud principal de la liste chaînée

Le code est le suivant :

/**
     * 头插
     */
    public void addFirst(int val){
        DoubleNode node = new DoubleNode(val);
        if (head == null){
            head = tail = node;
        }else{
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
    }

Insertion de la queue

C'est la même chose que l'insertion de la tête, mais dans la liste chaînée Le code pour insérer la queue de

est la suivante :

 public void addLast(int val){
        DoubleNode node = new DoubleNode(val);
        if (head == null){
            head = tail =node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
    }

Insérer à la position d'index

Insérer le nœud de valeur val à la position où l'index est index :

L'insertion nécessite toujours de trouver le nœud prédécesseur, mais dans le liste doublement chaînée Le nœud prédécesseur est beaucoup plus flexible que la liste chaînée unidirectionnelle pour trouver le nœud prédécesseur. La liste chaînée unidirectionnelle ne peut aller du début à la fin que s'il y a 100 nœuds à ce moment-là. Le nœud doit être inséré à l'index de 98, alors la liste chaînée bidirectionnelle peut commencer à partir du nœud de queue. Il sera beaucoup plus facile de commencer la recherche

Comment juger s'il faut rechercher d'avant en arrière ou d'arrière en arrière. devant?

• 1.index < taille / 2 > Regardez d'avant en arrière, la position d'insertion est dans la moitié avant

• 2.index > à l'avant, insérez La position est dans la seconde moitié

Le code est le suivant :

/**
     * 在index位置插入
     * @param index
     * @param val
     */
    public void add(int index,int val){
        DoubleNode cur = new DoubleNode(val);
        if (index < 0 || index > size){
            System.err.println("add index illegal");
            return;
        }else{
            if (index == 0){addFirst(val);}
            else if (index == size){addLast(val);}
            else{
                DoubleNode prev = node(index-1);
                DoubleNode next = prev.next;
                cur.next = next;
                next.prev = cur;
                prev.next = cur;
                cur.prev = prev;
            }
        }
        size++;
    }
/**
     * 根据索引值找到对应的结点
     * @param index
     * @return
     */
    private DoubleNode node(int index){
        DoubleNode x = null;
        if (index < size/2){
            x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        }else{
            x = tail;
            for (int i = size - 1; i > index ; i--) {
                x = x.prev;
            }
        }
        return x;
    }

2 Modifiez le

comme suit :

/**
     * 修改双向链表index位置的结点值为newVal
     */
    public int set(int index,int newVal){
        DoubleNode dummyHead = new DoubleNode();
        dummyHead.next = head;
        DoubleNode prev = dummyHead;
        DoubleNode cur = prev.next;
        if (index < 0 || index > size - 1){
            System.err.println("set index illegal");
        }else{
            for (int i = 0; i < index; i++) {
                prev = prev.next;
                cur = cur.next;
            }
        }
        int oldVal = cur.val;
        cur.val = newVal;
        return oldVal;
    }

3.

codez comme suit :

 /**
     * 查询index位置的结点值
     */
    public int get(int index){
        DoubleNode dummyHead = new DoubleNode();
        dummyHead.next = head;
        DoubleNode prev = dummyHead;
        DoubleNode cur = prev.next;
        if (index < 0 || index > size - 1){
            System.err.println("get index illegal");
        }else{
            for (int i = 0; i < index; i++) {
                prev = prev.next;
                cur = cur.next;
            }
        }
        return cur.val;
    }

4. Supprimez

Supprimez le nœud à la position d'index

Le code est le suivant :

//删除链表index位置的结点
    public void removeIndex(int index){
        if (index < 0 || index > size - 1){
            System.err.println("remove index illegal");
            return;
        }
        DoubleNode cur = node(index);
        unlink(cur);
    }
 /**
     * 删除当前双向链表的node结点
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先处理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

Suppression de tête

Appelez simplement pour supprimer le nœud à n'importe quelle position

Le code est le suivant :

//头删
    public void removeFirst(){
      removeIndex(0);
    }

Tail delete

Appelez simplement pour supprimer le nœud à n'importe quelle position

Le code est le suivant :

//尾删
    public void removeLast(){
        removeIndex(size - 1);
    }

Supprimez le premier nœud avec la valeur val

Le code est le suivant suit :

//删除第一个值为val的结点
    public void removeValOnce(int val){
        if (head == null){
            return;
        }
        for (DoubleNode x = head;x != null;x = x.next){
            if (x.val == val){
                unlink(x);
                break;
            }
        }
    }

 /**
     * 删除当前双向链表的node结点
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先处理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

Supprimer toutes les valeurs en tant que val

Le code est le suivant :

//删除链表中所有值为val的结点
    public void removeAllVal(int val){
        for (DoubleNode x = head;x != null;){
            if (x.val == val){
                //暂存一下x的下一个结点
                DoubleNode next = x.next;
                unlink(x);
                x = next;
            }else{
                //val不是待删除的元素
                x = x.next;
            }
        }
    }
 /**
     * 删除当前双向链表的node结点
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先处理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

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!