[자료구조] - 자바로 연결 리스트를 구현해보자. #2

[자료구조] - 자바로 연결 리스트를 구현해보자. #2

이중 연결 리스트

기존 연결 리스트 구조의 단점

- 연결 리스트의 길이가 길어질 경우 원하는 데이터를 찾을 때 최악의 경우 연결 리스트의 최대 길이만큼 탐색해야 한다.

- 연결 리스트는 데이터를 헤더에서 부터 순차 탐색으로 찾기 때문이다.

* 이중 연결 리스트의 장점

- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능하다.(자바의 경우 ListIterator 클래스로 구현가능)

- 데이터를 탐색 할 때 찾고자 하는 데이터가 리스트의 후반부 쯤에 있을 경우, 리스트의 가장 뒤에서 부터 앞으로 탐색하면 기존의 리스트 보다 더 빨리 데이터를 찾을 수 있다.

이중 연결 리스트는 기존의 연결 리스트가 자신의 다음에 있는 노드의 주소를 가지고 있는것과 달리 자신의 앞에 있는 노드의 주소 또한 가지고 있으며, 이를 통해 리스트 내부에서 데이터를 탐색할 때 양방향으로 이동하며 탐색할 수 있게 된다.

자바로 직접 구현해보자.

이중 연결리스트 또한 이전글에서 작성한 일반 연결리스트 때와 같이 ListIterator 와 같은 클래스 없이 직접 자바 코드로 구현해보았다.

- DoubleNode.java

public class DoubleNode { private int data; private DoubleNode prev; private DoubleNode next; public DoubleNode(int data) { this.data = data; } public void setPrev(DoubleNode prev) { this.prev = prev; } public void setNext(DoubleNode next) { this.next = next; } public DoubleNode getPrev() { return prev; } public DoubleNode getNext() { return next; } public int getData() { return data; } }

- 각 노드 별로 이전 노드의 정보와 이후 노드의 정보를 가지고 있어야 하므로 DoubleNode 클래스 타입의 변수 prev, next 를 선언해주었다.

노드 객체로서 만들어진 DoubleNode 객체를 관리해줄 클래스 또한 작성해주었다.

- DoubleMgmt.java

public class DoubleMgmt { private DoubleNode head; private DoubleNode tail; private int listSize; // 연결리스트 헤더 노드 생성 public DoubleMgmt(int data) { this.head = new DoubleNode(data); this.tail = this.head; this.listSize = 1; } public void add(int data) { if(this.head == null) { // 연결 리스트의 헤더가 생성되지 않은 상태일 경우 // 헤더를 새로 생셍해준다. this.head = new DoubleNode(data); this.tail = this.head; } else { // 가장 마지막 노드 뒤에 데이터를 추가해준다. DoubleNode node = this.tail; DoubleNode newNode = new DoubleNode(data); node.setNext(newNode); newNode.setPrev(node); this.tail = newNode; this.listSize += 1; } } public void desc() { DoubleNode node = this.head; while(node != null) { System.out.println(node.getData()); node = node.getNext(); } } public void delete(int data) { boolean search = false; if(this.head == null) { System.out.println("연결 리스트가 존재하지 않은 상태입니다."); System.out.println("연결 리스트를 먼저 생성해 주십시오"); System.out.println(); } else if(this.head.getData() == data) { // 헤더를 삭제하는 경우 this.listSize -= 1; DoubleNode temp = this.head; this.head = this.head.getNext(); this.head.setPrev(null); temp = null; // 아무것도 참조하지 않는 객체는 GC(가비지 컬렉션) 의 대상이 되어 // 메모리에서 자동으로 삭제된다. System.out.println("데이터가 정상적으로 삭제되었습니다."); System.out.println(); } else { // 중간 노드, 또는 마지막 노드를 삭제할 경우 DoubleNode node = this.head; while(node.getNext() != null) { if(node.getNext().getData() == data) { // 다음 탐색 데이터가 삭제하고자 하는 노드일 경우 this.listSize -= 1; DoubleNode temp = node.getNext(); node.setNext(node.getNext().getNext()); // 삭제된 노드가 가리키고 있던 주소를 적재 if(node.getNext() == null) { this.tail = node; }else { node.getNext().setPrev(node); } temp = null; search = true; break; } else node = node.getNext(); } if(search) { System.out.println("데이터가 정상적으로 삭제되었습니다."); System.out.println(); }else { System.out.println("입력하신 데이터가 존재하지 않습니다."); System.out.println(); } } } public void searchFromHead(int data) { if(this.head == null) { System.out.println("연결 리스트가 존재하지 않은 상태입니다."); System.out.println("연결 리스트를 먼저 생성해 주십시오"); System.out.println(); } else { boolean search = false; int count = 1; DoubleNode node = this.head; while(node != null) { if(node.getData() == data) { search = true; System.out.println(data + " (은)는 리스트의 헤더에서부터 " + count + "번째에 있습니다."); System.out.println(); break; } else { count++; node = node.getNext(); } } if(!search) { System.out.println(data + " (은)는 연결 리스트에 존재하지 않습니다."); System.out.println(); } } } public void searchFromTail(int data) { if(this.head == null) { System.out.println("연결 리스트가 존재하지 않은 상태입니다."); System.out.println("연결 리스트를 먼저 생성해 주십시오"); System.out.println(); } else { int count = 1; DoubleNode node = this.tail; boolean search = false; while(node != null) { if(node.getData() == data) { search = true; System.out.println(data + " (은)는 리스트의 끝에서부터 " + count + "번째에 있습니다."); System.out.println(); break; } else { count++; node = node.getPrev(); } } if(!search) { System.out.println(data + " (은)는 연결 리스트에 존재하지 않습니다."); System.out.println(); } } } public int doubleListSize() { if(this.head == null) { System.out.println("연결 리스트가 존재하지 않은 상태입니다."); System.out.println("연결 리스트를 먼저 생성해 주십시오"); System.out.println(); return 0; } else return this.listSize; } }

- listSize 필드를 추가로 선언하여 연결 리스트에 추가, 삭제 등의 동작이 발생할 때마다 변경 내역을 적용하여 항상 리스트의 길이를 적재하고 있게끔 만들었다.

- add, desc, delete 등 기존에 일반 연결리스트를 구현할 때 작성했던 코드에서 이중 연결리스트 구조에 맞게끔 객체 참조 과정을 변경했다.

- searchFromHeam, searchFromTail 과 같은 메소드를 작성하여 이중 연결리스트의 구조가 제대로 만들어졌는지를 확인했다.

* 위의 코드들의 기능 검증을 위한 main 메소드가 작성된 클래스는 다음과 같다.

- DoubleList_main.java

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class DoubleList_main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write("데이터를 입력하세요 : "); bw.flush(); int data = Integer.parseInt(br.readLine()); DoubleMgmt ngmt = new DoubleMgmt(data); bw.write("연결 리스트의 헤더가 생성 완료되었습니다.

"); bw.flush(); while(true) { String option = ""; bw.write("메뉴를 선택하세요

"); bw.write("1. 연결 리스트 전체 출력

"); bw.write("2. 연결 리스트 데이터 추가

"); bw.write("3. 연결 리스트 데이터 삭제

"); bw.write("4. 연결 리스트 헤더에서부터 검색

"); bw.write("5. 연결 리스트 끝에서부터 검색

"); bw.write("6. 연결 리스트 전체 길이 출력

"); bw.write("7. 프로그램 종료

"); bw.write("메뉴 선택 : "); bw.flush(); option = br.readLine(); if(option.equals("7")) { bw.write("프로그램이 종료됩니다.

"); bw.flush(); break; } else if(option.equals("1")) { bw.write("

연결 리스트 전체를 출력합니다.

"); bw.flush(); ngmt.desc(); bw.write("

"); bw.flush(); } else if(option.equals("2")) { bw.write("

연결 리스트에 데이터를 추가합니다.

"); bw.write("추가를 원하는 데이터를 입력하세요(숫자) : "); bw.flush(); int insert_data = Integer.parseInt(br.readLine()); ngmt.add(insert_data); bw.write("데이터가 정상적으로 추가 되었습니다.

"); bw.write("

"); bw.flush(); } else if(option.equals("3")) { bw.write("

연결 리스트에 데이터를 삭제합니다.

"); bw.write("삭제를 원하는 데이터를 입력하세요(숫자) : "); bw.flush(); int delete_data = Integer.parseInt(br.readLine()); ngmt.delete(delete_data); } else if(option.equals("4")) { bw.write("

리스트의 헤더에서부터 검색합니다.

"); bw.write("검색하고자 하는 데이터를 입력하세요(숫자) : "); bw.flush(); int searchHead = Integer.parseInt(br.readLine()); ngmt.searchFromHead(searchHead); } else if(option.equals("5")) { bw.write("

리스트의 끝에서부터 검색합니다.

"); bw.write("검색하고자 하는 데이터를 입력하세요 : "); bw.flush(); int searchTail = Integer.parseInt(br.readLine()); ngmt.searchFromTail(searchTail); } else if(option.equals("6")) { bw.write("

연결 리스트의 전체 길이를 출력합니다.

"); bw.write("생성된 연결 리스트 전체 길이 : " + ngmt.doubleListSize() + "

"); bw.write("

"); bw.flush(); } else { bw.write("잘못된 입력입니다. 다시 입력해 주십시오

"); bw.flush(); } } bw.close(); } }

from http://evan-development.tistory.com/123 by ccl(A) rewrite - 2021-11-25 00:27:22