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

이중 연결 리스트

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

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

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

 

* 이중 연결 리스트의 장점

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

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

 

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

 

자바로 직접 구현해보자.

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

- 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("연결 리스트의 헤더가 생성 완료되었습니다.\n");
		bw.flush();
		
		while(true) {
			String option = "";
			bw.write("메뉴를 선택하세요 \n");
			bw.write("1. 연결 리스트 전체 출력\n");
			bw.write("2. 연결 리스트 데이터 추가\n");
			bw.write("3. 연결 리스트 데이터 삭제\n");
			bw.write("4. 연결 리스트 헤더에서부터 검색\n");
			bw.write("5. 연결 리스트 끝에서부터 검색\n");
			bw.write("6. 연결 리스트 전체 길이 출력\n");
			bw.write("7. 프로그램 종료\n");
			bw.write("메뉴 선택 : ");
			bw.flush();
			
			option = br.readLine();
			
			if(option.equals("7")) {
				bw.write("프로그램이 종료됩니다.\n");
				bw.flush();
				break;
			}
			else if(option.equals("1")) {
				bw.write("\n연결 리스트 전체를 출력합니다.\n");
				bw.flush();
				ngmt.desc();
				bw.write("\n");
				bw.flush();
			}
			else if(option.equals("2")) {
				bw.write("\n연결 리스트에 데이터를 추가합니다.\n");
				bw.write("추가를 원하는 데이터를 입력하세요(숫자) : ");
				bw.flush();
				int insert_data = Integer.parseInt(br.readLine());
				ngmt.add(insert_data);
				bw.write("데이터가 정상적으로 추가 되었습니다.\n");
				bw.write("\n");
				bw.flush();
			}
			else if(option.equals("3")) {
				bw.write("\n연결 리스트에 데이터를 삭제합니다.\n");
				bw.write("삭제를 원하는 데이터를 입력하세요(숫자) : ");
				bw.flush();
				int delete_data = Integer.parseInt(br.readLine());
				ngmt.delete(delete_data);
			}
			else if(option.equals("4")) {
				bw.write("\n 리스트의 헤더에서부터 검색합니다.\n");
				bw.write("검색하고자 하는 데이터를 입력하세요(숫자) : ");
				bw.flush();
				int searchHead = Integer.parseInt(br.readLine());
				ngmt.searchFromHead(searchHead);
			}
			else if(option.equals("5")) {
				bw.write("\n 리스트의 끝에서부터 검색합니다.\n");
				bw.write("검색하고자 하는 데이터를 입력하세요 : ");
				bw.flush();
				int searchTail = Integer.parseInt(br.readLine());
				ngmt.searchFromTail(searchTail);
			}
			else if(option.equals("6")) {
				bw.write("\n연결 리스트의 전체 길이를 출력합니다.\n");
				bw.write("생성된 연결 리스트 전체 길이 : " + ngmt.doubleListSize() + "\n");
				bw.write("\n");
				bw.flush();
			}
			else {
				bw.write("잘못된 입력입니다. 다시 입력해 주십시오\n");
				bw.flush();
			}
				
		}
			
		bw.close();
	}
}