5. Linked List

배열의 추가, 삭제의 선형 시간 소요의 단점을 보완하기 위한 자료구조

배열은 추가, 삭제가 선형적인 소요 시간을 갖는다. 추가, 삭제가 자주 발생하는 로직의 경우 시간 복잡도가 상당히 커지게 된다. 이러한 단점을 보완하고자 등장한 자료구조가 연결 리스트이다.

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다. 각 요소는 노드라고 부르며 데이터 영역, 포인터 영역으로 나뉜다.

연결 리스트 자료구조

탐색, 추가, 삭제의 시간 복잡도

연결 리스트는 배열과 다른점이 있다면, 메모리가 허용하는한 요소를 제한없이 추가할 수 있다. 배열의 경우 탐색 시간 복잡도는 요소의 인덱스를 알고 있다는 가정하에 O(1) 이지만, 연결 리스트는 탐색에서 O(n) 의 시간 복잡도를 갖는다. 반대로 O(n) 의 시간 복잡도를 갖는 배열의 요소 추가, 삭제와는 달리, 연결 리스트는 O(1) 의 시간 복잡도를 갖는다. 결론적으로 추가, 삭제에 배열보다 유리한 자료구조임을 알 수 있다.

메모리 영역

연결 리스트는 연속적인 메모리 영역을 갖는 배열과는 달리 분산된 메모리 영역을 갖는다.

연결 리스트의 종류

연결 리스트는 단순 연결 리스트, 이중 연결 리스트, 순환 연결 리스트 등 다양한 구조로 구현될 수 있다. 아래 링크를 참고하자.

https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8#s-3

연결 리스트 구현 코드

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  find(value) {
    let currNode = this.head;
    
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    
    return currNode;
  }
  
  append(newValue) {
    const newNode = new Node(newValue);
    
    if (this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  
  insert(node, newValue) {
    const newNode = new Node(newValue);
    
    newNode.next = node.next;
    node.next = newNode;
  }
  
  remove(value) {
    let prevNode = this.head;
    
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }
    
    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    } 
  }
  
  display() {
    let currNode = this.head;
    let result = '[';
    
    while (currNode !== null) {
      result += `${currNode.value}, `;
      currNode = currNode.next;
    }
    
    result = result.substr(0, result.length -2);
    result += ']';
    console.log(result);
  }
}

const linkedList = new SinglyLinkedList();

linkedList.append(1);
linkedList.append(2);
linkedList.append(4);
linkedList.append(5);

linkedList.display(); // '[1, 2, 4, 5]'

linkedList.insert(linkedList.find(2), 3);
linkedList.remove(5);

linkedList.display();  // '[1, 2, 3, 4]'