JS로 불변성을 가지는 연결 리스트 만들어보기

목표

함수형 프로그래밍의 특징 중 하나인 불변성을 살려서 자료구조 중 하나인 연결 리스트를 Array 없이 JavaScript로 구현해보자

선수지식

• JavaScript 기초 문법, class 사용법
• 자료구조 - 연결 리스트
• 함수형 프로그래밍 (불변성) (블로그 글 보러가기)
• Jest (단위 테스트를 원할 경우)

전체 코드 Gist

바로가기

📚 분석 및 설계

핵심은 불변성이다.

예시로 만약 리스트 중간에 노드를 삽입 한다면 원본 리스트를 바꾸는 게 아니다. 대신, 이 방법을 따른다.

1. 삽입 지점까지의 노드들을 전부 새로 복사
2. 거기에 새 노드를 끼워 넣음
3. 나머지 노드들을 연결한 완전히 새로운 연결 리스트를 반환

또한 제약사항으로 Array 사용 금지를 걸겠다. 깡으로 모든 걸 구현해야한다.

연결 리스트 기초 구조 설계

1. 노드 (node)

• 역할: 리스트의 각 데이터를 담는 최소 단위
• 필수 속성
  • value: 실제 저장될 값
  • next: 다음 노드를 가리키는 포인터, 리스트의 끝이면 null
• 설계 아이디어: 간단한 객체 { value, next } 형태
  • 불변성을 강제하기 위해 Object.freeze()를 사용해 노드가 생성된 후에는 속성을 바꿀 수 없도록 함

const node = Object.freeze({
  value: 10,
  next: someOtherNode, // 다음 노드 혹은 null
});

2. 연결 리스트 컨테이너 (ImmutableLinkedList)

• 역할: 전체 연결 리스트를 대표, 관련 기능(append, remove 등)을 메소드로 제공하는 래퍼(wrapper)
• 필수 속성
  • head: 리스트의 첫 번째 노드를 가리키는 포인터
    • 리스트가 비어있으면 null
    • 이 속성이 리스트의 전체 상태를 나타냄
• 설계 아이디어: class를 사용해 구조를 명확하게 함
  • 생성자는 head 값을 받아 내부 속성으로 설정하는 역할을 한다

class ImmutableLinkedList {
  constructor(head = null) {
    this.head = head;
    // 클래스 자체도 freeze하여 head 속성이 외부에서 변경되는 것을 방지
    Object.freeze(this);
  }

  // 여기에 메소드들 추가
}

연결 리스트 필수 기능 설계

append(value)

• 리스트의 가장 마지막에 새로운 값을 추가
• 입력: 추가할 value
• 출력: value가 추가된 새로운 ImmutableLinkedList 인스턴스
• 핵심 동작: head부터 마지막 노드까지 모든 노드를 복사한 뒤, 마지막에 새 노드를 연결
• 엣지 케이스: 리스트가 비어있을 경우(this.head === null) - 새 노드가 유일한 노드이자 head

append(value) {
  // 재귀적으로 노드를 복사하며 끝에 새 노드를 추가하는 헬퍼 함수
  const appendRecursive = (node) => {
    // 1. Base Case: 리스트의 끝에 도달하면 새 노드를 만들어 반환
    if (node === null) {
      return createNode(value);
    }
    // 2. Recursive Step: 현재 노드를 복사하고, next는 재귀 호출 결과로 설정
    return createNode(node.value, appendRecursive(node.next));
  };

  const newHead = appendRecursive(this.head);
  return new ImmutableLinkedList(newHead);
}

1. 재귀 헬퍼 함수로 접근
   • 종료 조건: node === null - 즉, 리스트의 끝에 도달하면 새 노드를 생성해 반환
   • 재귀 단계: node !== null 이면 현재 노드를 복사하고 node.next로 재귀 호출
2. 재귀 함수를 호출해 새로운 head를 얻음
3. newHead를 사용해 새로운 연결 리스트를 생성하고 반환

insert(at, value)

• 리스트의 특정 위치(at)에 값을 삽입
• 입력: 삽입할 위치 인덱스 at, 삽입값 value
• 출력: 값이 삽입된 새로운 ImmutableLinkedList 인스턴스
• 핵심 동작
  • at 이전까지의 노드들은 모두 복사
  • at 위치에 새로운 노드를 삽입하고, 이 노드의 next는 원본 리스트의 at 위치에 있던 노드를 가리키게 함

remove(at)

• 리스트의 특정 위치(at)에 있는 노드를 제거
• 입력: 제거할 위치 인덱스 at
• 출력: 해당 노드가 제거된 새로운 ImmutableLinkedList 인스턴스
• 핵심 동작
  • 인덱스 at의 노드를 건너뛰도록 노드 체인을 재구성
  • at 이전까지의 노드는 복사하고, at - 1번째 복사본 노드의 next가 원본 at + 1 번째 노드를 가리키게 함

item(at)

• 리스트의 특정 위치(at)에 있는 값을 반환
• 입력: 조회할 위치 인덱스 at
• 출력: 해당 위치의 value
• 핵심 동작
  • 단순히 순회하며 값을 찾음

clear()

• 리스트의 모든 요소를 제거하여 비움
• 입력: 없음
• 출력: 비어있는 새로운 ImmutableLinkedList 인스턴스
• 핵심 동작: head가 null인 새로운 리스트를 반환

☠️ 구현

노드 구조 구현

일단 간단하게 노드를 만들어주는 함수부터 구현한다.

const createNode = (value, next = null) => {
  return Object.freeze({
    value,
    next,
  });
};

연결 리스트 컨테이너 구조 구현

class ImmutableLinkedList {
  constructor(head = null) {
    this.head = head;
    Object.freeze(this);
  }

  // 메소드 추가
}

위에서 설계한 바와 같다.

연결 리스트 필수 기능 구현

append(value)

append(value) {
    const appendRecursive = (currentNode) => {
      // 1. 종료 조건: 리스트의 끝에 도달
      if (currentNode === null) {
        return createNode(value);
      }

      // 2. 재귀 단계: 현재 노드가 존재할 때
      // 현재 노드를 '복사'하고, 'next' 포인터는 재귀 호출의 결과로 연결
      return createNode(currentNode.value, appendRecursive(currentNode.next));
    };

    // head부터 시작해서 재귀로 리스트 만들기
    const newHead = appendRecursive(this.head);

    // 반환된 새로운 head로 새로운 ImmutableLinkedList 인스턴스 생성
    return new ImmutableLinkedList(newHead);
}

사용 예시

// 초기 리스트 생성: (10) -> (20) -> null
const node2 = createNode(20);
const node1 = createNode(10, node2);
const list1 = new ImmutableLinkedList(node1);

// append(30) 호출
const list2 = list1.append(30);

// append(40) 호출
const list3 = list2.append(40);

// 결과 확인
console.log(list1.head.next.next); // null (list1은 변경되지 않음)
console.log(list2.head.next.next.value); // 30
console.log(list3.head.next.next.next.value); // 40

// 각 리스트는 서로 다른 인스턴스입니다.
console.log(list1 === list2); // false (불변성이 지켜짐)

insert(at, value)

insert(at, value) {
    const insertRecursive = (currentNode, currentIndex) => {
      // 1. 종료 조건: 삽입 위치에 도달
      // 새 노드를 생성하고, 이 노드의 next가 원본의 현재 노드를 가리키게 함
      if (currentIndex === at) {
        return createNode(value, currentNode);
      }

      // 2. 종료 조건: 리스트의 끝에 도달했는데 삽입 위치를 찾지 못함
      if (currentNode === null) {
        throw new Error("Index out of bounds");
      }

      // 3. 재귀 단계: 삽입 위치까지 이동
      // 현재 노드를 복사하고, next는 다음 노드에 대한 재귀 호출 결과로 설정
      // 현재 인덱스를 증가시켜 다음 노드로 이동
      return createNode(currentNode.value, insertRecursive(currentNode.next, currentIndex + 1));
    };

    const newHead = insertRecursive(this.head, 0);

    return new ImmutableLinkedList(newHead);
}

append와 유사하지만 현재 인덱스를 추적한다는 점이 다르다. 그 외에는 유사한 재귀 방식을 따라간다.

item(at)

item(at) {
    let currentNode = this.head;
    let currentIndex = 0;

    // 끝까지 순회
    while (currentNode !== null) {
      // 현재 인덱스가 찾으려는 위치와 같으면 현재 노드 값을 반환
      if (currentIndex === at) {
        return currentNode.value;
      }

      // 찾는 위치가 아니면 다음 노드로 이동, 인덱스 1 증가
      currentNode = currentNode.next;
      currentIndex++;
    }

    // 루프가 끝날 때까지 값을 반환하지 못할 때
    throw new Error("Index out of bounds");
}

별 거 없이 쭉 순회하면서 인덱스를 비교하는 방식이다.

clear()

clear() {
    // 생성자의 인자를 비워두면 head가 기본값인 null로 설정
    // 이를 이용해 비어있는 새 리스트를 생성하여 반환
    return new ImmutableLinkedList();
}

원본 리스트는 전혀 건드리지 않고 완전히 독립적인 빈 리스트를 새로 만들어 반환한다.

🧪 테스트

테스트 설계

ImmutableLinkedList는 모든 연산 후 새로운 리스트를 반환하며 원본은 변경되지 않아야 한다.

테스트 대상	테스트 시나리오	입력값	기대 결과	핵심 검증 코드 (Jest)
constructor	빈 리스트 생성	new ImmutableLinkedList()	head가 null인 인스턴스 생성	expect(list.head).toBeNull();
	초기 노드를 가진 리스트 생성	const node = createNode(1); new ImmutableLinkedList(node)	head가 node인 인스턴스 생성	expect(list.head.value).toBe(1);
append	빈 리스트에 값 추가	const list = new ImmutableLinkedList(); list.append(10);	head의 값이 10인 새로운 리스트 반환	const newList = list.append(10); expect(newList.head.value).toBe(10); expect(list.head).toBeNull();
	기존 리스트에 값 추가	// list: 1 -> 2 list.append(3);	1 -> 2 -> 3 구조의 새로운 리스트 반환, 원본은 불변	const newList = list.append(3); expect(newList.item(2)).toBe(3); expect(() => list.item(2)).toThrow();
insert	리스트 맨 앞에 값 삽입	// list: 10 -> 20 list.insert(0, 5);	5 -> 10 -> 20 구조의 새로운 리스트 반환	const newList = list.insert(0, 5); expect(newList.item(0)).toBe(5); expect(newList.item(1)).toBe(10);
	리스트 중간에 값 삽입	// list: 10 -> 30 list.insert(1, 20);	10 -> 20 -> 30 구조의 새로운 리스트 반환	const newList = list.insert(1, 20); expect(newList.item(1)).toBe(20);
	범위를 벗어난 인덱스에 삽입	// list: 10 list.insert(5, 1);	Index out of bounds 에러 발생	expect(() => list.insert(5, 1)).toThrow("Index out of bounds");
remove	리스트 맨 앞의 값 제거	// list: 10 -> 20 list.remove(0);	head가 20을 가리키는 새로운 리스트 반환	const newList = list.remove(0); expect(newList.item(0)).toBe(20);
	리스트 중간 값 제거	// list: 10 -> 20 -> 30 list.remove(1);	10 -> 30 구조의 새로운 리스트 반환	const newList = list.remove(1); expect(newList.item(1)).toBe(30);
	범위를 벗어난 인덱스 제거	// list: 10 list.remove(5);	Index out of bounds 에러 발생	expect(() => list.remove(5)).toThrow("Index out of bounds");
item	특정 위치의 값 조회	// list: 10 -> 20 -> 30 list.item(2);	값 30 반환	expect(list.item(2)).toBe(30);
	범위를 벗어난 인덱스 조회	// list: 10 list.item(3);	Index out of bounds 에러 발생	expect(() => list.item(3)).toThrow("Index out of bounds");
clear	리스트 비우기	// list: 10 -> 20 list.clear();	head가 null인 새로운 빈 리스트 반환, 원본은 불변	const newList = list.clear(); expect(newList.head).toBeNull(); expect(list.item(0)).toBe(10);