연결 리스트 with Javascript

연결 리스트

연결리스트(Linked List)는 각 노드의 연결을 통해 리스트를 구현한 것이다. 자바스크립트 배열은 가변적이지만 C나 C++ 등의 전통적 언어에서 배열은 고정된 크기를 갖는 것이 일반적이다. 따라서 배열 대신 연결 리스트를 이용하면 실행 시간에 동적으로 메모리를 할당하고 해제할 수 있다는 장점이 있다.

 

Linked List

생성

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

class LinkedList{
    constructor(){
        this.head = null
        this.size = 0
    }
    isEmpty(){
        return this.size == 0
    }
}

리스트와 리스트에 담길 노드에 해당하는 클래스를 하나씩 만들어준다. LinkedListNode는 자신의 데이터 값과 다음 노드에 대한 포인터를 멤버로 가진다. 그리고 LinkedList는 연결의 시작점이 되는 head와 전체 리스트의 크기를 나타내는 size를 멤버로 가진다.

 

삽입

insert(value){
        if(this.isEmpty()){
            this.head = new LinkedListNode(value)
            this.size++
        }
        else{
            let tmp = this.head
            this.head = new LinkedListNode(value)
            this.head.next = tmp
            this.size++
        }
}

리스트가 비었으면 헤드에 바로 새로운 노드를 추가해주면 된다. 그렇지 않은 경우에는 원래 헤드를 헤드의 다음 칸으로 미뤄주고 삽입하는 값을 헤드로 바꿔준다. 순회가 필요없으므로 상수 시간에 처리 가능하다. 따라서 연결리스트 요소 삽입의 시간복잡도는 O(1)이다.

 

값에 의한 삭제 (Remove by value)

 

remove by value

remove(value){
        let current = this.head

        if(current.data == value){
            this.head = current.next
            this.size--
        }
        else{
            let prev = current
            let error = true

            while(current.next){
                if(current.data == value){
                    prev.next = current.next
                    current = current.next
                    error = false
                    break
                }
                prev = current
                current = current.next
            }
            if(current.data == value){
                prev.next = null
                error = false
            } 

            if(error) console.log(`There is no ${value}`) 
            else this.size--
        }
}

값에 의해 노드를 삭제를 수행하려면 헤드부터 시작해서 리스트를 순회해야한다. 삭제하려는 값이 운좋게 헤드에 있다면 루프를 돌지 않고 그대로 처리할 수 있다. 그렇지 않다면 삭제하려는 값을 찾을 때까지 계속해서 노드를 다음으로 갱신해주어야 한다. 원하는 값을 찾았다면 현재 노드 이전 노드의 next가 현재 노드의 next를 가리키게 하고, 현재 노드는 현재 노드 다음 노드로 채워주면 끝이다. 마지막으로 순회를 다 마쳤는데도 원하는 값을 얻어내지 못했다면 에러 메세지를 출력한다. 연결리스트 요소 삭제의 시간복잡도는 O(n)이다.

 

헤드 삭제(Remove at head)

removeHead(){
        let value = null
        if(this.head != null){
            value = this.head.data
            this.head = this.head.next
            this.size--
        }
        return value
}

특정 값과 무관하게 단순히 헤드 항목을 삭제하는 것은 O(1) 시간에 가능하다. 헤드는 리스트를 순회하지 않고도 바로 알 수 있기 때문이다. 이는 곧 스택에서의 pop() 메소드를 구현하는 것과 같다.

 

검색

search(value){
        let current = this.head
        while(current.next){
            if(current.data == value) return true
            current = current.next
        }
        return false
}

리스트를 돌면서 값의 존재 여부를 반환한다. 전체 리스트를 순회해야하므로 시간복잡도는 O(n)이다.

출력

print(){
        let result = ""
        let current = this.head

        while(current.next){
            result += `${current.data} => `
            current = current.next
        }
        result += current.data

        console.log(result)
}

연결 리스트의 각 요소들을 순서대로 출력하려면 리스트를 순회하면서 출력 결과를 생성해주면 된다. 마찬가지로 시간복잡도는 O(n)이다.

 

 

전체 소스 (테스트 코드)

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

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

    isEmpty(){
        return this.size == 0
    }

    insert(value){
        if(this.isEmpty()){
            this.head = new LinkedListNode(value)
            this.size++
        }
        else{
            let tmp = this.head
            this.head = new LinkedListNode(value)
            this.head.next = tmp
            this.size++
        }
    }

    remove(value){
        let current = this.head

        if(current.data == value){
            this.head = current.next
            this.size--
        }
        else{
            let prev = current
            let error = true

            while(current.next){
                if(current.data == value){
                    prev.next = current.next
                    current = current.next
                    error = false
                    break
                }
                prev = current
                current = current.next
            }
            if(current.data == value){
                prev.next = null
                error = false
            } 

            if(error) console.log(`There is no ${value}`) 
            else this.size--
        }
    }

    removeHead(){
        let value = null
        if(this.head != null){
            value = this.head.data
            this.head = this.head.next
            this.size--
        }
        return value
    }

    search(value){
        let current = this.head
        while(current.next){
            if(current.data == value) return true
            current = current.next
        }
        return false
    }

    print(){
        let result = ""
        let current = this.head

        while(current.next){
            result += `${current.data} => `
            current = current.next
        }
        result += current.data

        console.log(result)
    }
}

(function test(){
    let ll = new LinkedList()

    for(let i=1; i<=5; i++) ll.insert(i) 
    ll.print() // 5=>4=>3=>2=>1

    ll.remove(3) 
    ll.print() // 5=>4=>2=>1

    ll.removeHead()
    ll.print() // 4=>2=>1

    ll.remove(5) //error!
})()

테스트 결과

---

정리

연결 리스트는 다른 노드에 대한 next 포인터를 지닌 각 노드에 의해 동작한다. 따라서 배열처럼 인덱스(index) 개념이 없으므로 삽입과 삭제 연산을 보다 유연하게 처리할 수 있다. 연결 리스트에서 삽입과 삭제는 상수 시간에, 삭제와 검색은 O(n) 안에 처리할 수 있다.

시간복잡도	삽입	삭제	헤드 삭제	검색
Linked List	O(1)	O(n)	O(1)	O(n)