이중 연결 목록이란 무엇인가요?
이중 연결 목록이라고도 하는 이중 연결 목록은 연결 목록의 한 유형입니다. 각 데이터 노드에는 각각 직접 후속 항목과 직접 선행 항목을 가리키는 두 개의 포인터가 있습니다. 따라서 이중 연결 목록의 모든 노드에서 시작하면 이전 노드와 후속 노드에 쉽게 액세스할 수 있습니다.
이중 연결 목록과 단방향 연결 목록의 주요 차이점:
검색 방향: 단방향 연결 목록의 검색 방향은 한 방향으로만 가능하지만 이중 연결 목록은 앞으로 검색할 수 있습니다. 또는 뒤로.
삭제: 단방향 연결 목록을 삭제하려면 보조 포인터를 사용해야 합니다. 먼저 삭제할 노드의 선행 노드를 찾은 다음 삭제합니다. 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; } }삭제:
그림:
//删除一个节点。 //自我删除 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!