[자료구조] 연결 리스트의 개념과 자바스크립트를 통한 구현 (Linked List)

연결 리스트는 이후에 다루게 될 트리(Tree), 그래프(Graph) 등 다른 자료 구조의 밑바탕이 되기 때문에 배열과 함께 가장 먼저 배우게 되는 자료구조이다. 또한 스택(Stack), 큐(Queue) 그리고 해시 테이블(Hash Table)에도 적용 가능하다고 하니 최대한 자세하게 다뤄보도록 하겠다.

연결 리스트란

• 연결 리스트는 배열처럼 여러 개의 값을 순서대로 지정하기 위한 자료 구조이다.

• 배열 구조에서는 데이터가 정적 공간의 메모리에 순서대로 응집돼 저장된다면, 연결 리스트는 데이터가 메모리에 흩어져서 저장되는 방식이다.

• 노드(Node)를 하나의 데이터 단위로 사용하며, 노드에는 데이터의 값(Value)과 다음 노드를 가리키는 포인터(Pointer)로 구성되어 있다.

• 포인터는 참조하는 노드의 메모리상 위치를 가리킨다. 자바스크립트는 포인터 개념이 없으므로 참조로 이를 대신한다.

연결 리스트와 배열의 차이점

(업데이트 예정 - 각각의 장단점 비교)

연결 리스트 종류

포인터가 가리키는 방향에 따라 종류를 구분한다.

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

  한 방향으로 포인터가 다음 노드만 참조하는 구조이다. (장점)

• 양방향 연결 리스트 (Doubly Linked List)

  양 방향의 두 포인터가 각각 이전과 다음 노드 참조하는 구조이다. (장점)

• 순환 연결 리스트 (Circular Linked List)

  마지막 노드의 포인터가 첫 노드를 참조하여 첫 지점(head)으로 순환 가능한 구조이다. (장점)

데이터 읽기와 쓰기 (Read, Write)

나는 이 포스팅에서 단일 연결 리스트를 구현할 것이다. 그래서 단일 연결 리스트를 기준으로 읽기 ・ 쓰기 방법과 시간 복잡도를 설명했다.

• 탐색(Lookup)

  데이터가 메모리에 흩어져 저장돼 있으므로 포인터 값을 처음부터 체이닝(참조를 계속 따라가기)하면서 값을 확인하는 과정을 거쳐야 한다.

  찾고자 하는 데이터가 가장 마지막 노드에 있을 수 있으므로 최대 O(n)의 시간 복잡도를 가진다.

연결 리스트는 해당 위치에 접근 후 쓰기가 가능한 구조이기 때문에, 여기서는 원하는 위치에 접근이 된 상태라 가정하겠다.

• 삽입(Insert)

  먼저 새로운 노드를 만들고, 포인터 값을 기존 노드가 참조하고 있는 노드로 할당한다. 그 다음, 기존 노드의 포인터 값을 새로운 노드로 재할당한다.

  • 리스트 중간에 데이터를 삽입할 경우

    삽입할 위치에 접근이 되었다 가정했기 때문에 삽입 연산은 데이터 크기에 상관없이 어디서든 동일하다. 그래서 O(1)의 시간 복잡도를 가진다. 하지만 가정을 하지 않는다면 접근 + 삽입이 이뤄져야 하므로 최대 O(n) 만큼 시간 복잡도를 가지게 된다.

  • 리스트 맨 앞 혹은 마지막에 삽입할 경우

    시작점 head 또는 끝점 tail 속성을 이용하면 되므로 탐색 연산이 필요없다. 그러므로 가정과 상관없이 O(1)의 시간 복잡도를 가진다.

• 삭제(Remove)

  먼저 삭제할 노드를 참조하고 있는 앞 노드에 접근한다. 그 다음, 앞 노드의 포인터 참조를 삭제할 노드의 다음 노드로 재할당한다. 이후, 삭제할 노드는 완전히 참조 관계가 끊어졌기 때문에 메모리에서 GC(Garbage Collecting) 된다.

  • 리스트 중간에 있는 데이터를 삭제할 경우

    삽입과 마찬가지다. 삭제 연산 자체로는 O(1)의 시간 복잡도를 가지지만, 접근 + 삭제 연산은 최대 O(n)의 시간 복잡도를 가진다.

  • 리스트 맨 앞 혹은 마지막의 데이터를 삭제할 경우

    삽입과 마찬가지다. head 혹은 tail 속성을 이용하면 되므로 O(1)의 시간 복잡도를 가진다.

단일 연결 리스트 구현하기

• 속성

  • head
  • tail

• 메소드

  • addToTail
  • removeHead
  • find
  • size

• 코드

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  push(...values) {
    for (let value of values) {
      const node = new Node(value);
      if (this.head === null) {
        this.head = node;
        this.tail = node;
      } else {
      	this.tail.next = node;
        this.tail = node;
      }
    }
  }
  pop() {
  	const currentTail = this.tail;
    this.tail = this.tail.next || null;
    if (this.tail) this.head = null;
    return currentTail.value;
  }
  unshift(...values) {
  	for (let value of values) {
      const node = new Node(value);
      if (this.tail === null) {
          
      }
    }
  }
  shift() {
    const currentHead = this.head;
    this.head = currentHead.next || null;
    if (this.head === null) this.tail = null;
    return currentHead.value;
  }
  size() {
  
  }
}