링크드 리스트 : 메모리 알뜰하게 사용하기

빙글빙글 돌아가는 짱구의 하루~~ 

 

자료구조 시리즈 두 번째는 바로 '링크드 리스트'입니다. 

지난 시간에는 '동적 배열'에 대해서 알아보았습니다. 

 

동적 배열은 '콜 스택 구조상 컴파일 전에 메모리 양이 정해져야 하는 한계'를 

힙을 사용해 런타임에 메모리를 결정할 수 있게 해 줌으로써 해결해 줬지요?

덕분에 우리는 사용자의 입력, 입,출력되는 파일 등

프로그램이 실행될 때 결정되는 것들을 유연하게 저장할 수 있게 되었어요. 

 

동적 배열: 스택의 한계를 넘어서

 

그렇다면 링크드 리스트는 뭐 때문에 필요하게 되었는지 살펴봅시다. 

레츠기딧~~

배열의 한계

배열은 정적이든 동적이든 상관없이 자료 구조 특성상 가지고 있는 제약사항이 있어요.

 

뭘까요?

 

바로 "배열은 항상 연속된 메모리 블록에 저장되어야 한다"는 것입니다. 

 

 

위와 같은 특징은 '메모리 파편화' 을 가져와요. 

 

데이터를 저장하기 위해서는 먼저 그 데이터를 저장할 '공간'인 메모리를 할당받아야 해요. 

배열은 항상 연속된 메모리 블록에 저장되어야 하기 때문에 아래와 같이 저장돼요. 

 

 

그림을 보면 감이 오죠? 

만약에 데이터 A 크기 정도의 다른 데이터 E를 저장하려고 한다고 해봅시다. 

아직 메모리에 군데군데에 충분히 빈 공간들이 많지만 데이터 A 정도의 크기가 한 번에 들어갈 만큼의

메모리는 공간을 찾을 수가 없어요.

그러면 어쩔 수 없이 새로운 메모리 블록을 더 할당받아야 하죠. 

 

 

메모리가 아직 남았는데 왜 할당을 못하니 ㅠㅠ

 

메모리 파편화에 더해 배열의 한계를 아래와 같이 정리해 볼 수 있어요. 

1. 연속적인 메모리 할당 : 배열은 항상 연속된 메모리 블록에 저장되어야 합니다. 이는 메모리 공간이 파편화되어 있을 때 큰 배열을 할당하기 어렵게 만들어요. 
2. 크기 조정의 비효율성 : 동적 배열도 크기를 조정할 때는 새로운 메모리 블록을 할당하고 모든 요소를 복사하는 절차가 필요해요. 이는 O(n) 시간이 소요되는 작업이에요. 
3. 중간 삽입 / 삭제의 비효율성 : 배열의 중간에 요소를 삽입하거나 삭제하려면, 해당 위치 이후의 모든 요소를 한 칸씩 이동시켜야 돼요. 이 역시 O(n) 시간이 소요되는 작업이에요. 

링크드 리스트 등장

 

일단 링크드 리스트가 뭔지는 알아야겠죠?

 

링크드 리스트(Linked List)도 데이터 요소들을 순서대로 저장하는 자료구조예요. 

하지만 배열과 달리, 각 요소는 메모리상에 연속적으로 위치할 필요가 없답니다. 

 

링크드 리스트의 핵심 구성 요소는 '노드(Node)'에요.

링크드 리스트의 각 요소를 의미하며  두 가지 부분으로 구성돼요.

데이터(Data) : 저장하고자 하는 실제 값 ( 정수, 문자열, 객체 등 )

포인터(Next) : 다음 노드의 메모리 주소를 가리키는 참조 값 

단일 노드의 구조:
┌─────────────────────────┐
│ 데이터(Data) │ 다음(Next) │
└─────────────────────────┘

 

 

링크드 리스트는 위와 같은 단일 노드가 포인터로 연결된 데이터 구조예요. 

링크드 리스트의 구조:
┌─────────────────────────┐    ┌─────────────────────────┐    ┌─────────────────────────┐
│ 데이터(10) │ 다음(Next) │───>│ 데이터(20) │ 다음(Next) │───>│ 데이터(30) │ 다음(Next) │───> null
└─────────────────────────┘    └─────────────────────────┘    └─────────────────────────┘
       ↑                                                             ↑
       │                                                             │
      head                                                          tail

 

 

데이터 구조의 첫 번째 노드를 head, 마지막 노드를 tail이라고도 불러요. 

 

Swift로 기본 구조를 작성해 보면

// 노드 클래스 정의
class Node<T> {
    var data: T           // 데이터 (어떤 타입이든 가능)
    var next: Node<T>?    // 다음 노드를 가리키는 포인터 (옵셔널)
    
    init(data: T) {
        self.data = data
        self.next = nil   // 처음에는 다음 노드가 없음
    }
}

// 링크드 리스트 클래스
class LinkedList<T> {
    var head: Node<T>?    // 첫 번째 노드를 가리키는 포인터
    var tail: Node<T>?    // 마지막 노드를 가리키는 포인터
    
    // 링크드 리스트가 비어있는지 확인
    var isEmpty: Bool {
        return head == nil
    }
    
    // 나머지 메서드들...
}

링크드 리스트가 동작하는 방식을 단계별로 살펴볼까요. 

 

1. 빈 리스트에 첫 노드 추가하기 

초기 상태: head = null, tail = null

새 노드 생성: [데이터(10) | next -> null]

head와 tail이 새 노드를 가리키도록 설정:
head -> [데이터(10) | next -> null] <- tail

2. 리스트 끝에 노드 추가 

현재 상태: head -> [데이터(10) | next -> null] <- tail

새 노드 생성: [데이터(20) | next -> null]

tail.next가 새 노드를 가리키도록 설정:
head -> [데이터(10) | next ->] -> [데이터(20) | next -> null]

tail을 새 노드로 업데이트:
head -> [데이터(10) | next ->] -> [데이터(20) | next -> null] <- tail

3. 리스트 중간에 노드를 삽입할 수도 있어요. 

현재 상태: 
head -> [데이터(10) | next ->] -> [데이터(20) | next -> null] <- tail

새 노드 생성: [데이터(15) | next -> null]

첫 번째 노드의 next를 새 노드로 설정하고, 새 노드의 next를 두 번째 노드로 설정:
head -> [데이터(10) | next ->] -> [데이터(15) | next ->] -> [데이터(20) | next -> null] <- tail

 

자 이제 링크드 리스트 뭐고 대충 어떻게 작동하는지 알게 되었으니 

이 자료구조가 어떻게 동적 배열의 한계를 하였는지 이해할 수 있을 거예요. 

 

1. 링크드 리스트는 비연속적인 메모리 공간을 활용할 수 있어요.

각 노드는 독립적으로 할당되므로, 메모리 어디에나 위치할 수 있죠. 

동일한 파편화 상황에서 링크드 리스트:
┌───┬─────┬───┬─────────┬───┬───────┬───┬───┐
│사용│[노드1]│사용│ [노드2] │사용│[노드3]│사용│...│
└───┴──↓──┴───┴────↓────┴───┴───↓───┴───┴───┘
        └───────→└──────────→└────→ ...

위의 그림처럼 파편화된 메모리 공간에서도 각 노드는 개별적으로 할당하고 포인터로 연결할 수 있어요. 

 

2. 크기 조정을 효율적으로 할 수 있어요. 

동적 배열의 경우 용량(capacity)이 가득 차면 더 큰 배열을 할당하고 모은 요소를 복사해야 돼요. 

1. 초기 상태 (크기 4)
┌───┬───┬───┬───┐
│ A │ B │ C │ D │
└───┴───┴───┴───┘

2. 요소 추가 시도 → 용량 부족 → 새 배열 할당 (크기 8)
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

3. 모든 요소 복사 (O(n) 작업)
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

4. 새 요소 추가
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

이 과정은 시간 복잡도가 O(n)이며, 따라서 배열이 클수록 복사 비용이 증가해요.

또한 메모리 사용 측면에서도 갑자기 원래 크기의 두 배에 가까운 메모리를 더 요구해요. 

 

하지만 링크드 리스트는 새 노드를 추가할 때

단순히 새로 추가되는 노드에 대한 메모리만 할당하고 포인터를 조정하면 돼요. 

1. 초기 상태
[A] → [B] → [C] → [D] → null

2. 새 노드 할당 (O(1) 작업)
[E]

3. 포인터 조정 (O(1) 작업)
[A] → [B] → [C] → [D] → [E] → null

기존 요소를 복사할 필요가 없는 시간 복잡도 O(1)의 동작이에요.

또한 메모리도 딱 필요한 크기만큼만 사용해요. 

 

3. 중간 삽입 / 삭제가 효율적이에요. 

배열에서 중간에 요소를 삽입하거나 삭제하려면, 해당 위치 이후의 모든 요소를 이동시켜야 해요.

요소 'C'를 삭제하는 경우 (인덱스 2):

1. 초기 상태
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘

2. 'C' 이후 요소들을 한 칸씩 앞으로 이동 (O(n) 작업)
┌───┬───┬───┬───┬───┐
│ A │ B │ D │ E │   │
└───┴───┴───┴───┴───┘

이 작업은 시간 복잡도가 O(n)이며 특히 배열의 앞부분에서 삽입/삭제가 일어날 경우 거의 모든 요소를 이동시켜야 해요. 

 

반면 링크드 리스트에서는 삽입/삭제할 위치를 알고 있다면 단순히 포인터만 조정하면 돼요. 

요소 'C'를 삭제하는 경우:

1. 초기 상태
[A] → [B] → [C] → [D] → [E] → null

2. 포인터 조정 (O(1) 작업)
[A] → [B] → [D] → [E] → null
       ↑      ↑
       │      │
   B.next = C.next

이 작업은 시간 복잡도가 O(1)이에요. (노드에 직접 접근할 수 있는 경우)

물론 링크드 리스트에서 특정 위치에 접근하는 것 자체는 O(n)이지만, 이미 위치를 알고 있거나(예: 리스트 순회 중에 노드를 가리키는 포인터를 가지고 있는 경우) 이중 연결 리스트에서 삭제 대상 노드에 직접 접근할 수 있는 경우에는 삽입/삭제 자체는 O(1)이에요. 

 

4. 데이터에 필요한 만큼만 메모리를 사용할 수 있어요. 

동적 배열은 일반적으로 용량(capacity)을 실제 크기(size)보다 크게 유지하기 때문에 이는 메모리 낭비로 이어질 수 있어요. 

크기 5, 용량 8의 동적 배열:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘
                    ↑
                실제 사용: 5
                할당된 메모리: 8
                낭비: 3 (37.5%)

위의 예에서는 메모리의 37.5%가 낭비되고 있으며, 실제 사용량이 적을수록 이 비율은 더 높아질 수 있어요. 

 

링크드 리스트는 정확히 필요한 만큼만 메모리를 사용해요. 

크기 5의 링크드 리스트:
[A] → [B] → [C] → [D] → [E] → null

 

위와 같은 장점들 덕분에 링크드 리스트는 특히 삽입 / 삭제가 빈번하게 발생하거나 , 메모리 효율성이 중요하거나, 실시간 성능이 필요한 상황에서 동적 배열의 한계를 효과적으로 해결할 수 있어요. 

물론 링크드 리스트도 임의 접근(random access)이 느리다는 단점이 있지만, 이는 감수할 수 있는 정도이지요. 

 

마지막으로 링크드 리스트의 종류에 대해서 간단히 알아볼까요?

 

1. 단일 연결 리스트(Singly Linked List) : 각 노드가 다음 노드만을 가리키는 포인터를 가짐 

┌─────────────────────────┐    ┌─────────────────────────┐    ┌─────────────────────────┐
│ 데이터(10) │ 다음(Next) │───>│ 데이터(20) │ 다음(Next) │───>│ 데이터(30) │ 다음(Next) │───> null
└─────────────────────────┘    └─────────────────────────┘    └─────────────────────────┘

 

2. 이중 연결 리스트(Doubly Linked List) :  각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터를 가짐 

┌───────────────────────────────┐    ┌───────────────────────────────┐
│ 이전(Prev) │ 데이터 │ 다음(Next) │<-->│ 이전(Prev) │ 데이터 │ 다음(Next) │
└───────────────────────────────┘    └───────────────────────────────┘

3. 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 구조

┌─────────────────────────┐    ┌─────────────────────────┐
│ 데이터 │ 다음(Next) │────────> 데이터 │ 다음(Next) │────────────
└─────────────────────────┘    └─────────────────────────┘  │
       ^                                                    │
       └────────────────────────────────────────────────────┘

 

여기까지 해서 지난 시간에 배운 동적 배열의 한계와 링크드 리스트가 이를 어떻게 해결하는지에 대해서 알아보았어요. 

 

요즘은 옛날처럼 메모리가 부족해서 아득바득 아껴야 하는 것은 아니지만 

이렇게 자료구조가 탄생한 이유와 내부 동작을 알아 놓으면 진짜 필요한 순간에 

마지막 한 방울까지 짜낼 수 있지 않을까요?