How to implement addition, deletion, modification and query in Java doubly linked list

1. Understanding the doubly linked list

The one-way linked list not only saves the current node value, but also saves the address of the next node

The doubly linked list not only saves the value of the current node, but also saves the address of the previous node and the address of the next node

Define the structure of a doubly linked list Point class:

The node must save not only the value of the current node, but also the address of the predecessor node of this node and the address of the successor node of this node

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

Define a doubly linked list class:

It can be from front to back or from back to front, so in this class, the value of the head node and the tail node are saved.

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

2. Add, delete, modify and check the doubly linked list

1. Insert

Head plug

Insert a node at the head of the current linked list, so that the current The predecessor of the head node of the linked list points to the node node to be inserted, and then let the successor of node point to the head, and then let head = node, so that node becomes the head node of the linked list

The code is as follows:

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

Tail insertion

is the same as head insertion, except that

# is inserted at the end of the linked list

##The code is as follows:

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

Insert at the index position

Insert a node with value val at the index position:

Insertion still requires finding the predecessor node, but finding the predecessor node in a doubly linked list is much more flexible than finding the predecessor node in a one-way linked list. A one-way linked list can only go from beginning to end. If there are 100 nodes at this time, the index is 98. Insert the node at the position, then the doubly linked list can be searched from the tail node, which will be much more convenient.

How to judge whether to search from front to back or from back to front?

##1.index Looking from front to back, the insertion position is in the front half
2 .index > size / 2 – >Look from back to front, the insertion position is in the second half

##The code is as follows:

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

code as follows:

/**
     * 修改双向链表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. Query the

code as follows:

 /**
     * 查询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. Delete

Delete the node at index position

The code is as follows:

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

Just call to delete the node at any position

The code is as follows:

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

Tail delete

Just call to delete the node at any position

The code is as follows:

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

Delete the first node with value val

The code is as follows:

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

Delete all values ​​whose value is val

The code is as follows:

//删除链表中所有值为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--;
    }

The above is the detailed content of How to implement addition, deletion, modification and query in Java doubly linked list. For more information, please follow other related articles on the PHP Chinese website!