[Data Structure] Linked List

연결리스트(Linked List)는 노드(Node)의 연결로 이루어진 자료구조이다. 연결리스트는 데이터의 추가와 삭제에 대해 O(n)(선형 시간)의 시간 복잡도를 갖는 배열과 달리, O(1)(상수 시간)의 시간 복잡도를 갖는다. 다만 추가와 삭제 속도가 더 빠른 대신, 연결리스트의 각 노드는 인덱스를 갖지 않는다. 따라서 연결리스트에서 어떤 특정 데이터를 검색하고자 할 경우, 처음부터 전체 연결리스트를 훑어야하는 O(n)(선형 시간)의 복잡도를 필요로 한다.

노드(Node)는 Head(첫번째 노드)와 Tail(마지막 노드)로 구성되어 있으며, 각 노드는 다음 노드를 가리키는 포인터(Next)를 가지고 있다.

이미지 출처: codestates urclass

연결리스트에는 단일 연결리스트(Singly-Linked List)와 이중 연결리스트(Doubly-Linked List) 등의 종류가 있다.

단일 연결리스트(Singly-Linked List)

이미지 출처: 필자 제작

• 단일 연결리스트는 각 노드를 선형(linear)으로 연결한 것으로, 각 노드에는 다음 연결리스트를 가리키는 포인터(Next)가 포함되어 있다.
• 기존 배열에 비해 특정 지점에 요소를 추가하거나 삭제하기가 용이하다.
• 포인터로 다음 연결리스트를 지정해야하기 때문에 배열보다 더 많은 메모리를 사용한다.
• 이전 노드 값을 확인하기 위해서는 전체 목록을 처음부터 다시 순서대로 읽어야 한다.

이중 연결리스트(Doubly-Linked List)

이미지 출처: 필자 제작

• 이중 연결리스트는 하나의 노드에 이전 노드(Previous)와 다음 노드(Next)를 가리키는 두 개의 포인터가 존재한다.
• 따라서 단일 연결리스트와 다르게 이전 노드의 링크를 통해 O(1)의 시간 복잡도로 이전 노드를 찾을 수 있다.
• 음악 재생목록 구현(곡 건너뛰기, 다음 곡 재생, 재생목록에 음악 추가, 한 곡의 시작과 끝 구분 등)에 적용할 수 있다.

JS 코드 구현

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }
//주어진 값을 연결 리스트의 끝에 추가
  addToTail(value) {
    let node = new Node(value);
    //리스트가 없는 경우, head와 tail 생성
    if(this.head === null){ 
      this.head = node;
      this.tail = node; 
   //리스트가 있는 경우, tail을 추가하고 포인터 설정
    }else{
      this.tail.next = node;
      this.tail = node; 
    }
    this._size++;
    return this;
  } 
//주어진 값을 찾아서 연결을 해제(삭제)
  remove(value) {
    if(this.head === null){
      return undefined;
    } else if(value === this.head.value){
      this.head = this.head.next;
    }
    this._size--;
    return this;
  }
//주어진 인덱스의 노드를 찾아서 반환
  getNodeAt(index) {
    let list = this.head;
    if(index > this._size){
      return undefined;
    } else {
      for(let i = 0; i < index; i++){
        list = list.next;
      }
    }
    return list;
    }
//연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환
  contains(value) {
    let list = this.head;
    while(list){
      if(value === list.value){
        return true;
      } else {
        list = list.next;
      }
    }
    return false;
  }
//주어진 값의 인덱스를 반환, 없을 경우 -1을 반환
  indexOf(value) {
    let list = this.head; 
    let count = 0;
    while(list){
      if(value === list.value){
        return count;
      }else{
        list = list.next;
        count++
      }
    }
    return -1;
  }

  size() {
    return this._size;
  }
}