(JS 자료구조)단일 연결 리스트

단일 연결 리스트(Singly linked list)

• 단일 연결 리스트는 head , tail , length 프로퍼티들을 포함한 자료구조다.

• 단일 연결 리스트는 node 들로 구성되어 있으며, 각각의 node 는 value 와 다른 노드나 null을 향한 pointer 를 갖고 있다.

• 단일 연결 리스트에는 인덱스가 없다. 예를 들어, 마지막 노드를 찾으려면 첫 노드에서부터 포인터를 통해 다른 노드들을 모두 순차적으로 지나야 한다.

• 연결 리스트 특징

  • 연결 리스트는 인덱스가 없다.(반면, 배열은 인덱스가 있다)

  • 연결 리스트는 무작위 접근이 불가능하다. 즉, 10번째 요소에 접근하려면 처음부터 10번째 요소까지 차례대로 순회하여야 한다.
    (반면, 배열은 원하는 인덱스의 요소에 무작위 접근이 빠르게 가능하다)

  • 연결 리스트는 노드와 포인터로 구성되어 있다. 따라서 노드의 삽입이나 삭제는 그 노드의 앞 뒤 노드에만 영향을 미친다.
    (반면, 배열은 요소의 삽입이나 삭제 시, 기존의 모든 요소들이 인덱스를 다시 받아야 하므로 비용이 더 든다고 볼 수 있다.)

• 이러한 이유 때문에 아주 긴 데이터에서 무작위 접근은 하지 않고 저장이나 삭제를 주로 한다면, 배열 대신 연결 리스트를 사용하는 것이 효율적일 수 있다.

기본구조

• Node 클래스의 constructor
  • 연결 리스트를 구성하는 기본 자료구조인 Node 클래스를 정의하고, 필요한 곳에서 인스턴스화하여 사용한다.
  • value는 this.val에 할당하고, 다음으로 연결된 노드에 대한 pointer는 this.next에 할당한다.
• SinglyLinkedList의 construcotr
  • head, tail, length 프로퍼티

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

SinglyLinkedList

• 여러 메소드를 자바스크립트 코드로 작성해보자.

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
  //연결리스트의 맨 뒤에 노드 추가
    push(val){
      let 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;
    }
//연결리스트의 첫 번째 노드를 제거(head 교체)
    shift(){
        if(!this.head) return undefined;
        let nexthead = this.head;
        this.head = nexthead.next;
        this.length--;

        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }

        return nexthead;
    }
//연결리스트이 첫 번째에 새 노드를 추가한다.
    unshift(val){
        let firstNode = new Node(val);

        if(!this.head){
            this.head = firstNode;
            this.tail = this.head;
        }else{
            firstNode.next = this.head;
            this.head = firstNode;
        }
        this.length++;
        return this;
    }
//연결리스트에서 위치를 통해 노드를 반환받음
//인덱스가 존재하지 않기 때문에 그 위치까지 순회해야함
    get(index){
        if(index < 0 || index >= this.length){
            return null;
        }
        let count = 0;
        let result = this.head;
        while(count!==index){
            result = result.next;
            count++;
        }
        return result;
    }
//특정 위치의 노드의 값을 변경한다
    set(index,val){
        let foundindex = this.get(index);
        if(foundindex){
            foundindex.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);
        
        let insertNode = new Node(val);
        let previous = this.get(index-1);
        let temp = previous.next;
        previous.next = insertNode;
        insertNode.next = temp;
        this.length++;
        return true;
    }
//연결리스트 특정 위치에 있는 노드를 삭제
    remove(index){
        if(index < 0 || index >= this.length) return false;
        if(index === 0) return !!this.shift();
        if(index===this.length-1) return !!this.pop();

        let preremove = this.get(index-1);
        let remove = preremove.next
        preremove.next = remove.next;
        
        this.length--
        return remove;
    }
//연결리스트 노드 순서 뒤집기
    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;
    }
}

단일 연결 리스트 성능

• 시간복잡도
• 삽입(제일 앞이나 뒤에) : O(1)
  • 단일 연결리스트는 제일 앞이나 뒤에 노드 추가를 할 때, O(1)의 시간 복잡도를 갖는다.
  • 배열의 경우, 제일 앞에 노드 추가는 O(N)의 시간 복잡도를 갖는다. 따라서 삽입의 경우 단일 연결 리스트가 유리하다.(인덱스 수정 필요)
• 제거(제일 앞이나 뒤에) : 첫 번째 노드 제거는 O(1), 마지막 노드 제거는 O(N)
  • 단일 연결리스트는 제일 앞에서 노드를 제거하면 O(1)의 시간 복잡도를 갖고, 제일 뒤에서 노드를 제거하면 O(N)의 시간복잡도를 갖는다(제일 뒤에서 두 번째에 있는 노드를 처음부터 순회해야 하므로) .
• 탐색 : O(N)
• 접근 : O(N)
  • 배열에서는 인덱스로 접근을 하므로 동일한 시간인 O(1)만 소요된다.

결론

• 단일 연결 리스트는 삽입과 제거라는 분야에서 배열보다 성능이 앞선다.
• 배열에는 내장 인덱스가 있지만, 단일 연결 리스트에는 내장 인덱스가 없다. 단일 연결 리스트는 서로가 next 라는 포인터로 연결되어 있는 노드들의 연결체다.