다양한 자료 구조는 모두 노드라는 개념에 기반해 만들어졌다.
노드란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다.
14장에서는 가장 간단한 노드 기반 자료 구조이자 이후 배울 내용의 기반인 연결 리스트 살펴본다.
연결 리스트 (Linked List)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 배열과 연결 리스트는 외견상 상당히 비슷한 모습으로 동작하지만 내부적으로는 크게 다르다.
앞서 배웠듯이 코드에서 배열을 생성하면 메모리 내에 연속된 빈 셀 그룹을 찾아 사용자 애플리케이션이 데이터를 저장할 수 있도록 할당한다. 컴퓨터는 어떤 메모리 주소든 한 번에 접근할 수 있으므로 배열 내 어떤 인덱스든 바로 갈 수 있다. 즉, 프로그램은 배열이 어떤 메모리 주소부터 시작하는지를 알고 있다.
그에 비해 연결 리스트는 상당히 다르게 동작한다. 연결 리스트 내 데이터는 연속된 메모리 블록이 아니라 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다.
메모리에 곳곳에 흩어진 연결된 데이터를 노드라 부른다. 연결 리스트에서 각 노드는 리스트 내 한 항목을 나타낸다. 각 노드는 연결 리스트 내의 다음 노드의 메모리 주소도 포함한다. 연결 리스트의 첫 번째 노드를 헤드, 마지막 노드를 테일이라고도 부른다
데이터가 컴퓨터 메모리 전체에 흩어질 수 있다는 점에서 연결 리스트가 배열보다 유리할 수 있다.
배열은 데이터를 저장하기 위해 연속된 전체 셀 블록을 찾아야 하는데 배열이 커질수록 굉장히 어렵기 때문이다.
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)을 사용해 리스트를 참조 할 수 있다.
연결 리스트를 다룰 때는 첫 번째 노드에만 즉시 접근할 수 있다.
배열의 경우 읽기는 O(1)이다