LinkedList Data Structure

About LinkedList

자바스크립트에서 리스트는 배열로 구현한다.

다른 언어에서 배열은 길이가 정해져 있어 배열에 저장하는 데이터가

가변적이라면 메모리에 낭비 또는 초과를 일으킨다.

이러한 문제를 개선하기위해 LinkedList 를 사용 할수있다.

기차의 형태를 연상하면 이해하기 쉬우며 추가,삭제가 용이 하지만

특정 요소 접근이나 검색은 비효율적이다.

 

LinkedList 는 Node 라는 객체의 집합인데 각 객체간 연결이 되어 있는

방식이기때문에 요소를 참조할뿐 인덱스를 부여받는것이 아니기 때문이다.

let arr = ["hello","world","javascript"];
let head =  { element: "head" , next: Node1 }
let Node1 = { element: "hello", next: Node2 }
let Node2 = { element: "world", next: Node3 }
let Node3 = { element: "javascript", next: null }

arr 은 배열 이다 world 에 접근하기위해선 배열생성시 부여된 인덱스 번호만 알고 있으면 된다. arr[1]

Node1 ~ Node3 은 LinkedList 를 표현하기 위해 임의로 정의한 객체 이다

world에 접근하기 위해선 head로 부터 element 값이 world인 객체를 next로 참조 해서 찾아가야 한다.

More About

일반적인 링크드 리스트는 단방향 으로 구현 되며 기준이되는 head 로 시작해서 null 로 끝나게 된다.

이를 개선하기 위해 양방향 리스트 를 사용 할수 있는데 양방향 리스트는 Node에 previous 를 추가하여 코드를 개선 시킨다.

양방향 리스트는 코드가 복잡해 질수 있는 단점이 있는데 상황에 따라 순환 구조인 순환형 리스트 를 사용할수 있다.

순환형 리스트는 단방향 리스트의 끝인 null 포인트를 시작점인 head로 지정하여 순환형태를 만든다.

 

ADT (Abstract Data Type)

methodname	contents
append(element)	노드의 끝에 새로운 노드를 추가한다
insert(position, element)	원하는 위치에 새로운 노드를 추가한다
remove(element)	노드를 삭제 한다.

핵심 메소드만 설명 하였습니다.

implementation

//ES6
class Node {
    constructor(el) {
        this.element = el
        this.next = null
        this.prev = null //doubly new
    }
}

class LinkedList {
    constructor() {
        this.length = 0
        this.head = null
        this.tail = null //doubly new
    }

    append(element) {
        let node = new Node(element),
            current = null

        if (this.head == null) {
            this.head = node
        } else {
            current = this.head

            while (current.next) {
                current = current.next
            }
            current.next = node
        }

        this.length++
    }

    remove(element) {
        var index = this.indexOf(element)
        return this.removeAt(index)
    }

    removeAt(position) {
        if (position > -1 && position < this.length) {
            let current = this.head,
                previous,
                index = 0

                if (position === 0) {
                    this.head = current.next

                    if (this.length === 1) { //doubly new
                        this.tail = null
                    } else {
                        this.head.prev = null
                    }
                } else if (position === length-1) {
                    current = this.tail
                    this.tail = current.prev
                    this.tail.next = null
                } else {

                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }

                    previous.next = current.next
                    current.next.prev = previous
                }

                length--

                return current.element
        } else {
            return null
        }
    }

    insert(position, element) {
        if (position >= 0 && position <= this.length) {
            var node = new Node(element),
            current = this.head,
            previous,
            index = 0

            if(position === 0) {

                if (!this.head) { //doubly new
                    this.head = node
                    this.tail = node
                } else {
                    node.next = current
                    current.prev = node 
                    this.head = node
                }
            } else if (position === this.length) { //doubly new
                current = this.tail
                current.next = node
                node.prev = current
                this.tail = node

            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                node.next = current
                previous.next = node

                current.prev = node //doubly new
                node.prev = previous //doubly new
            }
            length++

            return true
        } else {
            return false
        }
    }

    toString() {
        var current = this.head,
            string = ''

            while (current) {
                string = current.element
                current = current.next
            }
            return string
    }

    indexOf(element) {
        var current = this.head,
            index = -1

            while (current) {
                if (element === current.element) {
                    return index
                }
                index++
                current = current.next
            }

            return -1
    }

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

    size() {
        return this.length
    }

    getHead() {
        return this.head
    }

    advance(n) {
        for (;;) {
            if (n <= 0) break
            this.head = this.head.next
            n--
        } 
    }

    back(n) {
        for (;;) {
            if (n <= 0) break
            this.head = this.head.prev
            n--
        }
    }

    show() {
        return this.head.element
    }

}