본문 바로가기
Algorithm/Data Structure

[Data Structure / JS] 연결 리스트

도리닥닥 2023. 3. 25. 21:06
728x90

연결리스트 ?

 

연결리스트는 선형 구조로서 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 입니다. 배열이라는 편리한 자료구조가 자바스크립트에서 제공이 되지만 왜 연결리스트가 필요할까 라는 의문이 들 수 있습니다. 배열과 연결리스트의 차이 대해서 알아봅니다.

 

배열과의 차이점

 

1. 메모리 차이

왼쪽은 배열, 오른쪽은 연결리스트

  • 배열은 순차적인 데이터, 즉 메모리 영역이 연속적으로 사용됩니다.
  • 연결리스트는 각 데이터가 퍼져있습니다. 즉, 포인터를 사용하여 각 영역을 참조합니다.

 

2. 요소의 삭제 / 추가

  • 배열은 O(n) 시간이 소요됩니다.
  • 연결리스트의 삭제와 추가는 O(1) 시간이 소요됩니다.

 

연결 리스트의 특징

  • 연결 리스트는 인덱스가 없습니다.
  • 연결 리스트는 무작위 접근이 불가능합니다.
  • 연결 리스트는 노드와 포인터로 구성되어 있다. 따라서 노드의 삽입이나 삭제는 그 노드의 앞 뒤 노드에만 영향을 미칩니다.

 

연결리스트의 구현 in JS

단일 연결리스트

push

  • 주어진 값을 받고 node를 생성합니다.
  • 만약 헤드가 없다면 => 리스트가 비어있다는 것을 의미합니다. 그럴 경우에는 head와 tail을 모두 새 노드를 가리키게 합니다.
  • 헤드가 있다면 마지막 노드(tail)의 next를 새롭게 생성된 노드를 가리키도록 하고 다시 tail이 새로운 값을 기리키게 하고 length를 늘립니다.
  • 시간 복잡도 O(1)
    push(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this
    }

 

pop

  • 리스트에 아무 것도 없을 경우 undefined를 반환합니다.
  • 비어있지 않을 경우 tail까지 전체 리스트를 따라갑니다. 마지막에서 두번째 노드의 next를 null로 설정하고 tail 값을 마지막에서 두 번째 노드로 업데이트합니다.
  • 길이를 하나 감소시킨 다음 방금 제거한 노드를 반환합니다.
  • 리스트에 하나의 노드만 남겨져있다가 제거되었을 경우 헤드와 테일이 null로 설정되어야 합니다.
  • 시간 복잡도 O(n)
    pop() {
        if(!this.head) return undefined;
        let current = this.head;
        let newTail = current;
        while(current.next) {
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return current
    }

 

shift

  • 노드가 없을 경우 undefined를 반환합니다
  • 노드가 존재할 경우 현재의 헤드 속성을 변수에 저장하고 현재 헤드의 next 노드를 가리키도록 헤드 속성을 업데이트
  • 제거된 노드를 반환합니다.
  • 시간 복잡도 O(1)
    shift() {
        if(!this.head) return undefined;
        let currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0) this.tail = null;
        return currentHead;
    }

 

unshift

  • 새로운 노드를 생성하고 헤드가 있는지 없는지를 확인합니다.
  • 헤드가 없을 경우 헤드와 테일 모두 새로운 노드를 기리키도록 설정합니다.
  • 헤드가 있을 경우 새롭게 생성된 노드의 next를 현재의 헤드값으로 설정하고 헤드가 새롭게 생성된 노드를 가리키도록 합니다.
  • 시간 복잡도 O(1);
    unshift(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

 

get

  • 인덱스가 음수이거나 리스트의 길이보다 클 경우는 null을 리턴합니다.
  • 루프를 통해 인덱스가 지정하는 위치에 이를 때까지 반복해서 이동한 다음 해당 인덱스 위치에 있는 노드를 반환합니다.
  • 시간 복잡도 O(N)
    get(index) {
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }

 

set

  • 업데이트할 값과 인덱스를 받습니다.
  • 앞서 만들어 놓은 get 메서드를 활용하여 특정 노드를 찾을 수 있습니다.
  • 노드가 있다면 해당 노드 값을 인자로 받아들인 값으로 업데이트하고, true를 반환합니다.
  • 시간 복잡도 O(N)
    set(index, val) {
        const foundNode = this.get(index);
        if(foundNode) {
            foundNode.val = val;
            return true;
        }
        return false;
    }

 

insert

  • 인덱스와 값 두개의 인자를 받습니다.
  • 범위를 벗어날 경우 삽입이 가능하지 않기 때문에 인덱스가 0보다 작거나 리스트의 길이보다 크거나 같을 경우 false를 반환합니다.
  • 마지막 node에 삽입할 경우 push메서드 , 맨앞에 node에 삽입할 경우 unshift 메서드 활용 가능합니다
  • 인덱스 위치의 앞의 숫자를 불러와야 합니다.
  • 이전 노드의 next가 새롭게 생성된 후 삽입되는 노드를 가리키도록 합니다.
  • 새 노드를 이전의 next 노드로 연결합니다.
  • 시간 복잡도 O(N)
   insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);

        let newNode = new Node(val);
        let prev = this.get(index - 1);
        let temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }

 

remove

  • 인덱스를 인자로 받아서 해당 인덱스의 노드를 제거합니다.
  • 인덱스 값이 0보다 작거나 혹은 리스트 길이보다 클 경우 undefined를 반환합니다.
  • insert와 마찬가지로 인덱스가 0이라면 shift, 길이의 -1 이라면 pop 메서드를 활용할 수 있습니다.
  • 이전 노드를 찾기 위해 index-1을 get() 메소드의 인자로 호출
  • next를 이전 노드의 next로 설정합니다.
  • 제거된 노드를 반환합니다.
  • 시간 복잡도 O(N)
    remove(index) {
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length-1) return this.pop();

        let prevNode = this.get(index-1);
        let removed = prevNode.next;
        prevNode.next = removed.next;
        this.length--;

        return removed;
    
    }

 

reverse

  • 인자를 받지 않고 리스트의 순서를 역으로 변경하는 메서드입니다.
  • 헤드와 테일을 서로 교환하고, next라는 변수를 생성합니다.
  • prev 변수를 생성한다음 node 변수를 생성하고 현재의 헤드 값으로 초기화 시킵니다.
  • 루프를 통해 리스트를 따라가면서 현재 node의 .next를 노드의 next.next로 설정하는 작업을 반복합니다.
  • 현재 노드의 next를 이전에 바로 앞에 있던 노드를 가리키도록 설정합니다.
  • 마지막으로 현재의 노드값을 prev에 저장하고 node의 next값을 저장합니다.
  • 시간 복잡도 O(N)
    reverse() {
        let node = this.head;
        this.head = this.tail;
        this.tail = node;
        let prev = null;
        let next = null;
        for(let i = 0 ; i < this.length; i++) {
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return this;
    
    
    }

 

 

 

완성 코드

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

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push(val) {

        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this
    }

    pop() {
        if(!this.head) return undefined;
        let current = this.head;
        let newTail = current;
        while(current.next) {
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return current
    }

    shift() {
        if(!this.head) return undefined;
        let currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0) this.tail = null;
        return currentHead;
    }

    unshift(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

    get(index) {
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }

    set(index, val) {
        const foundNode = this.get(index);
        if(foundNode) {
            foundNode.val = val;
            return true;
        }
        return false;
    }

    insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);

        let newNode = new Node(val);
        let prev = this.get(index - 1);
        let temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }

    remove(index) {
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length-1) return this.pop();

        let prevNode = this.get(index-1);
        let removed = prevNode.next;
        prevNode.next = removed.next;
        this.length--;

        return removed;
    
    }

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

    print() {
        const arr = [];
        let current = this.head;
        while(current) {
            arr.push(current.val);
            current = current.next;
        }
        console.log(arr);
    }
}

이중 연결리스트

push

  • 값을 가지는 새로운 노드를 만듭니다
  • 헤드가 null인지 확인하고 그렇다면 헤드와 테일 모두 새로 만든 노드로 설정되어야 합니다.
  • 그렇지 않다면 현재 테일을 찾아서 테일의 next를 새로운 노드로 설정해줍니다.
  • 새로만든 노드의 prev를 예전 테일로 설정해줍니다. 테일을 가장 끝에 있게된 새로운 노드로 바꿔줍니다.
  • 시간복잡도 O(1)
    push(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;

        return this;
    }

pop

  • 테일이 없다면 (비어있는 상황) undefined를 출력해줍니다.
  • 그렇지 않다면 현재 테일을 나중에 출력할 수 있도록 변수에 저장해줍니다.
  • 테일이 그 전에 있는 노드가 되도록 설정해줍니다. 새로운 테일의 next를 null로 변경합니다.
  • 시간 복잡도 O(1)
    pop() {
        if(!this.head) return undefined;
        const poppedNode = this.tail;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;

    }

shift

  • 리스트가 비어있다면 undefined를 리턴합니다.
  • 그렇지 않다면 head를 변수에 저장해 줍니다.
  • 길이가 1인 상태에서 제거하게 된다면 헤드와 테일을 null로 바꾸어줍니다.
  • 헤드가 이전 헤드의 next가 되도록 설정합니다. 헤드의 prev를 null로 설정하고, 이전 headd의 next로 설정합니다.
  • 시간 복잡도 O(1)
    shift() {
        if(this.length === 0) return undefined;
        const oldHead = this.head;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }

unshift

  • 입력된 값을 가지는 새로운 값을 만듭니다.
  • 비어있는 리스트라면 헤드와 테일이 새로운 노드가 되도록합니다.
  • 그렇지 않다면 헤드의 prev가 새로운 노드가 되도록 하고 새로운 노드의 next가 현재 헤드가 되도록 합니다.
  • 새로은 노드가 헤드가 되도록합니다.
  • 시간 복잡도 O(1);
    unshift(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;

        return this;
    }

get

  • 인덱스가 유효한지 확인합니다.
  • 0보다 작거나 길이보다 크다면 null을 반환합니다.
  • 그렇지 않다면 리스트의 길이가 절반보다 작거나 같은지 확인합니다.
  • 참이라면 오른쪽으로 가면서 next를 추적합니다. 거짓이라면 왼쪽으로 가면서 prev를 추적합니다.
  • 노드를 찾고 출력합니다.
  • 시간 복잡도 O(N)
    get(index) {
        if(index < 0 || index >= this.length) return null;
        if(index <= this.length/2) {
            let count = 0;
            let current = this.head;
            while(count !== index) {
                current = current.next;
                count++;
            }
            return current;
        } else {
        
            let count = this.length - 1;
            let current = this.tail;
            while(count !== index) {
                current = current.prev;
                count--;
            }
            return current;
        }
    }

set

  • 입력받은 값을 넣은 노드를 생성하고 get메소드의 결과값에 넣습니다.
  • 시간 복잡도 O(N)
    set(index, val) {
        const foundNode = this.get(index);
        if(foundNode !== null) {
            foundNode.val = val;
            return true;
        }
        return false;
    }

insert

  • 인덱스가 유효한지 확인합니다.
  • 유효하지 않다면 false를 출력합니다.
  • 인덱스가 0이라면 unshift, length와 같다면 push 그렇지 않다면 get 메서드를 사용하여 index-1에 접근합니다.
  • next와 prev에 만든 노드를 넣고 length를 증가시킵니다.
  • 시간 복잡도 O(N)
    insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);
        const newNode = new Node(val);
        const prevNode = this.get(index-1);
        const nextNode = prevNode.next;
        prevNode.next = newNode;
        newNode.prev = prevNode;
        newNode.next = nextNode;
        nextNode.prev = newNode;
        this.length++;
        return true;

    }

remove

  • 인덱스가 유효한지 확인합니다.
  • 유효하지 않다면 false를 출력합니다.
  • 인덱스가 0이라면 shift, length-1와 같다면 pop 그렇지 않다면 get 메서드를 사용하여 index -1 에 접근합니다.
  • node를 찾아내고 리스트에서 제거합니다.
  • 찾아낸 node에서 next와 prev 값을 null로 바꾸고 노드를 리턴합니다.
  • 시간 복잡도 O(N)
    remove(index) {
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length-1) return this.pop();
        const removedNode = this.get(index);
        removedNode.prev.next = removedNode.next;
        removedNode.next.prev = removedNode.prev;
        removedNode.next = null;
        removedNode.prev = null;
        this.length--;
        return removedNode;
    }

전체 코드

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

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;

        return this;
    }

    pop() {
        if(!this.head) return undefined;
        const poppedNode = this.tail;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;

    }

    shift() {
        if(this.length === 0) return undefined;
        const oldHead = this.head;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }

    unshift(val) {
        const newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;

        return this;
    }

    get(index) {
        if(index < 0 || index >= this.length) return null;
        if(index <= this.length/2) {
            let count = 0;
            let current = this.head;
            while(count !== index) {
                current = current.next;
                count++;
            }
            return current;
        } else {
        
            let count = this.length - 1;
            let current = this.tail;
            while(count !== index) {
                current = current.prev;
                count--;
            }
            return current;
        }
    }

    set(index, val) {
        const foundNode = this.get(index);
        if(foundNode !== null) {
            foundNode.val = val;
            return true;
        }
        return false;
    }

    insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);
        const newNode = new Node(val);
        const prevNode = this.get(index-1);
        const nextNode = prevNode.next;
        prevNode.next = newNode;
        newNode.prev = prevNode;
        newNode.next = nextNode;
        nextNode.prev = newNode;
        this.length++;
        return true;

    }

    remove(index) {
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length-1) return this.pop();
        const removedNode = this.get(index);
        removedNode.prev.next = removedNode.next;
        removedNode.next.prev = removedNode.prev;
        removedNode.next = null;
        removedNode.prev = null;
        this.length--;
        return removedNode;
    }

}
저작자표시

'Algorithm > Data Structure' 카테고리의 다른 글

[Data Structure / JS] 이진 힙(Binary Heaps) / 우선순위 큐(Priority Queue)  (0) 2023.03.29

'Algorithm/Data Structure' Related Articles

티스토리툴바