ZeroCho Blog

안녕하세요. 이번 시간부터는 잠깐 화제를 돌려 자료구조에 대해 알아보고 가겠습니다.

자료구조는 데이터의 표현 및 저장 방법을 의미합니다. 알고리즘은 그 저장된 데이터를 처리하는 과정이고요. 즉, 자료구조를 알아야 알고리즘을 배울 수 있습니다. 하지만 지금까지 우리는 자료구조를 배우지 않았는데도 알고리즘을 배웠습니다. 제가 또 거짓말을 한 걸까요? 지난 시간에 우리는 계속 자료구조를 썼습니다. 다만 그게 자료구조였다는 것을 눈치채지 못했을 뿐이죠.

바로 배열이 자료구조 중 하나입니다. 그리고 자료구조의 대부분을 혼자서 다 해먹습니다. 자료구조에는 연결리스트, 스택, 큐 등이 있는데 자바스크립트의 배열은 훌륭하게도 이 모든 것을 표현할 수 있습니다. 그래서 문제가 되는 것이 자료구조를 배울 때 자바스크립트는 도움이 되지 않습니다. 이미 만능 배열이 있거든요. 굳이 연결리스트, 스택, 큐를 직접 구현할 필요가 적습니다.

하지만 그렇다고 해서 배울 필요가 아예 없다는 것은 아닙니다. 자료구조를 배우고, 직접 구현하다보면 생각하는 힘(프로그래밍 사고력)이 길러집니다. 그리고 어떤 때 어떤 자료구조를 쓰는 게 최선인지도 알게 됩니다. 같이 한 번 배워봅시다.

이번 시간에는 가장 기본인 연결 리스트에 대해 배워봅시다. 연결 리스트는 여러 개의 노드(Node.js 아님)로 이루어져 있습니다. 각각의 노드는 일종의 객체로 데이터와 다음 노드가 뭔지 알려주는 주소를 가지고 있습니다. 또한 연결 리스트에는 새로운 데이터를 추가(add)하거나, 데이터의 위치를 찾거나(search), 제거(remove)하는 기능이 있어야 합니다.

1->2->3->4->5 라는 연결 리스트가 있다면 1,2,3,4,5는 데이터고 ->는 주소입니다. 안타깝게도, 이미 자바스크립트에는 이것이 구현되어 있습니다. 바로 배열입니다. [1,2,3,4,5]가 있으면 1,2,3,4,5는 데이터이고, array[0], array[1] 등은 데이터가 담긴 위치를 말해주고 있죠. 또한, array.push();를 통해 데이터를 추가할 수 있고, array.splice();를 통해 데이터를 제거할 수 있습니다.

하지만 이렇게 바로 배열을 써버리면 공부가 안 되겠죠? 우리는 조금 고통을 받더라도 객체를 통해 직접 구현할 겁니다. 즉, 자바스크립트의 배열을 우리 손으로 직접 만드는 과정입니다.

일단 연결 리스트와 노드를 만들어봅시다.

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

class LinkedList {
  length = 0;
  head = null;    
}

LinkedList에는 length와 head가 있습니다. length는 노드의 개수를 표현하는 부분이고, head가 바로 첫 노드의 주소를 가리키는 부분입니다. 이제 데이터를 추가(add), 검색(search), 삭제(remove)하는 메소드를 구현해봅시다.

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

class LinkedList {
  length = 0;
  head = null;

  add(value) {
    if (this.head) {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = new Node(value);
    } else {
      this.head = new Node(value); 
    }
    this.length++;
    return this.length;
  }
  search(index) {
    return this.#search(index)[1]?.value;
  }
  #search(index) {
    let count = 0;
    let prev;
    let current = this.head;
    while (count < index) {
      prev = current;
      current = current?.next;
      count++;
    }
    return [prev, current];
  }
  remove(index) {
    const [prev, current] = this.#search(index);
    if (prev && current) {
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if (current) {
      // index가 0일 때
      this.head = current.next;
      this.length--;
      return this.length;
    }
    // 삭제하고자 하는 대상이 없을 때
    // 아무것도 안 함
  }
}

물론 추가할 때는 굳이 마지막에 추가하지 않아도 되고, 중간에 끼워넣는다든지, 맨 처음에 끼워넣어도 되겠죠? 직접 구현해보세요. 이제 테스트를 한 번 해볼까요?

const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.length; // 3
list.search(0); // 1
list.search(2); // 3
list.remove(1);
list.search(2); // undefined
list.length; // 2

배열과 비슷하게 동작하는 것을 확인할 수 있습니다. 시간 복잡도를 생각해봅시다. 맨 앞에 추가하는 것은 O(1)이고 뒤에 추가하는 것은 O(n)입니다. 반복문이 있나 세어보면 됩니다. 맨 뒤에 추가하는 것도 O(1)로 만들고 싶다면 head처럼 tail 속성을 추가하면 됩니다. 데이터를 찾는데는 O(n), 데이터를 제거하는 데는 O(n), 중간에 넣는 데는 O(n)이 소요됩니다. 공간 복잡도도 O(n)입니다.

특수한 연결 리스트도 있습니다. 현재 연결 리스트는 한 쪽 방향으로만 이동합니다. 그래서 다시 뒤로 가기는 불편하죠. 이걸 해결한 리스트가 이중 연결 리스트입니다. next외에 this.prev를 넣어 이전 노드를 가리키게 한 겁니다. 구현은 조금 더 복잡해지지만, 한 번 구현하면 그 뒤로는 편하게 앞과 뒤로 노드를 왔다갔다할 수 있습니다. 또 지금은 하나의 데이터씩만 연결되지만 한 노드에서 여러 노드를 연결하는 다중 연결 리스트도 있습니다. this.next를 노드들의 배열로 만들면 되겠죠? 필요에 따라 조금씩 변형해서 쓰시면 됩니다.

다음 시간에는 스택에 대해서 알아보겠습니다!