
연결 리스트란 무엇일까요?
연결 리스트는 컴퓨터 과학에서 가장 기본적이면서도 강력한 데이터 구조 중 하나입니다. 배열과는 달리, 연결 리스트는 서로 연결된 노드로 구성됩니다. 각 노드에는 데이터와 다음 노드를 가리키는 참조(포인터)가 포함되어 있습니다.
💡 연결 리스트의 가장 큰 장점은 동적인 특성입니다. 실행 시간에 크기가 늘어나거나 줄어들 수 있으며, 전체 구조의 메모리 재할당이 필요하지 않습니다.
연결 리스트의 핵심 특징
1. 동적 크기
- 실행 시간에 크기가 변할 수 있습니다.
- 초기화 시 크기를 지정할 필요가 없습니다.
- 메모리 사용이 효율적입니다.
2. 메모리 구조
- 비연속적인 메모리 할당
- 각 노드에는 데이터와 다음 노드를 가리키는 참조가 포함됩니다.
- 마지막 노드는 null을 가리킵니다.
3. 성능 특성
- 삽입 및 삭제: 위치가 알려진 경우 O(1)
- 검색: 순차 접근이 필요하므로 O(n)
- 메모리 사용: 참조를 저장하기 위한 추가 공간 필요
러스트로 구현해보기
이제 단일 연결 리스트의 일반적인 구현을 살펴보겠습니다:
struct Node<T> {
value: T,
next: Option<Box<Node<T>>>,
}
struct LinkedList<T: PartialEq> {
head: Option<Box<Node<T>>>,
}
주요 연산 살펴보기
1. 새 리스트 만들기
impl<T: PartialEq> LinkedList<T> {
fn new() -> Self {
LinkedList { head: None }
}
}
2. 요소 추가하기 (Push)
push 연산은 새 노드를 리스트의 맨 앞에 추가합니다:
fn push(&mut self, value: T) {
let new_node = Box::new(Node {
value: value,
next: self.head.take(),
});
self.head = Some(new_node);
}
3. 요소 제거하기
요소를 제거할 때는 두 가지 경우를 고려해야 합니다:
- 맨 앞의 요소 제거(pop)
- 리스트 어디에서나 특정 값을 가진 요소 제거
fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.value
})
}
fn remove(&mut self, value: T) {
let mut cur = &mut self.head;
if let Some(node) = cur {
if node.value == value {
self.head = node.next.take();
return;
}
}
while let Some(node) = cur {
if let Some(next_node) = &mut node.next {
if next_node.value == value {
node.next = next_node.next.take();
break;
}
}
cur = &mut node.next;
}
}
러스트의 연결 리스트 메모리 관리
러스트에서 연결 리스트를 구현할 때 주목해야 할 점은 소유권 시스템을 다루는 것입니다. Option<Box<Node<T>>> 사용의 목적은 다음과 같습니다:
- Box<T>를 통해 노드를 힙에 할당
- Option으로 리스트의 끝(null)을 처리
- 소유권 규칙을 통해 메모리 안전성 보장, 가비지 컬렉션 불필요
언제 사용할까요?
연결 리스트는 다음과 같은 경우에 유용합니다:
- 잦은 삽입 및 삭제가 필요할 때
- 동적 메모리 할당이 필요할 때
- 무작위 접근이 중요하지 않을 때
- 대용량 데이터에서 메모리 효율성이 중요할 때
전체 코드
struct Node<T> {
value: T,
next: Option<Box<Node<T>>>,
}
struct LinkedList<T: PartialEq> {
head: Option<Box<Node<T>>>,
}
impl<T: PartialEq> LinkedList<T> {
fn new() -> Self {
LinkedList { head: None }
}
fn push(&mut self, value: T) {
let new_node = Box::new(Node {
value: value,
next: self.head.take(),
});
self.head = Some(new_node);
}
fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.value
})
}
fn remove(&mut self, value: T) {
let mut cur = &mut self.head;
if let Some(node) = cur {
if node.value == value {
self.head = node.next.take();
return;
}
}
while let Some(node) = cur {
if let Some(next_node) = &mut node.next {
if next_node.value == value {
node.next = next_node.next.take();
break;
}
}
cur = &mut node.next;
}
}
fn is_empty(&self) -> bool {
self.head.is_none()
}
}
fn main() {
let mut list: LinkedList<i32> = LinkedList::new();
list.push(3);
list.push(2);
list.push(1);
list.remove(2);
while let Some(value) = list.pop() {
println!("{}", value);
}
}
마무리
연결 리스트를 이해하는 것은 모든 프로그래머에게 필수적입니다. 이는 더 복잡한 데이터 구조의 기반이 되기 때문입니다. 러스트에서의 구현은 소유권 규칙으로 인해 다소 복잡해 보일 수 있지만, 이러한 제약은 더 안전하고 신뢰할 수 있는 코드 작성에 도움이 됩니다.
기억해야 할 점은, 연결 리스트가 일정한 장점을 가지고 있다고 해서 모든 상황에서 가장 좋은 선택은 아니라는 것입니다. 특정 사용 사례, 성능 요구사항, 메모리 제약 등을 고려하여 가장 적합한 데이터 구조를 선택해야 합니다.
728x90
'Dev > Algorithm' 카테고리의 다른 글
| Rust로 구현하는 자료구조 (Part 4) - 큐(Queue) (7) | 2024.11.26 |
|---|---|
| Rust로 구현하는 자료구조 (Part 2) - 스택 (6) | 2024.11.21 |
| Rust로 구현하는 자료구조 (Part 1) - 배열 (6) | 2024.11.20 |