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

양방향 연결 목록 클래스 정의:

앞에서 뒤로 또는 뒤에서 앞으로 진행하므로 이번 수업에서는 head 노드와 tail 노드가 모두 저장됩니다. 노드의 값

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

2. 이중 연결 리스트 추가, 삭제, 수정 및 확인

1. 삽입

헤드 삽입

현재 연결 리스트의 헤드 노드가 삽입될 노드를 가리키도록 현재 연결 리스트의 헤드에 노드를 삽입한 다음, 노드의 후속 노드가 헤드를 가리키도록 하고, 헤드 = 노드, 하자. 노드는 링크드 리스트의 헤드 노드가 됩니다

코드는 다음과 같습니다.

/**
     * 头插
     */
    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인 노드를 삽입합니다.

삽입에는 여전히 선행 노드를 찾아야 하지만 이중 연결 목록 선행 노드는 단방향 연결 목록에서 선행 노드를 찾는 것보다 훨씬 더 유연합니다. 단방향 연결 목록은 현재 100개의 노드가 있는 경우에만 이동할 수 있습니다. 노드를 인덱스 98에 삽입하면 꼬리 노드부터 이중 연결 리스트를 시작할 수 있습니다. 검색을 시작하면 훨씬 쉽습니다.

앞에서 뒤로 검색할지 뒤에서 앞으로 검색할지 판단하는 방법 ?

• 1.index < size / 2 – > 앞에서 뒤로 보면 삽입 위치가 앞쪽 절반입니다.

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

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

으로 삭제합니다. 코드는 다음과 같습니다.

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

위 내용은 Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!