[Data Structure] 연결 리스트와 스킵 리스트

* 연결 리스트(Linked List)

 

연결 리스트는 일렬로 연결된 데이터를 저장할 때 사용하는 자료구조. 한 노드에는 다음 노드의 주소 정보가 담겨져 있다. 

배열과 연결 리스트는 흔히 비교되는 자료구조 형태다.

배열의 경우에는 배열 각 칸들이 물리적으로 한 곳에 모여 있으므로, 크기를 한 번 정하면 늘리거나 줄일 수 없다. 반면, 연결 리스트의 경우 데이터를 중간에 삽입을 하는 것이 용이하다. 가령, A노드와 C 노드 사이에 B 노드를 추가하려는 경우, B 노드의 다음 주소를 C노드로 연결하고, A노드의 다음 주소를 B노드로 연결하면 된다. (관련 알고리즘 문제풀이)

연결 리스트는 주소를 일일이 찾아다녀야 하기 때문에 배열보다 검색 속도가 느릴 수 있다. 반면 위에서 본 것 처럼 데이터를 중간에 추가하거나 삭제해야 할 경우 해당 위치의 주소값만 변경하면 되므로 배열보다 용이하다. 이처럼 연결 리스트는 길이가 정해지지 않은 데이터를 핸들링 할 때 용이하다. 

자료를 검색할 때, 노드의 다음 주소값들을 순차적으로 따라가야 하므로 시간복잡도는 O(N)이 된다. 

*연결 리스트 코드로 구현해보기

연결 리스트를 자바스크립트 코드로 아래와 같이 구현해볼 수 있다. 

const LinkedList = function() {
  const list = {};
  list.head = null;
  list.tail = null;

  list.addToTail = function(value) {
    let node = new Node(value);
    if (!this.head && !this.tail) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
  };

  list.removeHead = function() {
    let resultNode = this.head;
    if (!resultNode) {
      return undefined;
    } else {
      if (!resultNode.next) {
        this.head = null;
        this.tail = null;
        return resultNode.value;
      } else {
        this.head = this.head.next;
        return resultNode.value;
      }
    }
  };

  list.contains = function(target) {
    let current = this.head;
    let flag = true;
    while (flag) {
      if (current.value === target) {
        return true;
      }
      if(current.next === null){
        flag = false;
      }
      current = current.next;
    }
    return false;
  };
  return list;
};

const Node = function(value) {
  this.value = value;
  this.next = null;
};

 

*스킵 리스트(Skip List)

위에 언급했듯이 연결리스트에서 자료를 검색할 때의 시간복잡도는 O(N)이다. 조금 더 효율적인 방법은 없을까?

스킵 리스트(Skip List)는 연결리스트 노드의 검색, 삽입, 제거를 O(log n)의 시간복잡도로 할 수 있는 정렬된 자료구조를 이른다. 스킵리스트는 노드들이 오름차순 혹은 내림차순의 크기로 정렬되어 있는 경우 사용 가능하다. 

가령, 연결 리스트에서 빠른 검색을 위해 두 칸씩 건너뛰는 링크를 두 개 노드마다 하나씩 추가한다면 검색시간은 N/2로 줄어들게 된다(레벨 1). 더욱 빠른 검색을 원한다면, 네 칸씩 건너뛰는 링크를 네 개 노드마다 추가할 수 있다(레벨 2). 이 경우에는 검색시간이 약 N/4로 줄어들게 된다. 같은 원리로 링크를 계속 추가하며 검색 속도를 늘릴 수 있다. (물론, 추가한 링크만큼의 메모리가 추가되는 것을 염두해야 한다)

 

스킵리스트 예시. 출처: 널널한교수 유튜브 

 

예를 들어, 총 4레벨을 가진 위의 스킵리스트에서 20을 찾는다고 해보자.

- 헤드에서 레벨 4를 타고 88로 이동한다. 20은 88보다 작으므로, 다시 헤드로 가서 레벨 3을 통해 16으로 이동한다.

- 레벨 3을 타고 88로 이동한다. 20은 88보다 작으므로 다시 16으로 돌아가 레벨 2를 통해 72로 이동한다.

- 20은 72보다 작으므로 다시 16으로 돌아가 레벨 2를 통해 20으로 이동한다. 

스킵 리스트를 사용하면 모든 노드를 돌지 않고도 레벨을 이용해 노드들을 스킵하며 원하는 값을 찾을 수 있다. 스킵 리스트는 검색 시 시간복잡도가 O(log n)으로 효율적이나, 노드를 삽입, 혹은 삭제할 때에는 노드를 재구성해야 하므로 O(N)의 연산이 필요하다.

 

* Reference

- 엔지니어대한민국: https://www.youtube.com/watch?v=DzGnME1jIwY

- 널널한교수: https://www.youtube.com/watch?v=mh09uZDQw4A