자료구조 2. Linked List

1. Linked List

Linked List

  연결 리스트(Linked List)는 저장된 데이터 간의 연결이 존재하는 형태로 데이터를 저장하는 자료구조이다. 연결 리스트에 저장되는 데이터 형태를 자세히 들여다보면 다음과 같다.

 

Linked List의 Node

  연결 리스트는 데이터를 그대로 저장하는 것이 아니라 Node라는 형태로 저장한다. 노드는 Data와 다음 노드와의 연결인 Link로 구성되어있다. 링크를 통해 데이터의 연결 및 순서가 발생하며 순서상 가장 앞에 있는 노드는 Head, 가장 뒤에 있는 노드는 Tail이라 한다. 

 

2. vs Array

  순서가 있는 데이터라는 점에서 배열과 연결 리스트는 매우 유사한 구조로 보인다. 그러나 몇 가지 차이점이 존재한다.

1) 메모리

배열과 연결 리스트의 메모리 상태

   배열과 연결 리스트에 각각 1, 2, 3, 4 라는 데이터를 넣었을 때 메모리상에는 위의 그림과 같이 저장된다. 배열의 경우 반드시 각 데이터들이 연속으로 위치하여있어야한다. 그러나 연결 리스트의 경우 각 데이터들이 연속으로 위치할 필요가 없다. 노드에서 다음 데이터의 위치를 저장하기 때문이다. 위의 Linked List는 다음과 같은 형태를 갖는다.

 

 

Linked List

   데이터들의 메모리 배치가 자유롭다는 특성 때문에 연결 리스트는 데이터의 삽입과 삭제가 배열에 비해 용이하다. 위 연결 리스트의 2번 노드와 3번 노드 사이에 7이라는 데이터를 삽입해보자.

 

Linked List의 데이터 삽입

  위의 연결 리스트에서 2번째 노드와 3번째 노드 사이에 7이라는 데이터를 삽입하기 위해 데이터 7을 가진 노드를 메모리에 할당 후 2번 노드의 링크를 데이터 7을 가진 노드의 주소인 @407을 가리키도록 변경하고, 데이터 7을 가진 노드의 링크는 원래 3번째 노드의 주소인 @203을 가리키도록 변경하였다. 즉, 연결 리스트에서 데이터 삽입, 삭제 시 기존 데이터의 메모리 이동 없이 링크가 가리키는 노드를 변경해주면 된다. 반면, 배열의 경우 메모리를 연속적으로 할당해주어야하기 때문에 중간에 데이터를 삽입하기 위해서는 기존 데이터들의 메모리 이동(Shift)이 필요하다. 또한 배열은 고정된 크기를 가지고 있어 데이터 삽입에 제한이 있다. 배열의 길이가 5칸이라면 6개의 데이터를 넣을 수 없는 것이다. 그러나 연결 리스트의 경우 크기 제한 없이 무한하게 데이터를 저장가능하다.

 

   마지막으로 배열보다 연결 리스트가 메모리를 더 효율적으로 사용할 수 있다. 예를 들어 4칸 짜리 배열이 있는데 2칸만 사용한다 하더라도 나머지 2칸의 메모리를 배열이 차지하고 있다. 반면, 연결 리스트는 메모리를 동적으로 할당하여 2칸만 사용한다면 연결 리스트는 2칸의 메모리만 차지한다. 연결 리스트는 할당된 메모리를 모두 활용하고 있는 것이다. (단, 총 메모리 할당량 측면에서는 연결리스트의 경우 데이터 외의 링크에 대한 메모리도 차지하므로 같은 데이터를 저장하더라도 더 많은 메모리를 사용한다.)

 

결론적으로 연결 리스트는 메모리 활용면, 데이터 수정면에서 배열보다 더 효율적이다.

 

2) 데이터 접근 속도

Array와 Linked List에서 3 찾기

   배열은 탐색, 정렬 면에서 연결리스트보다 용이하다. 데이터에의 접근이 빠르기 때문이다. 예를 들어 1, 2, 3이 들어있는 배열과 연결 리스트에서 3을 찾아보자. 위처럼 배열은 배열의 첫번째 요소부터 차례대로 2번만 거치면 3을 찾아낼 수 있다. 배열의 인덱스(오프셋)만 증가시키면 다음 요소로 이동할 수 있기 때문이다. 그러나 연결 리스트의 경우 첫번째 노드부터 4번을 거쳐야 3에 도달할 수 있다. 노드의 데이터를 확인 후 노드의 링크로 이동하여 다음 노드의 위치를 확인해주어야 하기 때문이다. 정렬도 위와 같은 이유 때문에 배열이 연결리스트보다 빠르고 쉽다.

 

결론적으로 연결 리스트는 데이터 접근 속도 측면에서 배열보다 비효율적이다.

 3) 활용

   배열과 연결 리스트는 서로다른 특징을 갖고 있으므로 상황에 따라 적절히 선택하여 사용해야 한다.

  배열의 경우 탐색과 정렬은 용이하지만 데이터의 추가/삭제 측면에서 유연하지 못하며 크기가 고정되어있다. 따라서 배열은 고정된 양의 데이터를 저장하고 데이터에의 접근이 잦은 경우에 사용하는 것이 좋다. 또한 스택처럼 데이터의 추가/ 삭제가 일어나는 위치가 동일한 경우에 사용한다.

  연결리스트의 경우 데이터의 추가/삭제 측면에서 유연하므로 데이터의 추가/삭제가 자주 발생하거나 그래프 등의 복잡한 형태의 자료구조를 만들 때 사용한다.

 

3. JavaScript 구현

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);
    if (this.size() === 0) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this._size++;
  }

  remove(value) {
    let node = this.head;
    if (node !== null && node.value === value) {
      this.head = node.next;
      this._size--;
      return;
    }

    while (node !== null && node.next !== null) {
      let child = node.next;
      if (child.value == value) {
        node.next = child.next;
        if (this.tail === child) {
          this.tail = null;
        }
        this._size--;
        return;
      }
      node = child;
    }
  }

  getNodeAt(index) {
    let value = this.head;
    for (let i = 1; i <= index; i++) {
      value = value.next;
      if (value === null) {
        return undefined;
      }
    }
    return value;
  }

  contains(value) {
    let node = this.head;
    while (node !== null) {
      if (node.value === value) {
        return true;
      }
      node = node.next;
    }
    return false;
  }

  indexOf(value) {
    let node = this.head;
    let idx = 0;
    while (node !== null) {
      if (node.value === value) {
        return idx;
      }
      node = node.next;
      idx++;
    }
    return -1;
  }

  size() {
    return this._size;
  }
}

 

4. 종류

 1) Doubly Linked List

Double Linked List

   이중 연결 리스트는 각 노드가 자신의 이전 노드를 가리키는 링크, 다음 노드를 가리키는 링크 총 2개의 링크를 갖는다. 연결 스트에서 한 방향으로만 탐색을 할 수 있었던 단점을 개선한 것이다. 예를 들어 노드가 10개 존재하는 연결 리스트에서 9번째 노드에 접근해보자. 반드시 Head -> Tail 방향으로 탐색을 해야하므로 총 8번의 링크 추적이 필요하다. 그러나 이중 연결 리스트는 Tail -> Head 방향으로도 탐색이 가능하므로 1번의 링크 추적만으로 목표 노드에 접근 가능하다. 반면, 이중 연결 리스트는 링크를 2개 사용하므로 그만큼 많은 메모리를 차지한다. 양 방향에서 데이터의 입출력이 발생하는 Dequeue 구현 등에 사용한다.

 

 2) Circular Linked List

Circular Linked List

  환형 연결 리스트는 마지막 노드인 Tail의 링크가 Head를 가리키고 있어 링크가 순환하고 있는 형태를 갖는다. 따라서 한 노드에서 다른 모든 노드로 접근이 가능하다. 예를 들어 노드가 5개 존재하는 연결 리스트의 3번째 노드에서 1번째 노드에 접근해보자. 이는 불가능 하다. 항상 Head(1) -> Tail(3) 방향으로 탐색이 가능하며 Tail노드에서는 더 이상 탐색이 불가능 하기 때문이다. 그러나 환형 연결 리스트에서는 3 -> 4 -> 5 -> 1 로 1 번째 노드에 도달할 수 있다. 또한 환형 연결 리스트는 삽입/삭제 시 해당 노드가 연결 리스트의 끝 노드(Head/Tail)인지 확인할 필요가 없다.

 

---

참고 사이트:

[Algorithm] 배열과 연결리스트 (Array & Linked List)