자바스크립트로 연결 리스트를 구현하는 방법

Original article: How to Implement a Linked List in JavaScript

여러분이 만약 데이터 구조를 공부하고 있다면, 연결 리스트(linked list)는 반드시 알아야 할 구조 중 하나입니다. 연결 리스트를 좀 더 이해하고 싶거나 구현하는 방법이 궁금하다면 이 게시글이 도움을 줄 것입니다.

이 글에서는 연결 리스트가 무엇이고, 유사한 특징을 가진 배열(array)과 어떤 차이점이 있는지, 그리고 이를 자바스크립트로 어떻게 구현하는지 알아보겠습니다.

연결 리스트란

연결 리스트는 선형적인 데이터 구조라는 점에서 배열과 유사합니다. 하지만 배열과 달리, 연결 리스트의 요소(elements)들은 특정 메모리 주소나 인덱스에 저장되지 않습니다. 오히려 각 요소는 포인터 또는 다음 객체에 대한 링크를 가지는 독립적인 객체에 가깝습니다.

연결 리스트의 각 요소를 노드(node)라 부릅니다. 노드는 일반적으로 데이터 그리고 다음 노드를 가리키는 링크, 이 2가지 아이템으로 구성됩니다. 참고로 데이터의 유형은 다양하게 올 수 있습니다. 아래 도표를 보겠습니다.

연결 리스트의 가장 첫 번째 지점을 헤드(head)라 부릅니다. 헤드는 연결 리스트의 첫 번째 노드를 의미합니다. 마지막 노드는 null을 가르킵니다. 만약 연결 리스트가 비어있는 경우, 헤드는 null을 참조하게 됩니다.

자바스크립트로 연결 리스트를 표현하자면 이렇게 표현할 수 있습니다:

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

연결 리스트의 장점

연결 리스트는 데이터 구조의 큰 틀을 바꾸지 않고 노드를 추가하거나 삭제하기 쉽다는 장점이 있습니다. 이러한 점이 배열과 대비되는 점입니다.

연결 리스트의 단점

연결 리스트는 탐색이 느립니다. 배열과 달리, 연결 리스트는 데이터에 무작위 접근(random access)을 할 수 없기 때문입니다. 노드들은 첫 번째 노드부터 순차적으로만 접근해야 합니다.
연결 리스트는 배열보다 더 많은 메모리를 사용합니다. 왜냐하면 각 노드는 포인터를 담고 있기 때문입니다.

연결 리스트의 유형

연결 리스트는 크게 3가지 유형이 있습니다.

단일 연결 리스트(Singly Linked Lists) : 각 노드는 하나의 포인터만 가집니다. 우리가 위에서 이야기한 유형이 단일 연결 리스트입니다.
이중 연결 리스트(Doubly Linked Lists) : 각 노드는 2개의 포인터를 가지는데, 하나는 다음 노드를 그리고 나머지 하나는 이전 노드를 가르킵니다.
원형 연결 리스트(Circular Linked Lists) : 연결 리스트를 응용한 유형으로, 마지막 노드의 포인터가 첫 노드 또는 특정 노드를 가르키고 있는 마치 루프 형태를 가지는 유형을 말합니다.

자바스크립트로 리스트 노드 구현하기

연결 리스트(Singly Linked Lists의 경우)의 노드는 데이터와 포인터, 총 2개의 요소를 가진다고 했습니다. 자바스크립트로 아래와 같이 구현할 수 있습니다.

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

자바스크립트로 연결 리스트 구현하기

아래는 생성자(constructor)를 사용하여 연결 리스트 클래스를 구현하는 코드입니다. 헤드 노드에 아무 값도 전달하지 않으면 null로 초기화됩니다.

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

함께 사용하기

위에서 만들었던 클래스를 사용해서 연결 리스트를 구현하겠습니다. 우선, node1와 node2 두 개의 노드를 만들어 주세요. 그리고 node1에 node2 를 가르키는 포인터도 만들어 주세요.

let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

그다음, node1를 사용하여 연결 리스트를 만들겠습니다.

let list = new LinkedList(node1)

우리가 만든 리스트에서 노드를 호출해 봅시다.

console.log(list.head.next.data) //returns 5

연결 리스트 메소드들

다음은 연결 리스트를 위한 4개의 헬퍼 메소드를 구현해 보겠습니다.

size()
clear()
getLast()
getFirst()

1. size()

size() 메소드는 연결 리스트에 있는 노드들의 개수를 반환합니다.

size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

2. clear()

clear() 메소드는 리스트를 비우는 역할을 합니다.

clear() {
    this.head = null;
}

3. getLast()

getLast() 메소드는 연결 리스트의 마지막 노드를 반환합니다.

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

4. getFirst()

getFirst() 메소드는 연결 리스트의 첫 번째 노드를 반환합니다.

getFirst() {
    return this.head;
}

마치며

이번 글에서는 연결 리스트가 무엇이고 자바스크립트로 어떻게 구현하는지 알아보았습니다. 그리고 연결 리스트의 다양한 유형들과 각 장단점도 함께 알아보았습니다.

이 글을 재미있게 읽으셨길 바랍니다.

저의 새로운 글에 대한 알람을 받고 싶다면 여기를 클릭해 주세요.