14장 노드 기반 자료 구조

다양한 자료 구조는 모두 노드라는 개념에 기반해 만들어졌다.

노드란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다.

14장에서는 가장 간단한 노드 기반 자료 구조이자 이후 배울 내용의 기반인 연결 리스트 살펴본다.

14.1 연결 리스트

연결 리스트 (Linked List)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 배열과 연결 리스트는 외견상 상당히 비슷한 모습으로 동작하지만 내부적으로는 크게 다르다.

앞서 배웠듯이 코드에서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 사용자 애플리케이션이 데이터를 저장할 수 있도록 할당한다. 컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 있으므로 배열 내 어떤 인덱스든 바로 갈 수 있다. 즉, 프로그램은 배열이 어떤 메모리 주소부터 시작하는지를 알고 있다.

그에 비해 연결 리스트는 상당히 다르게 동작한다. 연결 리스트 내 데이터는 연속된 메모리 블록이 아니라 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다.

메모리에 곳곳에 흩어진 연결된 데이터를 노드라 부른다. 연결 리스트에서 각 노드는 리스트 내 한 항목을 나타낸다. 각 노드는 연결 리스트 내의 다음 노드의 메모리 주소도 포함한다. 연결 리스트의 첫 번째 노드를 헤드, 마지막 노드를 테일이라고도 부른다

데이터가 컴퓨터 메모리 전체에 흩어질 수 있다는 점에서 연결 리스트가 배열보다 유리할 수 있다.

배열은 데이터를 저장하기 위해 연속된 전체 셀 블록을 찾아야 하는데 배열이 커질수록 굉장히 어렵기 때문이다.

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)dlek.

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)에 양 끝에 데이터를 삽입할 수 있을 뿐 아니라 O(1)에 양 끝에서 데이터를 삭제할 수 있다.

즉, 이중 연결 리스트는 O(1) 시간에 리스트 끝에 데이터를 삽입하고 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;
  }
}

이중 연결 리스트로 큐를 구현함으로써 삽입과 삭제 모두 O(1)만에 할 수 있게 됐다.

14.11 마무리

연결 리스트는 가장 단순한 노드 기반 자료 구조이지만 배열과 연결 리스트 간 미묘한 차이로 코드가 빨라진다.