[자료구조] Singly Linked List와 Doubly Linked List 성능 비교(삽입, 조회, 삭제)

Singly Linked List(단방향 연결 리스트)

개념

• 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지고 있다.

장점

• 메모리상 연속된 공간을 필요로 하지 않아, 동적 메모리 할당이 가능하다.
• 노드 삽입/삭제가 비교적 간단하다. 기존 노드의 포인터만 수정하면 되기 때문이다.

단점

• 특정 요소를 탐색하려면 헤드부터 순차적으로 탐색해야 하므로 접근 속도가 느리다(O(n)).
• 이전 노드에 대한 정보를 알 수 없으므로, 역방향 탐색이 불가능하다.

Linked List (양방향)

개념

• Doubly Linked List(양방향 연결 리스트)는 각 노드가 데이터와 함께 이전 노드(prev)와 다음 노드(next)에 대한 포인터를 가지는 자료 구조이다.

장점

• 양방향으로 탐색이 가능하므로 특정 작업(예: 중간 노드 삭제 등)이 더 효율적이다.
• 단방향 리스트에서 발생하는 역방향 탐색 문제를 해결할 수 있다.

단점

• 각 노드가 두 개의 포인터를 가지므로, 단방향 리스트에 비해 메모리 사용량이 많다.
  포인터 관리가 복잡하여 구현 난이도가 높다.

성능 비교

// PerformanceTest.test.ts
import { SinglyLinkedList } from "../data_structure/SinglyLinkedList";
import { DoublyLinkedList } from "../data_structure/DoublyLinkedList";

function measurePerformance(callback: () => void, iterations: number): number {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    callback();
  }
  const end = performance.now();
  return end - start;
}

describe("PerformanceTest", () => {
  const iterations = 1000;
  const testData = Array.from({ length: iterations }, (_, i) => i);

  test("Singly Linked List performance", () => {
    const singlyList = new SinglyLinkedList<number>();

    const singlyAddTime = measurePerformance(() => {
      singlyList.addLast(Math.random());
    }, iterations);

    const singlyFindTime = measurePerformance(() => {
      singlyList.find(testData[Math.floor(Math.random() * testData.length)]);
    }, iterations);

    const singlyRemoveTime = measurePerformance(() => {
      singlyList.removeLast();
    }, iterations);

    console.log("Singly Linked List:");
    console.log(`Add Time: ${singlyAddTime.toFixed(2)} ms`);
    console.log(`Find Time: ${singlyFindTime.toFixed(2)} ms`);
    console.log(`Remove Time: ${singlyRemoveTime.toFixed(2)} ms`);

    expect(singlyAddTime).toBeGreaterThanOrEqual(0);
    expect(singlyFindTime).toBeGreaterThanOrEqual(0);
    expect(singlyRemoveTime).toBeGreaterThanOrEqual(0);
  });

  test("Doubly Linked List performance", () => {
    const doublyList = new DoublyLinkedList<number>();

    const doublyAddTime = measurePerformance(() => {
      doublyList.addLast(Math.random());
    }, iterations);

    const doublyFindTime = measurePerformance(() => {
      doublyList.find(testData[Math.floor(Math.random() * testData.length)]);
    }, iterations);

    const doublyRemoveTime = measurePerformance(() => {
      doublyList.removeLast();
    }, iterations);

    console.log("\nDoubly Linked List:");
    console.log(`Add Time: ${doublyAddTime.toFixed(2)} ms`);
    console.log(`Find Time: ${doublyFindTime.toFixed(2)} ms`);
    console.log(`Remove Time: ${doublyRemoveTime.toFixed(2)} ms`);

    expect(doublyAddTime).toBeGreaterThanOrEqual(0);
    expect(doublyFindTime).toBeGreaterThanOrEqual(0);
    expect(doublyRemoveTime).toBeGreaterThanOrEqual(0);
  });
});

결과

• Singly Linked List

  • Add Time: 2.17 ms
  • Find Time: 3.16 ms
  • Remove Time: 2.14 ms

• Doubly Linked List

  • Add Time: 0.97 ms
  • Find Time: 3.26 ms
  • Remove Time: 0.11 ms

해석

1. 삽입(Add) 성능

• Doubly Linked List가 단방향 리스트에 비해 더 빠르다. 이유는 양방향 리스트에서 마지막 노드에 직접 접근할 수 있기 때문이다.
• 반면, 단방향 리스트는 마지막 노드에 접근하기 위해 전체를 순회해야 한다.

2. 탐색(Find) 성능

• 두 리스트의 탐색 성능 차이는 미미하다. 이유는 둘 다 헤드부터 시작해 순차적으로 탐색하기 때문이다.

3. 삭제(Remove) 성능

• Doubly Linked List의 삭제가 훨씬 빠르다. 이유는 양방향 리스트는 이전 노드(prev)를 바로 참조하여 포인터를 수정할 수 있지만, 단방향 리스트는 이전 노드를 찾기 위해 전체를 탐색해야 한다.

결론

• Doubly Linked List는 삽입과 삭제 작업에서 성능적 이점을 제공하며, 특히 노드 수가 많고 빈번한 수정 작업이 필요한 경우 적합하다.
• 반면, Singly Linked List는 메모리 사용량이 적고, 간단한 구조를 유지하므로 삽입/삭제가 빈번하지 않은 작업에 적합하다.