Rust로 구현하는 자료구조 (Part 3) - LinkedList

 

연결 리스트란 무엇일까요?

연결 리스트는 컴퓨터 과학에서 가장 기본적이면서도 강력한 데이터 구조 중 하나입니다. 배열과는 달리, 연결 리스트는 서로 연결된 노드로 구성됩니다. 각 노드에는 데이터와 다음 노드를 가리키는 참조(포인터)가 포함되어 있습니다.

💡 연결 리스트의 가장 큰 장점은 동적인 특성입니다. 실행 시간에 크기가 늘어나거나 줄어들 수 있으며, 전체 구조의 메모리 재할당이 필요하지 않습니다.

연결 리스트의 핵심 특징

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>>> 사용의 목적은 다음과 같습니다:

1. Box<T>를 통해 노드를 힙에 할당
2. Option으로 리스트의 끝(null)을 처리
3. 소유권 규칙을 통해 메모리 안전성 보장, 가비지 컬렉션 불필요

언제 사용할까요?

연결 리스트는 다음과 같은 경우에 유용합니다:

1. 잦은 삽입 및 삭제가 필요할 때
2. 동적 메모리 할당이 필요할 때
3. 무작위 접근이 중요하지 않을 때
4. 대용량 데이터에서 메모리 효율성이 중요할 때

전체 코드

 

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);
    }
}

마무리

연결 리스트를 이해하는 것은 모든 프로그래머에게 필수적입니다. 이는 더 복잡한 데이터 구조의 기반이 되기 때문입니다. 러스트에서의 구현은 소유권 규칙으로 인해 다소 복잡해 보일 수 있지만, 이러한 제약은 더 안전하고 신뢰할 수 있는 코드 작성에 도움이 됩니다.

기억해야 할 점은, 연결 리스트가 일정한 장점을 가지고 있다고 해서 모든 상황에서 가장 좋은 선택은 아니라는 것입니다. 특정 사용 사례, 성능 요구사항, 메모리 제약 등을 고려하여 가장 적합한 데이터 구조를 선택해야 합니다.