이중 연결 목록을 구현하는 Java 시뮬레이션 방법

이중 연결 목록이중 연결 목록이라고도 하는 것은 연결 목록의 한 유형입니다. 각 데이터 노드에는 각각 직접 후속 항목과 직접 선행 항목을 가리키는 두 개의 포인터가 있습니다. 따라서 이중 연결 리스트의 모든 노드에서 시작하면 해당 노드의 선행 노드와 후행 노드

에 쉽게 접근할 수 있습니다. 다음 그림은 이중 연결 리스트의 논리 구조도로서 단일 연결 리스트와 다릅니다. . 이중 연결 목록의 각 노드에는 두 개의 노드에 대한 포인터 참조와 데이터 필드가 포함되어 있습니다. 이 두 노드는 각각 이전 노드와 다음 노드를 가리킵니다.

이중 연결 목록의 구조는 단일 연결 목록보다 개선되었습니다. 이때 연결리스트는 이전 노드와 다음 노드를 참조하여 주어진 값으로 전체 연결리스트를 앞뒤로 순회할 수 있어 순회 쿼리의 효율성이 크게 향상되고 단일 연결 목록의 성능 문제를 특정 노드로 해결합니다. 하지만 동시에 연결된 목록의 저장 오버헤드도 증가했습니다. 익숙한 linkedList의 하위 계층은 이 원칙에 따라 구현됩니다.

위의 내용을 통해 모두가 명확하게 이해할 수 있을 것입니다. 설명 바로가기 코드 위에서는 코드와 그래프 구조를 결합하여 이중 연결 목록을 이해할 수 있습니다.

public class DoubleLinkTest<T> {

    /**
     * 内部构造节点类
     * 
     * @param <T>
     */
    private class Node<T> {
        private T data;
        private Node next; // 指向下一个节点的引用
        private Node prev; // 指向前一个节点的引用

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head; // 模拟头结点
    private Node<T> last; // 模拟尾部节点
    private Node<T> other; // 暂定一个临时节点，用作指针节点
    private int length;

    public void DoubleLinkTest() {
        head = new Node<T>(null);
        last = head;
        length = 0;
    }

    public void DoubleLinkTest(T data) {
        head = new Node<T>(data);
        last = head;
        length = 0;
    }

    /**
     * 链表是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return length == 0;
    }

    /**
     * 普通添加，往链表尾部添加
     * 
     * @param data
     */
    public void add(T data) {
        if (isEmpty()) { // 链表为空，新创建一个链表
            head = new Node<T>(data);
            last = head;
            length++;
        } else {
            other = new Node<T>(data);
            other.prev = last;
            last.next = other; // 将新的节点与原来的尾部节点进行结构上的关联
            last = other; // other将成为最后一个节点
            length++;
        }
    }

    /**
     * 在指定的数据后面添加数据
     * 
     * @param data
     * @param insertData
     */
    public void addAfter(T data, T insertData) {
        other = head;
        while (other != null) { // 我们假定这个head是不为空的。
            if (other.data.equals(data)) {
                Node<T> t = new Node<T>(insertData);
                t.prev = other;
                t.next = other.next;// 对新插入的数据进行一个指向的定义
                other.next = t;

                if (t.next == null) {
                    last = t;
                }
                length++;
            }
            other = other.next;
        }
    }

    /**
     * 删除，删除指定的数据
     * 
     * @param data
     */
    public void remove(T data) {
        other = head;// 我们假定这个head是不为空的。
        while (other != null) {
            if (other.data.equals(data)) {
                other.prev.next = other.next;
                length--;
            }
            other = other.next;
        }

    }

    /**
     * 测试打印数据
     */
    public void printList() {
        other = head;
        for (int i = 0; i < length; i++) {
            System.out.println(other.data + "  ");
            other = other.next;
        }
    }

    public static void main(String[] args) {

        DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
        link.add(1);
        link.add(2);
        link.add(3);
        link.add(5);
        link.add(6);
        link.add(7);
        link.printList();

        System.out.println(" ============== ");

        System.out.println(" ==== 在3后面添加一个数据开始========== ");
        link.addAfter(3, 99);
        link.printList();

        System.out.println(" ==== 在3后面添加一个数据结束========== " + "\r\n");

        System.out.println(" ==== 移除一个数据开始========== ");
        link.remove(99);
        link.printList();
        System.out.println(" \r\n");

    }

}

메인 함수를 실행하면 콘솔의 출력을 볼 수 있습니다.

위 내용은 이중 연결 목록을 구현하는 Java 시뮬레이션 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!