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

• 단일 연결 리스트는 head , tail , length 프로퍼티들을 포함한 자료구조다.
• 단일 연결 리스트는 node 들로 구성되어 있으며, 각각의 node 는 value 와 다른 노드나 null을 향한 pointer 를 갖고 있다.
• 마치 다음 열차와 연결되어 있는 기차와 같다.
• 단일 연결 리스트에는 인덱스가 없다. 예를 들어, 마지막 노드를 찾으려면 첫 노드에서부터 포인터를 통해 다른 노드들을 모두 순차적으로 지니야 한다.
• 연결 리스트의 특징
  1. 연결 리스트는 인덱스가 없다.
     • (반면, 배열은 인덱스가 있다)
  2. 연결 리스트는 무작위 접근이 불가능하다. 즉, 10번째 요소에 접근하려면 처음부터 10번째 요소까지 차례대로 순회하여야 한다.
     • (반면, 배열은 원하는 인덱스의 요소에 무작위 접근이 빠르게 가능하다)
  3. 연결 리스트는 노드와 포인터로 구성되어 있다. 따라서 노드의 삽입이나 삭제는 그 노드의 앞 뒤 노드에만 영향을 미친다.
     • (반면, 배열은 요소의 삽입이나 삭제 시, 기존의 모든 요소들이 인덱스를 다시 받아야 하므로 비용이 더 든다고 볼 수 있다.)
     • 이러한 이유 때문에 아주 긴 데이터에서 무작위 접근은 하지 않고 저장이나 삭제를 주로 한다면, 배열 대신 연결 리스트를 사용하는 것이 효율적일 수 있다.

기본 구조

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

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

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

push 메서드

• push 메서드는 연결 리스트의 맨 뒤에 노드를 추가한다.
• 단일 연결 리스트 push 메서드 자바스크립트 코드

  push(val) {
    // 함수에 전달된 값을 사용하여 새 노드를 생성한다.
    const newNode = new Node(val);
    // head에 값이 없다면 head와 tail이 새로 생성한 노드를 할당한다
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
      // head에 값이 있다면, tail과 추가된 새 노드를 연결하기 위해 
      // 새로 생성했던 노드를 next pointer에 할당하고, 
      // 새로 생성했던 노드를 tail에 할당한다
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    // length를 1씩 증가한다.
    this.length++;

    // 이 연결 리스트(this)를 반환한다.
    return this;
  }
}

• 이 클래스를 이용하여 값들을 push하고 해당 연결리스트를 출력하면 아래의 주석과 같은 형태로 나타난다.

const list = new SinglyLinkedList();
list.push('HELLO');
list.push('MARCO');
list.push('GOODBYE');

console.log(list);

/* 
SinglyLinkedList {
  head: Node { val: 'HELLO', next: Node { val: 'MARCO', next: [Node] } },
  tail: Node { val: 'GOODBYE', next: null },
  length: 3
}
 */

pop 메서드

• pop 메서드는 연결 리스트의 맨 뒤에서 노드를 제거하고, 제거한 노드를 반환한다.

pop() {
  // head가 없으면(=연결리스트의 길이가 0이면) undefined를 반환한다.
    if (!this.head) return undefined;

  // 아래의 반복문을 통해 연결 리스트를 tail까지 순회한다.
    let current = this.head;
    let newTail = current;
    while (current.next) { 
      // 새로운 tail은 current를 가리키도록 한다.
      // (마지막에는 pop된 노드의 직전 노드를 가리키게 된다.)
      newTail = current;
    
      // current가 다음으로 연결된 노드를 가리키도록 한다.
      // (마지막에는 current가 pop될 제일 끝 노드를 가리키게 된다.)
      current = current.next;  
    }
		
  // pop된 노드에 대한 꼬리 자르기
    this.tail = newTail;   // 새 꼬리는 이거야~
    this.tail.next = null;  // 새 꼬리 뒤에 next는 없어~
    this.length--;  // 길이를 1 줄이기

  // 만약 줄여진 길이가 0이라면, 아무 노드도 없다는 것이므로 head와 tail에 null 할당한다.
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }

  // pop된 노드 반환
    return current;
  }

Shift 메서드

• Shift 메서드는 연결 리스트에서 첫 번재 노드를 제거한다. (= head를 삭제한다. = 두 번째 노드를 head로 지정한다)

  shift() {
    if (!this.head) return undefined;
    // 두 번째 노드를 새로운 head로 재할당한다.
    const currentHead = this.head;
    this.head = currentHead.next;
    // 길이를 줄인다.
    this.length--;
    // 만약 길이가 0이 되면 tail도 null로 할당한다. 
    if (this.length === 0) {
      this.tail = null;
    }
    return currentHead;
  }

Unshift 메서드

• 연결 리스트의 첫 번째에 새 노드를 추가한다.(연결 리스트의 구조 덕분에 간단하다)

  unshift(val) {
    const newNode = new Node(val);
    // head가 없을 때(길이가 0), 추가된 노드가 head와 tail이 되도록 예외 설정
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    }


    // 새로운 head가 될 노드의 next 포인터가 원래 head를 가리키도록 한다. 
    newNode.next = this.head;
    // 새 head에 새롭게 head가 될 노드를 할당한다.
    this.head = newNode;
    this.length++;
    return this;
  }

Get 메서드

• 연결 리스트에서 위치를 통해 노드를 반환받는다.
  • 연결리스트의 특성상 개별 요소에 상응하는 인덱스는 존재하지 않는다. 따라서 그 위치까지 순회(루프)하여 노드를 반환받는다.

  get(index) {
    // 입력된 인덱스가 유효한지 체크한다.
    if (index < 0 || index >= this.length) return null;

    // 찾고 있는 인덱스에 상응할 카운터 변수 설정
    let counter = 0;
    let current = this.head;
    // 찾는 인덱스와 카운터가 같기 전까지 
    // current의 next를 반복문을 통해 계속 순회한다.
    while (counter !== index) {
      current = current.next;
      counter++;
    }
    return current;
  }

Set 메서드

• 연결 리스트에서 특정 위치의 노드의 값를 변경한다.
  • 위에서 만든 get 메서드를 사용한다.

  set(index, val) {
    // get 메서드를 사용하여 foundNode가 해당 인덱스의 노드를 가리키도록 한다.
    const foundNode = this.get(index);
    // 입력된 값을 foundNode의 val에 재할당하고 true를 반환한다.
    if (foundNode) {
      foundNode.val = val; 
      return true;
    }
    // 입력된 index에 노드가 없으면 false 반환
    return false;
  }

Insert 메서드

• 연결 리스트의 특정 위치에 노드를 삽입한다.

  insert(index, val) {
    // 입력된 인덱스가 유효한지 체크한다.
    if (index < 0 || index > this.length) return false;
    // 입력된 인덱스가 길이와 같다면, push 메서드 사용하고 형 변환을 통해 true를 반환한다.
    if (index === this.length) return !!this.push(val);
    // 입력된 인덱스가 0이라면, unshift 메서드 사용하고 형 변환을 통해 true를 반환한다.
    if (index === 0) return !!this.unshift(val);

    const newNode = new Node(val);
    // 직전 인덱스의 노드도 추적한다(prev)
    const prev = this.get(index - 1);
    // temp가 직전 인덱스의 다음 노드(=입력된 인덱스에 있는 노드)를 가리키게 한다.
    const temp = prev.next;
    // 직전 인덱스의 노드의 next 포인터가 새로 삽입한 노드를 가리키도록 한다.
    prev.next = newNode;
    // 새로 삽입한 노드의 next 포인터가 원래 해당 인덱스에 위치했던 노드(temp)를 가리키게 한다.
    newNode.next = temp;
    this.length++;
    return true;
  }

Remove 메서드

• 연결 리스트에서 특정 위치에 있는 노드를 삭제한다.
  • A→B→C 노드로 된 연결리스트가 있다고 했을 때, B 노드를 삭제하려고 할 경우
    • A→C가 되도록 해야 한다.

  remove(index) {
    // 입력된 인덱스가 유효한지 체크한다.
    if (index < 0 || index >= this.length) return undefined;
    // 입력된 인덱스가 0이면 shift 메서드를 사용한다.
    if (index === 0) return this.shift();
    // 입력된 인덱스가 끝 인덱스와 같다면 pop 메서드를 사용한다.
    if (index === this.length - 1) return this.pop();
    // previousNode 변수가 입력된 인덱스에 있는 노드의 직전 노드(A)를 가리키게 한다.
    const previousNode = this.get(index - 1);
    // removed 변수가 previousNode의 next 노드(B)를 가리키게 한다.
    const removed = previousNode.next;
    // previousNode(A)의 next 포인터가 removed(B)의 next 노드(C)를 가리키게 한다.(A->C) 
    previousNode.next = removed.next;
    this.length--;
    return removed;
  }

Reverse 메서드

• 연결 리스트의 노드 순서를 뒤집기
  • 순회를 하면서 하나씩 뒤집어 놓는 방법을 사용한다.

  reverse() {
    // node 변수가 head를 가리키게 한다.
    let node = this.head;
    // head는 tail을 가리키게 한다.
    this.head = this.tail;
    // tail은 node 변수에 저장된 기존의 head를 가리키게 한다.
    this.tail = node;
    // 이렇게 해서 head와 tail는 뒤집어졌다.

    let next;
    let prev = null;
    // 연결리스트 길이만큼 각각 노드에 대하여 뒤집는다.
    // next => node.next => prev => node => next
    // 결국 node->node.next로 연결됐던 것을 node.next->node(또는 처음에는 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 라는 포인터로 연결되어 있는 노드들의 연결체다.