Bagaimana untuk melaksanakan penambahan, pemadaman, pengubahsuaian dan pertanyaan dalam senarai terpaut berganda Java

1. Memahami senarai terpaut berganda

Senarai terpaut sehala bukan sahaja menyimpan nilai nod semasa, tetapi juga menyimpan alamat nod seterusnya

Senarai berganda berganda bukan sahaja menyimpan nilai nod semasa, tetapi juga menyimpan alamat nod sebelumnya dan alamat nod seterusnya

Tentukan penghujung senarai berganda Kelas mata:

Nod harus menyimpan bukan sahaja nilai nod semasa, tetapi juga alamat nod pendahulu nod ini dan alamat pengganti nod nod ini

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

Tentukan kelas senarai terpaut berganda:

Ia boleh digunakan dari hadapan ke belakang atau dari belakang ke hadapan, jadi dalam kelas ini, kedua-duanya nod kepala dan nilai nod ekor disimpan

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

2. Tambah, padam, ubah suai dan semak senarai berganda

1

Masukkan nod di kepala senarai terpaut semasa untuk membuat semasa Pendahulu nod kepala senarai terpaut menghala ke nod yang hendak dimasukkan, kemudian biarkan pengganti nod menghala ke kepala, dan kemudian biarkan kepala = nod, supaya nod itu menjadi nod kepala senarai terpaut

Kodnya adalah seperti berikut:

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

Sisipan ekor

Sama seperti sisipan kepala, kecuali

Kodnya adalah seperti berikut:

rreeeSisipkan

pada kedudukan indeks dan masukkan nod dengan nilai val pada kedudukan indeks:

Sisipan masih memerlukan mencari nod pendahulu, tetapi mencari nod pendahulu dalam dua pautan senarai adalah lebih fleksibel daripada mencari nod pendahulu dalam senarai terpaut sehala Senarai terpaut sehala hanya boleh pergi dari awal hingga akhir Jika terdapat 100 nod pada masa ini, indeksnya ialah 98. Masukkan nod di kedudukan, maka senarai pautan berganda boleh dicari dari nod ekor, yang akan menjadi lebih mudah

Bagaimana untuk menilai sama ada untuk mencari dari depan ke belakang atau dari belakang ke hadapan?

1.index < saiz / 2 &ndash >Melihat dari depan ke belakang, kedudukan sisipan adalah di bahagian hadapan

• 2 .indeks > saiz / 2 &ndash >Melihat dari belakang ke hadapan, kedudukan sisipan adalah pada separuh masa kedua

Kodnya adalah seperti berikut:

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

2 Ubah suai kod

seperti berikut:

rreee3

kod seperti berikut:

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

4. Padamkan

Padamkan nod pada kedudukan indeks

Kod itu ialah. seperti berikut:

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

Pemadaman pengepala

Panggilan untuk memadam nod pada sebarang kedudukan

Kodnya adalah seperti berikut:

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

Tail delete

Panggilan untuk memadam nod pada sebarang kedudukan

Kodnya adalah seperti berikut:

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

Padamkan nod pertama dengan value val

Kod adalah seperti berikut:

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

Padam semua nilai yang nilainya val

Kod adalah seperti berikut :

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

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan penambahan, pemadaman, pengubahsuaian dan pertanyaan dalam senarai terpaut berganda Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!