14장 노드 기반 자료 구조

앞으로 다룰 다양한 자료구조는 모드 노드라는 개념에 기반해 만들어졌다. 노드는 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다.

14장에선 연결 리스트를 살펴본다.

14.1 연결 리스트

연결 리스트(Linked List)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조이지만, 내부적으로는 크게 다르다.

연결 리스트 내 데이터는 연속된 메모리 블록이 아니라 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 메모리에 곳곳에 흩어진 연결된 데이터를 노드라 부른다. 각 노드는 연결 리스트 내의 다음 노드의 메모리 주소도 포함한다. 연결 리스트의 첫 번째 노드를 헤드head, 마지막 노드를 테일tail이라고도 부른다.

14.2 연결 리스트 구현

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

const node1 = new Node("once");
const node2 = new Node("upon");
const node3 = new Node("a");
const node4 = new Node("time");

node1.nextNode = node2;
node2.nextNode = node3;
node3.nextNode = node4;

이 구현에선 nextNode가 메모리 주소 대신 또 다른 Node 인스턴스를 참조한다. 노드가 메모리 곳곳에 흩어져 있어도 노드의 링크를 사용해 전체 리스트를 연결할 수 있으므로 결과는 같다.

class LinkedList {
  constructor(firstNode) {
    this.firstNode = firstNode;
  }
}

LinkedList 인스턴스의 역할은 리스트의 첫 노드를 추적하는 것 뿐이다. 앞서 node1, node2, node3, node4를 포함하는 노드 사슬을 생성했으므로, const list = new LinkedList(node1)을 사용해 리스트를 참조 할 수 있다.

연결 리스트를 다룰 때는 첫 번째 노드에만 즉시 접근할 수 있다.

14.3 읽기

배열의 경우 읽기는 O(1)이다.

하지만 연결 리스트의 경우 첫 번째 노드에만 접근할 수 있으므로, 어떤 노드를 가든 항상 첫 번째 노드로부터 노드 사슬을 따라가야 한다. 리스트의 마지막 노드를 읽는 최악의 시나리오에서 O(N)이다.

14.3.1 코드 구현: 연결 리스트 읽기

class LinkedList {
  constructor(firstNode) {
    this.firstNode = firstNode;
  }

  read(index) {
    let currentNode = this.firstNode;
    let currentIndex = 0;

    while (currentIndex < index) {
      currentNode = currentNode.nextNode;
      currentIndex += 1;

      if (!currentNode) return null;
    }

    return currentNode.data;
  }
}

const list = new LinkedList(node1);
list.read(3);		// time

현재 접근하는 노드를 참조하는 currentNode 변수를 생성하고, 첫 번째 노드부터 접근하므로 첫 번째 노드로 초기화한다.
currentNode의 인덱스를 기록할 currentIndex 변수를 생성해 첫 번째 노드의 인덱스인 0으로 초기화한다.

currentIndex가 읽으려는 인덱스보다 작을 때까지 반복문을 실행한다.
반복문의 각 패스스루에서는 리스트의 다음 노드에 접근해 그 노드를 새 currentNode로 만들고, 인덱스를 1씩 증가 시킨다.
패스스루마다 리스트의 끝에 도달했는지 확인하고 읽으려는 인덱스가 연결 리스트에 없으면 null을 반환한다.
반복문이 종료되면 찾은 인덱스에 해당하는 노드의 데이터를 반환한다.

14.4 검색

배열을 선형 검사하면 O(N)이다.

연결 리스트의 검색 속도 역시 O(N)이다. 첫 노드에서 시작해 각 노드의 링크를 따라 다음 노드로 가며 찾는 값이 나올 때까지 매번 검사한다.

14.4.1 코드 구현: 연결 리스트 검색

indexOf(value) {
  let currentNode = this.firstNode;
  let currentIndex = 0;

  while (currentNode) {
    if (currentNode.data === value) {
      return currentIndex;
    }
    currentNode = currentNode.nextNode;
    currentIndex += 1;
  }

  return null;
}

indexOf(value) 함수를 LinkedList 클래스의 메서드로 추가한다. list.indexOf("time") 등을 통해 찾으려는 값의 인덱스를 구할 수 있다.

검색 기법은 읽기와 비슷하나, 반복문이 특정 인덱스에서 중지되지 않고 찾으려는 값(value)을 찾거나 리스트 끝에 도달할 때까지 실행된다는 점이 다르다.

14.5 삽입

연결 리스트가 배열에 비해 어떤 상황에서 뚜렷한 장점을 보이는 연산이 삽입이다.

배열 삽입에서 인덱스 0에 데이터를 삽입할 경우 O(N)이었다.

하지만 연결 리스트는 리스트 앞에 데이터를 삽입해도 O(1)이다. 새 노드를 생성하고 노드가 원래 첫 노드를 가리키게끔 하면 된다. 즉, 데이터를 하나도 옮기지 않고 리스트 앞에 데이터를 삽입할 수 있다.

리스트 중간에 삽입하는 것에는 알아둬야 할 점이 있다. 새 노드를 리스트 중간에 추가하려면 추가하려는 인덱스에 가야 하는데, 연결 리스트는 인덱스 0에만 즉시 접근할 수 있다. 즉, 리스트의 마지막에 추가하는 최악의 경우 추가하려는 인덱스에 가는 것이 N단계이고 추가하는데 1단계가 걸리니 N+1단계로 O(N)이다.

따라서, 연결 리스트 삽입은 사실상 O(N)이지만, 맨 앞에 삽입하는 최선의 경우 O(1)이다. 배열의 시나리오와 정반대다. 배열은 데이터를 뒤에 삽입할 때 유리하고, 연결 리스트는 데이터를 앞에 삽입할 때 유리하다.

14.5.1 코드 구현: 연결 리스트 삽입

insertAtIndex(index, value) {
  const newNode = new Node(value);
  if(index === 0) {
    newNode.nextNode = this.firstNode;
    this.firstNode = newNode;
    return;
  }

  let currentNode = this.firstNode;
  let currentIndex = 0;

  while(currentIndex < (index - 1)) {
    currentNode = currentNode.nextNode;
    currentIndex += 1;
  }

  newNode.nextNode = currentNode.nextNode;
  currentNode.nextNode = newNode;
}

insertAtIndex(index, value) 함수를 LinkedList 클래스의 메서드로 추가한다. list.insertAtIndex(3, "purple") 등을 통해 원하는 인덱스에 데이터를 추가할 수 있다.

메서드의 제공된 값으로 새 노드 newNode를 생성한다.

리스트의 맨 앞에 삽입하는 경우, newNode를 리스트의 기존 첫 번째 노드와 연결한 뒤 리스트의 첫 번째 노드를 newNode로 선언한다.

리스트의 중간에 삽입하는 경우, currentNode와 currentIndex를 이용한 while 반복문으로 인덱스 0부터 삽입하려는 인덱스의 바로 앞 노드에 접근한다.

이 때 currentNode가 newNode의 바로 앞 노드이므로, newNode의 링크에 currnetNode의 다음 노드를 할당하고, currentNode의 링크가 newNode를 가리키도록 바꾼다.

14.6 삭제

연결 리스트는 삭제도 매우 빠르다. 특히 리스트 앞에서 삭제할 때 그렇다.

연결 리스트 앞에서 노드를 삭제하려면 한 단계면 된다. 리스트의 firstNode가 두 번째 노드를 가리키게 하면 된다.
list.firstNode = node2를 통해 할 수 있다. 배열의 경우 맨 앞의 요소를 삭제하고 다른 요소들을 한 셀씩 왼쪽으로 시프트해야 하므로 O(N)이다.

연결 리스트의 끝에서 노드를 삭제하려면 끝에서 두 번째 노드를 가져와 링크를 null로 만들면 된다. 하지만 끝에서 두 번째 노드까지 가야 하므로 이미 N단계가 걸리므로 O(N)이다. 배열의 경우는 한 단계면 된다. 즉, 삽입과 마찬가지로 최선과 최악의 시나리오가 정 반대이다.

리스트 중간에서의 삭제는 조금 더 복잡하다. 삭제하려는 노드의 바로 앞 노드에 접근한다. 그 노드의 링크를 삭제하려는 노드의 뒤 노드를 가리키도록 바꾼다.

연결 리스트에서 노드를 삭제해도 메모리 내 어딘가에는 남는다. 연결 리스트에서만 제거할 뿐이다. 이 삭제된 노드를 처리하는 방법은 프로그래밍 언어마다 다르다.

14.6.1 코드 구현: 연결 리스트 삭제

deleteAtIndex(index) {
  if (index === 0) {
    this.firstNode = this.firstNode.nextNode;
    return;
  }

  let currentNode = this.firstNode;
  let currentIndex = 0;

  while (currentIndex < index - 1) {
    currentNode = currentNode.nextNode;
    currentIndex += 1;
  }

  const nodeAfterDeletedNode = currentNode.nextNode.nextNode;
  currentNode.nextNode = nodeAfterDeletedNode;
}

삽입 때와 코드가 유사하다. 중간에서 삭제할 때 nodeAfterDeletedNode 변수를 추가해 삭제하려는 노드 뒤의 노드를 가져와 currentNode의 링크에 연결시켰다.

14.7 연결 리스트 연산의 효율성

연결 리스트가 효과적으로 쓰이려면 실제 삽입과 삭제 단계가 O(1)이라는 점을 활용해야 한다.
하지만 삽입과 삭제 모두 맨 앞에 연산할 경우만 그렇다. 중간 혹은 맨 뒤라면 그 인덱스까지 찾아가야하기 때문이다.

14.8 연결 리스트 다루기

연결 리스트가 빛을 발하는 경우는 한 리스트를 검사해 많은 원소를 삭제할 때다. 이메일 주소 리스트에서 유효하지 않은 형식의 이메일을 삭제하는 경우가 해당한다.

연결 리스트든 배열이든 전체 리스트를 순회하며 각 값을 검사하는 것은 N단계가 걸린다. 하지만 삭제할 때 배열은 나머지 원소를 왼쪽으로 시프트해야 하므로 O(N)단계가 추가로 들지만, 연결 리스트는 삭제할 때 한 단계면 된다.

1000개의 이메일 중 100개가 유효하지 않다고 쳤을 때, 배열과 연결 리스트 모두 1000개의 읽기 단계가 걸린다. 하지만 배열은 삭제에 약 100,000단계가 추가로 걸리는 반면 연결 리스트는 삭제에 100단계만 추가로 걸린다.

연결 리스트는 삽입이나 삭제 시 다른 데이터를 시프트하지 않아도 되므로 전체 리스트를 훑으며 삽입이나 삭제를 수행하기에 매우 알맞은 자료 구조다.

14.9 이중 연결 리스트

연결 리스트의 일부를 조금 수정해 연결 리스트를 엄청나게 향상시킬 수 있다.
연결 리스트 변형 중 하나가 이중 연결 리스트다.

이중 연결 리스트는 각 노드에 2개의 링크가 있다는 점을 제외하면 연결 리스트와 비슷하다. 한 링크는 앞 노드, 다른 한 링크는 다음 노드를 가리킨다. 이중 연결 리스트는 첫 번째 노드 외에 마지막 노드도 항상 기록한다.

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

class DoublyLinkedList {
  constructor(firstNode=null, lastNode=null) {
    this.firstNode = firstNode;
    this.lastNode = lastNode;
  }
}

이중 연결 리스트는 첫 노드와 마지막 노드를 O(1)에 접근할 수 있고, 리스트 끝에서의 읽기, 삽입, 삭제도 O(1)에 할 수 있다.

14.9.1 코드 구현: 이중 연결 리스트 삽입

만일 이중 연결 리스트의 끝에 데이터를 삽입한다면, 새 노드를 생성해서 그 노드의 previousNode가 기존 lastNode를 가리키도록한다. 그리고 기존 lastNode의 nextNode가 새 노드를 가리키도록 한다. 그리고 새 노드를 리스트의 lastNode로 선언한다.

insertAtEnd(value) {
  const newNode = new Node(value);

  if (!this.firstNode) {
    this.firstNode = newNode;
    this.lastNode = newNode;
  } else {
    newNode.previousNode = this.lastNode;
    this.lastNode.nextNode = newNode;
    this.lastNode = newNode;
  }
}

14.9.2 앞과 뒤로 이동

전혁적인 연결 리스트는 리스트 앞으로만 이동할 수 있다. 즉 첫 번째 노드에 접근해 링크를 따라 리스트의 나머지 노드를 찾아야 한다. 이전 노드는 기록되어 있지 않기 때문에 뒤로 이동할 수 없다.

이중 연결리스트는 리스트 앞과 뒤로 모두 이동할 수 있다. 마지막 노드에서 시작해 첫 번째 노드로 거슬러 올라갈 수 있다.

14.10 이중 연결 리스트 기반 큐

이중 연결 리스트는 O(1)에 리스트 끝에 데이터를 삽입하고 리스트 앞에서 데이터를 삭제하므로, 큐를 위한 완벽한 내부 자료 구조다.

큐는 데이터를 끝에만 삽입할 수 있고 앞에서만 삭제할 수 있는 항목들의 리스트이다. 9장에서는 배열을 이용해 내부적으로 구현했었다. 배열을 이용해 끝에 삽입할 땐 O(1)이지만 앞에서 삭제할 땐 O(N)이다. 이중 연결 리스트는 둘 다 O(1)이므로 큐의 내부 자료 구조로서 완벽하다.

14.10.1 코드 구현: 이중 연결 리스트 기반 큐

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

class DoublyLinkedList {
  constructor(firstNode = null, lastNode = null) {
    this.firstNode = firstNode;
    this.lastNode = lastNode;
  }

  insertAtEnd(value) {
    const newNode = new Node(value);

    if (!this.firstNode) {
      this.firstNode = newNode;
      this.lastNode = newNode;
    } else {
      newNode.previousNode = this.lastNode;
      this.lastNode.nextNode = newNode;
      this.lastNode = newNode;
    }
  }

  removeFromFront() {
    const removedNode = this.firstNode;
    this.firstNode = this.firstNode.nextNode;
    return removedNode;
  }
}

class Queue {
  constructor() {
    this.data = new DoublyLinkedList();
  }

  enque(element) {
    this.data.insertAtEnd(element);
  }

  deque() {
    const removedNode = this.data.removeFromFront();
    return removedNode.data;
  }

  read() {
    if (!this.data.firstNode) return null;
    return this.data.firstNode.data;
  }
}

14.11 마무리

배열과 연결 리스트 간 미묘한 차이로 코드가 빨라진다.