So implementieren Sie das Hinzufügen, Löschen, Ändern und Abfragen in einer doppelt verknüpften Java-Liste

1. Die doppelt verknüpfte Liste verstehen

Die einseitig verknüpfte Liste speichert nicht nur den aktuellen Knotenwert, sondern auch die Adresse des nächsten Knotens

Die doppelt verknüpfte Liste speichert nicht nur den aktuellen Wert Knoten, speichert aber auch die Adresse des Punktes und die Adresse des nächsten Knotens

Definieren Sie die Knotenklasse einer doppelt verknüpften Liste:

Der Knoten muss nicht nur den Wert des Knotens speichern aktueller Knoten, aber auch die Adresse und die Adresse des Vorgängerknotens dieses Knotens Von hinten nach vorne, daher werden in dieser Klasse sowohl der Kopfknoten als auch der Schwanz gespeichert. Der Wert des Knotens

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;
    }
}

2. Doppelt verknüpfte Liste hinzufügen, löschen, ändern und überprüfen 1. Einfügen

Kopfeinfügung

Fügen Sie einen Knoten am Kopf der aktuellen verknüpften Liste ein, sodass der Kopfknoten der aktuellen verknüpften Liste auf den einzufügenden Knoten zeigt. Lassen Sie dann den Nachfolger des Knotens auf den Kopf zeigen, und lassen Sie dann den Kopf = Knoten Der Knoten wird zum Hauptknoten der verknüpften Liste. Der Code lautet wie folgt:

lautet wie folgt:

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

Einfügen an der Indexposition

Einfügen des Knotens mit dem Wert val an der Position, an der der Index index:

Einfügen erfordert immer noch das Finden des Vorgängerknotens, aber in Doppelt verknüpfte Liste Der Vorgängerknoten ist viel flexibler als die einseitig verknüpfte Liste, um den Vorgängerknoten zu finden. Die einseitig verknüpfte Liste kann nur vom Anfang bis zum Ende durchlaufen, wenn zu diesem Zeitpunkt 100 Knoten vorhanden sind Wenn der Knoten am Index 98 eingefügt werden soll, kann die zweifach verknüpfte Liste am Endknoten beginnen. Es ist viel einfacher, wenn Sie mit der Suche beginnen

Wie Sie beurteilen können, ob von vorne nach hinten oder von hinten gesucht werden soll nach vorne?

1.index

2.index > Größe / 2 > Zum Vordergrund befindet sich die Position in der zweiten Hälfte. Der Code ist wie folgt:

/**
     * 头插
     */
    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++;
    }

2 Code wie folgt:

 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++;
    }

4. Löschen

Löschen Sie den Knoten an der Indexposition

Der Code lautet wie folgt:

• /**
       * 在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;
      }

  Kopf löschen
• Einfach aufrufen, um den Knoten an einer beliebigen Position zu löschen

Der Code lautet wie folgt:

/**
     * 修改双向链表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;
    }

Tail delete

Einfach aufrufen, um den Knoten an einer beliebigen Position zu löschen

Der Code lautet wie folgt:

 /**
     * 查询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;
    }

Löschen Sie den ersten Knoten mit dem Wert val

Der Code lautet wie folgt:

//删除链表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--;
    }

Alle Werte als val löschen

Der Code lautet wie folgt:

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie das Hinzufügen, Löschen, Ändern und Abfragen in einer doppelt verknüpften Java-Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!