Linked List

연결리스트가 리스트보다 빠른 경우

Shift() / Unshift()
리스트의 첫 번째 요소를 삽입,제거하는 경우 연결리스트는 새로 삽입한 node를 head로 지정해주기만 하면 되기 때문에 O(1)의 시간복잡도를 갖고, 리스트는 첫번째 요소를 삽입 또는 제거하고 뒤의 모든 index를 재 설정해줘야 하기 때문에 O(n)의 시간복잡도를 가진다.

리스트가 연결리스트보다 빠른 경우

pop()

연결리스트 : O(n)
리스트 : O(1)

리스트의 경우, 마지막 요소를 제거하는 경우 index를 재설정해줄 필요가 없어 O(1)의 시간복잡도를 갖고, 연결리스트의 경우 마지막 node를 찾기 까지 iterate 한 다음, node를 제거하고 tail을 설정하기 때문에 O(n)의 시간복잡도를 가진다.

Lookup by Index

연결 리스트 : O(1)
리스트 : O(n)

리스트의 경우 index가 부여되어 있기 때문에 index로 요소를 찾는 경우 O(1)의 시간복잡도를 가진다. 연결리스트의 경우, 해당 index의 요소까지 iterate 하므로 O(n)의 시간복잡도를 가진다.

정리

1. 연결 리스트는 원소에 다음 원소에 대한 주소를 할당하여 꼬리물기 처럼 메모리에 저장한다.

2. 배열은 배열 내 원소들에 각각 주소값(index)를 할당하여 메모리에 저장한다.

3. 읽기에서는 배열이 더 빠르다. 왜냐하면 배열은 각 원소에 할당한 index 값으로 원하는 원소에 바로 접근할 수 있기 때문이다. (= 임의의 원소에 접근할 수 있다. 임의접근)

4. 이에 비해 연결 리스트는 하나의 원소가 다음 원소의 주소를 가지고 있기 때문에 특정 위치의 원소를 읽으려면
   그 원소의 주소를 가진 원소에 접근하기까지 많은 원소를 거쳐야한다.(= 주소를 바로 알 수 없다. 순차접근)

5. 하지만 쓰기(입력과 삭제)에서는 리스트가 더 빠르다. 왜냐하면 리스트는 이전 원소가 무엇을 가리키는지 바꾸기만 하면 되기 때문이다.

6. 이에 비해 배열은 배열 중간에 특정 원소가 삽입되려면 나머지 원소들의 위치(index)값이 변경되야 하므로 더 작업이 많고 시간이 걸린다.

7. 즉 읽기를 할 때는 배열이 빠르고, 쓰기를 할 땐 리스트가 빠르다.

8. 연결리스트와 배열의 특성을 고려하여 더 빠르고 효율적으로 알고리즘을 짠다.

class Node {
    constructor(value) {
        this.value =value;
        this.next = null;
    }
}

class LinkedList {
    constructor(value) {
        const newNode = new Node(value)
        this.head = newNode
        this.tail = this.head
        this.length = 1
    }
    push(value){
        const newNode = new Node(value)
        if(!this.head){
            this.head = newNode
            this.tail = newNode
        }else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length ++
        return this
    }
    pop(){
        if(!this.head) return undefined
        let temp = this.head
        let pre = this.head
        while(temp.next){
            pre = temp
            temp = temp.next
        }
        this.tail = pre
        this.tail.next = null
        this.length --
        if(this.length === 0){
            this.head = null
            this.tail = null
        }
        return temp

    }
    unshift(value){
        const newNode = new Node(value)
        if(!this.head){
            this.head = newNode
            this.tail = newNode
        } else{
            newNode.next = this.head
            this.head = newNode
        }
        this.length++
        return this
    
    }
    shift(){
        if(!this.head){
            return undefined
        }
        let preHead = this.head
        let newHead = this.head.next
        this.head = newHead
        preHead.next = null
        this.length--
        if(this.length===0){
            this.tail = null
        }
        return preHead
    }
    get(index){
        let temp = this.head
        if(index <0 || index>this.length-1){
            return undefined
        }else{
            for(let i=0;i<index;i++){
                temp= temp.next
            }
            return temp
        }
    }
    set(index,value){
        let getNode = this.get(index)
        if(getNode){
            getNode.value = value
            return true
        }else{
            return false
        }
    }
       
    insert(index,value){
        if(index===0) return this.unshift(value)
        if(index===this.length) return this.push(value)
        if(index<0 || index > this.length) return false
        const newNode = new Node(value)
        const temp = this.get(index-1)
        newNode.next = temp.next
        temp.next = newNode
        this.length++
        return true
        
        
    }
    remove(index){
        if(index === 0) return this.shift()
        if(index<0 || index>this.length) return undefined
        if(index===this.length-1) return this.pop()
        
        const before = this.get(index-1)
        const temp = before.next
        
        before.next = temp.next
        temp.next = null
        this.length--
        return true

    }
    reverse() {
        let temp = this.head
        this.head = this.tail
        this.tail = temp
        let next = temp.next
        let prev = null
        for(let i=0; i< this.length;i++){
            next= temp.next
            temp.next = prev
            prev = temp
            temp = next
        }
        return this
    }
}