Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법-java지도 시간-php.cn

1. 이중 연결 리스트 이해

단방향 연결 리스트는 현재 노드의 값만 저장하는 것이 아니라 다음 노드의 주소도 저장합니다.

Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법

이중 연결 리스트는 현재 노드의 값만 저장하는 것이 아닙니다. 노드뿐만 아니라 이전 노드도 저장합니다. 포인트의 주소와 다음 노드의 주소

Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법

이중 연결 리스트의 노드 클래스 정의:

노드는 노드의 값만 저장해서는 안 됩니다. 현재 노드뿐만 아니라 이 노드의 이전 노드의 주소와 주소도 있습니다. 이 노드의 후속 노드의 주소

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. 삽입

헤드 삽입

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

Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법

코드는 다음과 같습니다.

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

로그인 후 복사

테일 삽입

헤드 삽입과 동일하지만 링크드 리스트에서

의 테일을 삽입하는 코드

Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법

은 다음과 같습니다.

 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 > 앞쪽으로 삽입 위치는 후반부

코드는 다음과 같습니다. Java 이중 연결 목록에서 추가, 삭제, 수정 및 쿼리를 구현하는 방법

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

로그인 후 복사

코드를 다음과 같이 수정합니다.

/**
     * 修改双向链表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 중국어 웹사이트의 기타 관련 기사를 참조하세요!