Java二重リンクリストで追加、削除、変更、クエリを実装する方法

1. 二重リンク リストについて理解する

一方向リンク リストは、現在のノード値を保存するだけでなく、次のノードのアドレスも保存します

## 二重リンク リストは、現在のノードの値を保存するだけでなく、前のノードのアドレスと次のノードのアドレスも保存します

二重リンクリストの構造を定義します。 ポイントクラス:

ノードは、現在のノードの値だけでなく、このノードの先行ノードのアドレスとノードのアドレスも保存する必要があります。このノードの後続ノード

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

二重リンク リスト クラスを定義します:

前から後ろ、または後ろから前に指定できるため、このクラスでは、先頭ノードと末尾ノードの値が保存されます

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

2. 二重リンクリストの追加、削除、変更、確認を行います

1.

先頭プラグを挿入します

現在のリンク リストの先頭ノードにノードを挿入して、現在のリンク リストの先頭ノードの先行ノードが挿入するノード ノードを指すようにし、ノードの後続ノードが次を指すようにします。 head を指定し、head = ノードにすると、そのノードがリンク リストのヘッド ノードになります

#コードは次のとおりです。

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

末尾の挿入

# は、

## がリンク リストの最後に挿入されることを除いて、先頭の挿入と同じです

##コードは次のとおりです:

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

インデックス位置に挿入

値 val を持つノードをインデックス位置に挿入します:

Insertionそれでも先行ノードを見つける必要がありますが、二重リンク リストで先行ノードを見つけることは、一方向リンク リストで先行ノードを見つけるよりもはるかに柔軟です。一方向リンク リストは最初から最後までしか進むことができません。このときのノード数は 100 なので、インデックスは 98 です。その位置にノードを挿入すると、末尾ノードから二重リンクリストを検索できるようになり、さらに便利になります。前から後ろに検索するか、後ろから前に検索するかを判断しますか?

1.index 挿入位置は前から後ろから見ると前半になります

2 .index > size / 2 – > 後ろから前に見て、挿入位置は後半です

• # #コードは次のとおりです:

  /**
       * 在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.

コードを次のように変更します:

/**
     * 修改双向链表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. ## をクエリします。

# コードは次のとおりです:

 /**
     * 查询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. 削除インデックス位置のノードを削除します

コードは次のとおりです:

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

Head delete

を呼び出すだけで任意の位置のノードを削除できます

コードは次のとおりです:

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

Tail delete

を呼び出すだけで、任意の位置にあるノードを削除できます。

コードは次のとおりです。

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

最初のノードを削除します。 value val

コードは次のとおりです:

//删除第一个值为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--;
    }

値が val

であるすべての値を削除しますコードは次のとおりです:

rree

以上がJava二重リンクリストで追加、削除、変更、クエリを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。