연결리스트 : 대량 삽입과 삭제에 유리한 Node 기반 자료구조

컴퓨터 과학의 많은 자료 구조들은 Node라는 개념에 기반해 만들어져 있습니다.
Node란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각을 의미합니다.
이번 포스트에서 알아볼 연결 리스트는 이러한 Node 기반 자료 구조 중 가장 간단한 자료구조라고 할 수 있습니다.
지금부터 연결리스트에 대해 알아보도록 하겠습니다.

---

1. 연결 리스트 (Linked List) 란?

연결리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료구조입니다.
배열은 연속되는 메모리에 항목들을 배치하고 이러한 점 덕분에 인덱스를 통해 항목에 바로 접근할 수 있습니다.
그렇다면 메모리에 흩어져있는 항목(Node)들을 가진 연결리스트는 어떻게 항목에 접근할까요?
이 답이 바로 연결 리스트의 핵심입니다.
각 Node는 추가정보, 연결리스트 내의 다음 Node의 메모리 주소를 포함하고 있습니다.
이 추가 정보를 Link라 부르며 다음과 같이 묘사 할 수 있습니다.

 

 

마지막 Node는 Link 부분이 비어있습니다.
이러한 구조의 장점은 연속된 메모리를 할당해야 하는 배열은 크기가 커질수록 메모리 할당에 어려움을 겪지만
연결 리스트는 파편화된 공간이더라도 메모리 안에 여유 공간이 존재한다면 자유롭게 크기가 늘어날 수 있다는 것입니다.

 

위의 내용을 코드로 구현해 보겠습니다.

 

class Node {
    data

    nextNode = null

    constructor(data) {
        this.data = data
    }
}

class LinkedList {

    firstNode = null

    constructor(firstNode) {
        this.firstNode = firstNode
    }
}

// Node 생성
const node1 = new Node("A") 
const node2 = new Node("B") 
const node3 = new Node("C") 
const node4 = new Node("D") 

// Node 연결
node1.nextNode = node2
node2.nextNode = node3
node3.nextNode = node4
node4.nextNode = null

const linkedList = new LinkedList(node1)

 

Node 클래스 이외에 컴퓨터에게 연결리스트가 어디서부터 시작하는지 알려주기 위한 클래스가 필요합니다.
이때 중요한 사실이 드러납니다.
"연결리스트를 다룰 때는 첫 번째 Node에만 즉시 접근할 수 있다"

---

2.  연결리스트의 자료구조 연산

 

(1) 읽기

 

배열은 인덱스가 제공 된다면 시작 메모리 주소와의 연산을 통해 즉시 접근 가능합니다.
하지만 연결리스트가 즉시 접근 가능한 것은 시작 메모리 주소이고 모든 Node가 메모리 상에 흩어져있기에
시작 Node부터 차례로 해당 인덱스까지 이동해야만 합니다.
때문에 시간 복잡도는 $ O(N) $ 입니다.

 

 read(index) {
        // 읽기 진행은 첫번째 Node 부터
        let currentNode = this.firstNode
        let currentIndex = 0

        while (currentIndex < index) {
            // 존재하지 않는 Node 이면 null 반환
            if (currentNode.nextNode === null) {
                return null;
            }
            // index 까지 nextNode를 통해 이동
            currentNode = currentNode.nextNode
            currentIndex += 1
        }

        return currentNode
}

 

(2) 탐색

 

배열은 선형 검색 할 때 한 번에 하나의 항목을 검사하게 되므로 O(N) 이 나왔습니다.
연결리스트 또한 이와 유사한 방식으로 탐색합니다.
시간 복잡도는 $ O(N) $ 입니다.

 

indexOf(value) {
        // 탐색 진행은 첫번째 Node 부터
        let currentNode = this.firstNode
        let currentIndex = 0
        do {
        	// 인덱스 발견시 해당 인덱스 반환
            if(currentNode.data === value) {
                return currentIndex
            }
            // 인덱스 발견 못했을 시 다음 Node로 이동
            currentNode = currentNode.nextNode
            currentIndex += 1
        } while (currentNode !== null)

        // 찾지 못했을 시 null 반환
        return null;
    }

 

(3) 삽입

 

위의 연산들에서는 연결리스트의 장점을 보여주지 못했지만 연결리스트는 삽입에서 빛을 발하게 됩니다.
배열은 삽입 시 해당 위치에 삽입하기위해 뒤에 위치한 원소들을 모두 Shift 합니다.
하지만 연결리스트는 Shift 없이 삽입할 위치의 앞 노드의 Link가 가리키는 값을 수정하여 주고 삽입 노드를 기존의 뒷 Node에 연결하면 삽입이 완료됩니다.
시간 복잡도는 해당 셀까지 이동 $ N $,  삽입 $ 1 $ 로 $ O(N) $ 입니다.
가장 앞에 삽입하는 최선의 시나리오에서는 $ O(1) $ 이 나오게 됩니다.

 

 insertAtIndex(index, value) {
        const newNode = new Node(value)

        // List의 첫 항목으로 삽입이라면
        if (index === 0) {
            newNode.nextNode = this.firstNode
            this.firstNode = newNode
            return;
        }

        let currentNode = this.firstNode
        let currentIndex = 0

        // 삽입할 인덱스의 바로 이전 노드까지 이동
        while (currentIndex < index - 1) {
            currentNode = currentNode.nextNode
            currentIndex += 1
        }
        // 이전 노드의 다음노드를 삽입할 노드로
        // 삽입할 노드의 다음노드를 이전 노드의 다음노드였던 노드로
        newNode.nextNode = currentNode.nextNode
        currentNode.nextNode = newNode
    }

 

(4) 삭제

 

삭제 또한 삽입과 유사한 형태로 진행됩니다.
삭제하고자 하는 앞 Node에 접근해 Link로 뒤 Node을 가리키게 수정합니다

시간 복잡도는 해당 셀까지 이동 $ N $,  삭제 $ 1 $ 로 $ O(N) $ 입니다.
가장 앞에서 삭제하는 최선의 시나리오에서는 $ O(1) $ 이 나오게 됩니다.

 

deleteAtIndex(index) {
        // 첫번째 인덱스의 노드를 삭제하는 경우
        if(index === 0) {
            this.firstNode = this.firstNode.nextNode
            return
        }
        let currentNode = this.firstNode
        let currentIndex = 0

        // 삭제될 노드의 바로 이전 노드를 탐색
        while(currentIndex < index -1) {
            currentNode = currentNode.nextNode
            currentIndex += 1
        }

        // 삭제할 노드의 이전 노드의 다음 노드를 삭제할 노드의 다음 노드로 변경
        const nodeAfterDeletedNode = currentNode.nextNode.nextNode
        currentNode.nextNode = currentNode.nextNode.nextNode
    }

 

이렇게 삭제된 Node는 메모리 상에 남아있게 되지만 사실상 연결리스트에서는 삭제되었습니다.
삭제되고 남은 Node를 처리하는 방식은 프로그래밍 언어마다 다르지만, 어떤 언어에서는 GC(Garbage collector)라는 개념을 통해 메모리를 해제합니다.

---

 

3. 연결리스트의 효율성

위에서 살펴본 연결리스트의 연산은 배열 연산과 비교해 보았을 때 사실 그렇게 매력적이지 못합니다.
연결리스트는 Shift가 필요 없기에 탐색 도중 삽입과 삭제가 자유롭습니다.
때문에 대량 삽입, 삭제에서 큰 효율성을 보입니다.
예시로 이해해 보겠습니다.
1000 개의 원소를 가진 리스트에서 100개의 원소를 삭제한다고 가정했을 때,
 (1) 배열은 1000개의 배열을 100번 Shift 해야 할 수 있기에 약 100,000 단계가 걸립니다.
 (2) 연결리스트는 1000개의 읽기 단계, 100개의 삭제 단계로 단 1,100 단계만 이 걸립니다.
이처럼 연결리스트는 삽입, 삭제 시 다른 데이터를 Shift 하지 않아도 되므로 전체 리스트를 훑으며 삽입이나 삭제를 수행하기에 매우 알맞은 자료 구조입니다.

 

---

 

4. 이중연결리스트 (Doubly Linked List)

연결리스트의 종류는 다양합니다.
앞서 본 연결리스트를 기본형으로 하여 조금 수정하게 되면 큰 효율성 향상을 가져올 수 있습니다.
이 중 하나가 이중 연결리스트입니다.
이중 연결리스트는 노드에 두 개의 링크를 가지고 앞뒤 노드와 연결되어있습니다.

 

 

때문에 앞뒤로 이동이 가능하며 시작정보를 가지고 있던 클래스에서는 가장 뒤 노드 정보도 가지고 있어 뒤에서부터의 탐색 또한 가능합니다.

앞 뒤 접근이 가능하고 가장 앞, 뒤 원소의 삽입, 삭제 연산이 $ O(1) $ 인 이중 연결 리스트는 큐 구현에 있어 최고의 자료구조라고 할 수 있습니다

---

마치며

이번 포스트에서는 Node 기반 자료구조 중 하나인 연결리스트에 대해서 알아보았습니다.
배열과 추상적 개념은 선형 자료구조로 동일하지만 내부 구현이 다르게 됨으로써 성능에 큰 차이를 보입니다.
우리가 개발할 때 있어 적절한 자료구조를 선택을 위해 고민할 시간을 할애해야 하는 이유에 대해 설명해 주는 좋은 예였습니다.