이 글에서는 자바로 연결 리스트(Linked List)를 직접 구현하는 방법을 알아봅니다. java.util의 LinkedList 클래스는 이중 연결 리스트(doubly-linked list)에서 기대할 수 있는 다양한 연산을 수행하며, 인덱스를 사용하는 연산은 지정된 인덱스에 더 가까운 쪽, 즉 리스트의 시작 또는 끝부터 탐색을 진행합니다.
아래 예제를 통해 실제 구현 과정을 살펴보겠습니다.
프로그램 실행 시 입력 −
Run the program
기대되는 출력 결과 −
연결 리스트의 요소들: 100 150 200 250
알고리즘
Step 1 - 시작 Step 2 - 필요한 멤버 변수를 포함하는 클래스를 생성한다. Step 3 - 리스트에 요소를 추가하는 'insert' 함수를 정의한다. Step 4 - 'main' 메서드에서 클래스의 새 인스턴스를 생성한다. Step 5 - 리스트를 생성하고 'insert' 메서드를 사용해 요소를 추가한다. Step 6 - 리스트를 순회하며 현재 노드에 저장된 값을 출력한다. Step 7 - 다음 노드로 이동하여 같은 작업을 반복한다. Step 8 - 리스트의 끝에 도달할 때까지 위 과정을 계속한다. Step 9 - 결과를 출력한다. Step 10 - 종료
예제 1
이 예제에서는 모든 연산을 'main' 함수 안에서 하나로 묶어 처리합니다.
public class Demo {
Node head;
static class Node {
int data;
Node next_element;
Node(int element){
data = element;
next_element = null;
}
}
public static Demo insert(Demo input_list, int data){
Node new_node = new Node(data);
new_node.next_element = null;
if (input_list.head == null) {
input_list.head = new_node;
}
else {
Node last = input_list.head;
while (last.next_element != null) {
last = last.next_element;
}
last.next_element = new_node;
}
return input_list;
}
public static void main(String[] args){
Demo input_list = new Demo();
System.out.print("A linked list is declared: \n");
input_list = insert(input_list, 100);
input_list = insert(input_list, 150);
input_list = insert(input_list, 200);
input_list = insert(input_list, 250);
Node current_node = input_list.head;
System.out.print("The elements of the linked list are: \n");
while (current_node != null) {
System.out.print(current_node.data + " ");
current_node = current_node.next_element;
}
}
}출력 결과
A linked list is declared: The elements of the linked list are: 100 150 200 250
예제 2
이번에는 객체 지향 프로그래밍(OOP) 방식에 맞게 각 연산을 별도의 함수로 캡슐화하여 구현합니다.
public class Demo {
Node head;
static class Node {
int data;
Node next_element;
Node(int element){
data = element;
next_element = null;
}
}
public static Demo insert(Demo input_list, int data){
Node new_node = new Node(data);
new_node.next_element = null;
if (input_list.head == null) {
input_list.head = new_node;
}
else {
Node last = input_list.head;
while (last.next_element != null) {
last = last.next_element;
}
last.next_element = new_node;
}
return input_list;
}
public static void print_list(Demo input_list){
Node current_node = input_list.head;
System.out.print("The elements of the linked list are: \n");
while (current_node != null) {
System.out.print(current_node.data + " ");
current_node = current_node.next_element;
}
}
public static void main(String[] args){
Demo input_list = new Demo();
System.out.print("A linked list is declared: \n");
input_list = insert(input_list, 100);
input_list = insert(input_list, 150);
input_list = insert(input_list, 200);
input_list = insert(input_list, 250);
print_list(input_list);
}
}출력 결과
A linked list is declared: The elements of the linked list are: 100 150 200 250
정리
연결 리스트는 각 노드가 데이터와 다음 노드의 참조를 함께 저장하는 자료구조입니다. 위 예제처럼 insert 메서드로 새 노드를 리스트 끝에 추가하고, head부터 순차적으로 순회하면서 값을 출력하는 것이 연결 리스트 구현의 핵심입니다. 특히 예제 2처럼 기능별로 메서드를 분리하면 코드의 재사용성과 유지보수성이 크게 향상됩니다.