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

연결 리스트(Linked List) 구조

순차적으로 연결된 공간에 데이터를 나열하는 배열과는 달리, 연결 리스트의 경우 메모리상에서 떨어진 곳에 위치한 데이터를 주소 참조를 통해 연결하여 관리할 수 있는 데이터 구조이다.

- 데이터의 추가, 삭제의 경우 배열보다 유리하다.

- 데이터 탐색의 경우 배열보다 불리하다.

    - 배열의 경우 인덱스 번호를 통해 찾고자 하는 데이터에 즉시 접근할 수 있으나, 연결 리스트의 경우 헤더에서 부터 순차적으로 탐색하여 데이터를 찾아야 한다.

 

자바의 경우 각 객체간의 참조를 통해 연결 리스트를 구현할 수 있다.

 

* 연결 리스트의 경우 다음과 같은 구조로 이루어져 있다.

- 노드(Node) : 데이터 저장 단위 (데이터 값, 포인터) 로 구성

- 포인터(Pointer) : 각 노드 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간

 

* 일반적인 연결 리스트의 형태는 아래와 같다.

 

연결 리스트를 자바로 직접 구현해보자.

자바에서 구현되는 연결 리스트의 경우 보통 LinkedList<T> 클래스를 Import 해서 연결리스트 객체를 생성하여 사용하면 그만인 부분이긴 하지만, 연결 리스트 구조의 확실한 이해를 위해 위의 클래스를 이용하지 않고 직접 연결 리스트를 구현해보았다.

 

우선 연결 리스트의 각 요소를 구성할 노드 객체를 위한 클래스를 다음과 같이 작성했다.

- Node.java

public class Node {
	
	private int data;
	private Node next;
	
	public Node(int data) {
		this.data = data;
	}
	
	public int getData() {
		return data;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}

- 노드에 데이터로 저장될 정수형 필드 data 와, 다음 노드에 대한 참조 정보를 저장할 next 필드를 선언하였다.

- 생성자의 경우 숫자 데이터만 파라미터로 받아서 객체를 생성하게끔 작성하였다.

- getter, setter 메소드에서 setData() 메소드의 경우 생성자를 통해 데이터를 저장해 줄 것이기 때문에 작성하지 않았다. 

 

그리고 LinkedList<T> 클래스와 같이 연결 리스트를 전체적으로 관리해줄 클래스 또한 만들어보았다.

- NodeMgmt.java

public class NodeMgmt {
	
	private Node head;
	
	// 연결리스트 헤더 노드 생성
	public NodeMgmt(int data) {
		this.head = new Node(data);
	}
	
	public void add(int data) {
		if(this.head == null) { 
			// 연결 리스트의 헤더가 생성되지 않은 상태일 경우
			// 헤더를 새로 생셍해준다.
			this.head = new Node(data);
		}
		else {
			// 가장 마지막 노드 뒤에 데이터를 추가해준다.
			Node node = this.head;
			while(node.getNext() != null) {
				node = node.getNext();
			}
			node.setNext(new Node(data));
		}
	}
	
	public void desc() {
		Node 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) {
			// 헤더를 삭제하는 경우
			Node temp = this.head;
			this.head = this.head.getNext();
			temp = null; 
			// 아무것도 참조하지 않는 객체는 GC(가비지 컬렉션) 의 대상이 되어
			// 메모리에서 자동으로 삭제된다.
			System.out.println("데이터가 정상적으로 삭제되었습니다.");
			System.out.println();
		}
		else {
			// 중간 노드, 또는 마지막 노드를 삭제할 경우
			Node node = this.head;
			
			while(node.getNext() != null) {
				if(node.getNext().getData() == data) {
					// 다음 탐색 데이터가 삭제하고자 하는 노드일 경우
					Node temp = node.getNext();
					node.setNext(node.getNext().getNext()); // 삭제된 노드가 가리키고 있던 주소를 적재
					temp = null;
					search = true;
					break;
				}
				else
					node = node.getNext();
			}
			
			if(search) {
				System.out.println("데이터가 정상적으로 삭제되었습니다.");
				System.out.println();
			}else {
				System.out.println("입력하신 데이터가 존재하지 않습니다.");
				System.out.println();
			}
		}
	}
}

 - 연결 리스트를 처음 생성할 때 헤더 노드를 만들기 위해 Node 클래스 타입의 필드 head 를 선언하였다.

- 생성자의 경우 입력받은 정수형 데이터를 통해 연결 리스트의 헤더 노드를 만들어주는 방식으로 작성하였다.

- add() 메소드의 경우 연결 리스트가 존재하지 않을 경우, 입력 받은 정수형 데이터를 이용해 헤더 노드를 생성해주고, 그렇지 않을 경우 반복문을 통해 연결 리스트의 가장 마지막 노드를 찾은 후, 마지막 노드의 다음 노드 참조 정보에 입력받은 정수를 기반으로 생성한 노드 객체를 참조하도록 만들었다.

- desc() 메소드의 경우 연결 리스트의 헤더에부터 시작하여 연결 리스트의 끝까지 순회하며 각 노드에 저장되어 있는 data 값을 출력해주고 다음 노드 참조 정보를 넘겨주는 것으로 반복문을 구성했다.

- delete() 메소드의 경우 연결리스트가 존재하지 않는 경우에 대한 예외 처리를 먼저 해준 다음

헤더 노드를 삭제하는 경우, 중간노드 또는 마지막 노드를 삭제하는 경우로 나누어 조건문을 작성했다.

* 헤더 노드를 삭제하는 경우

: 헤더 노드 정보를 원래 헤더 노드 정보가 가지고 있던 다음 노드 참조 값으로 변경해준 후, 기존의 헤더 노드 참조 정보를 null 값으로 변경해주는 것으로 처리했다.

* 중간 노드 또는 마지막 노드를 삭제하는 경우

: 헤더에서 부터 반복문을 통해 각 노드들을 순회한다.

반복문을 수행하던 도중 다음번 노드가 삭제하고자 하는 숫자에 대한 정보를 가지고 있을 경우, 삭제될 노드가 가지고 있던 그 다음번 노드에 대한 참조 정보를 이전 노드로 옮겨준 다음 삭제할 숫자를 가지고 있는 노드를 삭제해주는 방식으로 작성하였다.

 

 

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

- LinkedList_main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class LinkedList_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());
		NodeMgmt ngmt = new NodeMgmt(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("메뉴 선택 : ");
			bw.flush();
			
			option = br.readLine();
			
			if(option.equals("4")) {
				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 {
				bw.write("잘못된 입력입니다. 다시 입력해 주십시오\n");
				bw.flush();
			}
				
		}
			
		bw.close();
	}
}

- 연결 리스트 생성을 위한 초기 데이터 입력을 제외한 다른 기능들은 반복문 내부에서 수행하도록 만들어 각 기능들이 차질없이 잘 수행되는지 확인할 수 있도록 만들었다.