연결 리스트 (Linked List)
프로그래밍에서 연결 리스트(Linked List)는 데이터를 노드라는 단위로 저장하며, 각 노드가 다음 노드를 가리키는 포인터를 포함하는 자료구조이다. 배열과 달리 메모리가 연속적이지 않고, 동적으로 크기를 조정할 수 있다. 연결 리스트는 삽입과 삭제가 빈번한 상황에서 유용하며, 다양한 알고리즘의 기초가 된다. 이번 포스팅은 연결 리스트의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.
연결 리스트를 이해하면 데이터를 유연하게 관리하고 복잡한 문제를 효율적으로 해결할 수 있다. 하나씩 알아보자.
연결 리스트의 정의와 특징
연결 리스트는 데이터를 저장하는 노드와 다음 노드를 가리키는 포인터로 구성된다. 각 노드는 데이터와 다음 노드의 참조를 포함하며, 마지막 노드는 다음 노드가 없음을 나타내기 위해 null을 가리킨다. 연결 리스트는 배열과 달리 메모리 공간이 비연속적이며, 크기가 고정되지 않는다.
연결 리스트의 장점은 다음과 같다:
- 동적 크기 조정: 필요에 따라 노드를 추가하거나 제거할 수 있다.
- 효율적인 삽입/삭제: 특정 위치에서 삽입이나 삭제가 O(1) 시간에 가능하다(노드에 접근한 후).
- 유연한 메모리 사용: 메모리를 동적으로 할당하므로, 데이터 크기 변화에 적응적이다.
단점은 다음과 같다:
- 느린 접근 시간: 특정 노드에 접근하려면 리스트를 순회해야 하므로 O(n) 시간이 걸린다.
- 추가 메모리: 각 노드마다 포인터를 저장하므로 메모리 사용량이 증가한다.
- 캐시 비친화성: 메모리가 비연속적이어서 캐시 활용도가 낮다.
연결 리스트의 종류
연결 리스트는 구조에 따라 여러 종류로 나뉜다. 아래는 주요 형태와 구조를 도식화한 그림이다.
1. 단일 연결 리스트(Singly Linked List)
가장 기본적인 형태로, 각 노드가 다음 노드만 가리킨다.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
단일 연결 리스트 도식
[Head] → [Node1|data:1|next] → [Node2|data:2|next] → [Node3|data:3|null]
2. 이중 연결 리스트(Doubly Linked List)
각 노드가 이전 노드와 다음 노드를 모두 가리킨다. 양방향 순회가 가능하다.
class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
이중 연결 리스트 도식
[null] ↔ [Node1|prev|data:1|next] ↔ [Node2|prev|data:2|next] ↔ [Node3|prev|data:3|null]
3. 원형 연결 리스트(Circular Linked List)
마지막 노드가 첫 번째 노드를 가리켜 순환 구조를 형성한다.
원형 연결 리스트 도식
[Head] → [Node1|data:1|next] → [Node2|data:2|next] → [Node3|data:3|next] ↺
↑______________________________________________________________|
이 포스팅에서는 주로 단일 연결 리스트를 중심으로 설명하며, 필요 시 다른 변형을 다룬다.
자바에서 단일 연결 리스트 구현
단일 연결 리스트를 자바로 구현하는 기본 코드를 살펴보자.
class LinkedList {
Node head;
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 리스트 끝에 노드 추가
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
// 리스트 출력
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
이 코드는 기본적인 단일 연결 리스트 구현으로, 노드 추가와 리스트 출력 기능을 포함한다.
연결 리스트의 기본 연산
연결 리스트를 사용하려면 주요 연산을 이해해야 한다. 삽입, 삭제, 순회, 검색 등이 핵심 연산이다.
1. 삽입
노드를 리스트의 처음, 끝, 또는 특정 위치에 추가한다.
// 리스트 처음에 노드 추가
public void prepend(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// 특정 위치에 노드 추가 (index는 0부터 시작)
public void insertAt(int index, int data) {
if (index == 0) {
prepend(data);
return;
}
Node newNode = new Node(data);
Node current = head;
for (int i = 0; i < index - 1 && current != null; i++) {
current = current.next;
}
if (current != null) {
newNode.next = current.next;
current.next = newNode;
}
}
2. 삭제
특정 노드를 제거한다.
// 첫 번째 노드 삭제
public void deleteFirst() {
if (head != null) {
head = head.next;
}
}
// 특정 값의 노드 삭제 (첫 번째로 발견된 노드)
public void deleteValue(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
3. 순회
리스트의 모든 노드를 방문한다.
public void traverse() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
4. 검색
특정 값을 가진 노드를 찾는다.
public boolean search(int data) {
Node current = head;
while (current != null) {
if (current.data == data) return true;
current = current.next;
}
return false;
}
연결 리스트의 시간 복잡도
연결 리스트의 주요 연산의 시간 복잡도는 다음과 같다:
- 접근: O(n) - 특정 인덱스나 노드에 접근하려면 순회 필요.
- 삽입/삭제: O(1) - 노드에 이미 접근한 경우. 접근 시간이 포함되면 O(n).
- 검색: O(n) - 리스트를 순회하며 값을 찾는다.
- 순회: O(n) - 모든 노드를 방문한다.
배열과 비교하면, 접근은 느리지만 삽입과 삭제에서 유리하다.
이중 연결 리스트 구현
이중 연결 리스트는 양방향 순회가 가능해 특정 상황에서 유용하다.
class DoublyLinkedList {
Node head;
class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// 리스트 끝에 노드 추가
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
// 리스트 출력 (정방향)
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
이중 연결 리스트는 삭제나 역방향 순회에서 단일 연결 리스트보다 편리하다.
연결 리스트를 활용한 알고리즘
연결 리스트는 다양한 알고리즘에서 사용된다. 스택, 큐, 그래프 알고리즘 등에서 활용되며, 리스트 자체를 조작하는 문제도 많다.
1. 리스트 반전
연결 리스트의 노드 순서를 반대로 바꾼다.
public void reverse() {
Node prev = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
2. 사이클 탐지
연결 리스트에 사이클이 있는지 확인한다(플로이드의 토끼와 거북이 알고리즘).
public boolean hasCycle() {
if (head == null) return false;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
3. 리스트 병합
두 개의 정렬된 연결 리스트를 병합한다.
public Node mergeLists(Node l1, Node l2) {
Node dummy = new Node(0);
Node current = dummy;
while (l1 != null && l2 != null) {
if (l1.data <= l2.data) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 != null ? l1 : l2;
return dummy.next;
}
심화 주제: 연결 리스트 최적화
연결 리스트를 효율적으로 사용하려면 몇 가지 최적화 기법을 고려해야 한다.
1. 꼬리 포인터 사용
리스트 끝에 노드를 추가할 때 O(n) 순회가 필요하다. 이를 해결하기 위해 꼬리 포인터를 유지한다.
class LinkedList {
Node head;
Node tail;
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
return;
}
tail.next = newNode;
tail = newNode;
}
}
2. 더미 노드 사용
리스트 병합이나 특정 연산에서 더미 노드를 사용하면 코드를 간결하게 만들 수 있다.
3. 메모리 관리
삭제된 노드는 즉시 null로 설정해 가비지 컬렉션에 도움을 준다.
연결 리스트의 한계와 대안
연결 리스트는 삽입과 삭제에서 유리하지만, 접근 속도가 느리고 메모리 사용량이 많다. 이를 보완하기 위해 자바에서는 LinkedList 클래스를 제공한다.
import java.util.LinkedList;
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.addLast(2);
list.removeFirst();
그러나 빈번한 인덱스 기반 접근이 필요하면 배열이나 ArrayList가 적합하다.
문제
연결 리스트를 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고, 자바 코드로 해답을 제공한다.
난이도 하: 연결 리스트에서 특정 값 삭제
시간 제한: 1 초 | 메모리 제한: 256 MB | 제출: 123,456 | 정답: 78,901 | 맞힌 사람: 56,789 | 정답 비율: 63.789%
단일 연결 리스트와 정수 x가 주어진다. 리스트에서 값이 x인 모든 노드를 삭제하는 프로그램을 작성한다.
입력
첫째 줄에 리스트의 노드 수 N (1 ≤ N ≤ 100,000)과 삭제할 값 x (-1,000 ≤ x ≤ 1,000)가 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다.
출력
삭제 후 리스트의 노드 값을 순서대로 공백으로 구분해 출력한다. 리스트가 비었으면 아무 것도 출력하지 않는다.
입력 예시
6 3
1 2 3 4 3 5
출력 예시
1 2 4 5
문제 출처: 자체 제작
해답
해답 펼치기
import java.util.Scanner;
public class RemoveValue {
static class LinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Node head;
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void removeValue(int x) {
Node dummy = new Node(0);
dummy.next = head;
Node current = dummy;
while (current.next != null) {
if (current.next.data == x) {
current.next = current.next.next;
} else {
current = current.next;
}
}
head = dummy.next;
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int x = sc.nextInt();
LinkedList list = new LinkedList();
for (int i = 0; i < N; i++) {
list.append(sc.nextInt());
}
list.removeValue(x);
list.printList();
sc.close();
}
}
난이도 중: 연결 리스트 반전
단일 연결 리스트가 주어진다. 리스트의 노드 순서를 반대로 뒤집는 프로그램을 작성한다.
입력
첫째 줄에 리스트의 노드 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 모든 정수는 -1,000보다 크거나 같고, 1,000보다 작거나 같다.
출력
반전된 리스트의 노드 값을 순서대로 공백으로 구분해 출력한다.
입력 예시
5
1 2 3 4 5
출력 예시
5 4 3 2 1
문제 출처: LeetCode "Reverse Linked List"
해답
해답 펼치기
import java.util.Scanner;
public class ReverseList {
static class LinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Node head;
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void reverse() {
Node prev = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
LinkedList list = new LinkedList();
for (int i = 0; i < N; i++) {
list.append(sc.nextInt());
}
list.reverse();
list.printList();
sc.close();
}
}
난이도 상: 연결 리스트의 중간 노드 찾기
단일 연결 리스트가 주어진다. 리스트의 중간에 위치한 노드의 값을 출력하는 프로그램을 작성한다. 노드 수가 짝수인 경우, 두 번째 중간 노드의 값을 출력한다.
입력
첫째 줄에 리스트의 노드 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 모든 정수는 -1,000보다 크거나 같고, 1,000보다 작거나 같다.
출력
중간 노드의 값을 출력한다.
입력 예시
5
1 2 3 4 5
출력 예시
3
문제 출처: LeetCode "Middle of the Linked List"
해답
해답 펼치기
import java.util.Scanner;
public class MiddleNode {
static class LinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Node head;
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public int findMiddle() {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.data;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
LinkedList list = new LinkedList();
for (int i = 0; i < N; i++) {
list.append(sc.nextInt());
}
System.out.println(list.findMiddle());
sc.close();
}
}
마무리
연결 리스트는 데이터를 동적으로 관리하는 데 유용한 자료구조로, 삽입과 삭제에서 강점을 보인다. 단일 연결 리스트와 이중 연결 리스트의 구현, 기본 연산, 시간 복잡도, 활용 알고리즘, 최적화 기법을 다뤘다. 자바의 LinkedList 클래스와의 비교를 통해 한계와 대안을 살펴봤다.
'코딩 공부 > 알고리즘(자바)' 카테고리의 다른 글
| 기본 자료구조 - 해시 테이블 (Hash Table) (0) | 2025.05.08 |
|---|---|
| 기본 자료구조 - 덱 (Deque) (3) | 2025.05.06 |
| 기본 자료구조 - 큐 (Queue) (1) | 2025.05.04 |
| 기본 자료구조 - 스택 (Stack) (0) | 2025.05.03 |
| 기본 자료구조 - 배열 (Array) (1) | 2025.04.04 |