Java 데이터 구조 이중 연결 목록 구현

이중 연결 목록

이중 연결 목록이란 무엇인가요?

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

이중 연결 목록과 단방향 연결 목록의 주요 차이점:

검색 방향: 단방향 연결 목록의 검색 방향은 한 방향으로만 가능하지만 이중 연결 목록은 앞으로 검색할 수 있습니다. 또는 뒤로.
삭제: 단방향 연결 목록을 삭제하려면 보조 포인터를 사용해야 합니다. 먼저 삭제할 노드의 선행 노드를 찾은 다음 삭제합니다. E temp.next = temp.next.next; (temp는 보조 포인터)
양방향 연결 테이블은 스스로 삭제할 수 있습니다.

이중 연결 목록과 단일 연결 목록의 장점과 단점:

장점: 이중 연결 목록 구조는 단일 연결 목록 구조보다 더 많은 장점을 가지고 있습니다.

단점: 저장 구조 관점에서 이중 연결 목록에는 단일 연결 목록보다 포인터가 하나 더 많아 추가적인 선형 메모리 사용량이 필요합니다. (포인터는 32비트 운영 체제에서는 4바이트이고 64비트 운영 체제에서는 8바이트입니다.)

이중 연결 목록의 논리적 구조 그림:

이중 연결 목록의 특정 작업:

추가:

그림:

코드:

//添加一个节点到最后
    public void add(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                // 当temp.next 为空时，证明temp为最后一个元素。
                temp.next = newNode; //temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //按学号顺序添加节点
    public void Sortadd(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //说明要添加的节点序号在当前链表中最大，因此直接添加在末尾。
                temp.next = newNode;//temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            } else if (temp.next.ID > newNode.ID) {
                //当前节点的下一位节点的编号大于 要添加的新节点，则证明新节点要添加在temp节点之后
                newNode.next = temp.next;//要添加节点的下一位 指向temp当前节点的下一位
                temp.next.pre = newNode;//temp当前节点的下一位的前一位 指向 新节点构成双向链表
                temp.next = newNode; // 再让当前节点的下一位指向 新节点
                newNode.pre = temp;//新节点的前一位 指向 当前节点temp
                //这样连接完成后就将  新节点插入 到 原本链表的temp节点与temp.next节点之间
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }

삭제:

그림:

code :

 //删除一个节点。
    //自我删除
    public void DoubleDelete(int id) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                System.out.printf("要删除的%d节点不存在\n", id);
                break;
            } else if (temp.ID == id) {
                //找到要删除节点
                // 此时temp 就代表将要被删除节点
                //temp.pre.next 指 当前要被删除节点 的前一位 的后一位
                // temp.next  指 当前要被删除节点的后一位
                temp.pre.next = temp.next;
                // （当前要被删除节点 的前一位 的后一位）指向 （当前要被删除节点的后一位）
                //这样就完成了 temp节点的删除操作
 
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                break;
            }
            temp = temp.next;
        }
    }

수정:

徃侃: 실제로는 단일 연결 리스트를 삭제하는 것과 같습니다.

코드:

//修改链表节点
    public void DoubleUpdate(DoubleNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            } else if (temp.ID == newNode.ID) {
                //找到要修改的节点
                temp.name = newNode.name;
                temp.mark = newNode.mark;
                return;
            }
            temp = temp.next;
        }
        System.out.printf("要修改的%d节点不存在\n", newNode.ID);
    }

이중 연결 리스트 예시:

이중 연결 리스트를 사용하여 학생 정보 관리 시스템을 생성하여 학생 정보의 추가, 삭제, 수정을 완료합니다.

아아아아

위 내용은 Java 데이터 구조 이중 연결 목록 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!