연결 리스트(Linked List) 완전 정복: 메모리 효율적인 동적 자료구조의 모든 것

자료구조를 공부하다 보면 배열 다음으로 만나게 되는 것이 바로 연결 리스트(Linked List)입니다. 배열의 한계를 보완하면서도 동적으로 크기를 조절할 수 있는 연결 리스트는 많은 프로그래밍 상황에서 핵심적인 역할을 합니다. 오늘은 연결 리스트의 개념부터 실제 구현, 그리고 실무 활용까지 체계적으로 알아보겠습니다.

---

연결 리스트란 무엇인가?

연결 리스트는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조입니다. 마치 기차처럼 각 칸(노드)이 다음 칸을 가리키는 연결고리로 이어져 있다고 생각하면 됩니다.

연결 리스트의 핵심 구성 요소

• 노드(Node): 데이터와 다음 요소에 대한 포인터를 가진 기본 단위
• HEAD: 첫 번째 노드를 가리키는 포인터
• TAIL: 마지막 노드를 가리키는 포인터

// 노드의 기본 구조
class Node {
  constructor(data) {
    this.data = data;      // 실제 저장할 데이터
    this.next = null;      // 다음 노드를 가리키는 포인터
  }
}

연결 리스트의 주요 특징

특징	설명
동적 크기	메모리가 허용하는 한 요소를 계속 삽입 가능
메모리 효율성	필요한 만큼만 메모리 할당
비연속적 저장	메모리 공간에 흩어져서 존재
포인터 기반	다음 요소에 대한 참조로 연결

---

배열 vs 연결 리스트: 언제 무엇을 선택할까?

연결 리스트를 이해하기 위해서는 배열과의 차이점을 명확히 아는 것이 중요합니다.

메모리 사용 방식의 차이

배열 (Array):
┌─────┬─────┬─────┬─────┬─────┐
│  1  │  2  │  3  │  4  │  5  │  ← 연속적인 메모리 공간
└─────┴─────┴─────┴─────┴─────┘
 주소: 100  104  108  112  116

연결 리스트 (Linked List):
┌─────┐    ┌─────┐    ┌─────┐    ┌─────┐
│  1  │───▶│  2  │───▶│  3  │───▶│  4  │───▶ NULL
└─────┘    └─────┘    └─────┘    └─────┘
주소: 100     256     180     312      ← 메모리에 흩어져 있음

성능 비교표

연산	배열	연결 리스트	언제 사용?
접근(인덱스)	O(1)	O(n)	빈번한 랜덤 접근 → 배열
탐색	O(n)	O(n)	동일하므로 다른 요소 고려
삽입(맨 앞)	O(n)	O(1)	앞쪽 삽입 빈번 → 연결 리스트
삭제(맨 앞)	O(n)	O(1)	앞쪽 삭제 빈번 → 연결 리스트
메모리 사용	연속적	비연속적	메모리 절약 → 연결 리스트

---

연결 리스트의 종류

1. 단일 연결 리스트 (Singly Linked List)

가장 기본적인 형태로, 각 노드가 다음 노드만을 가리킵니다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

2. 이중 연결 리스트 (Doubly Linked List)

각 노드가 이전 노드와 다음 노드를 모두 가리킵니다.

class DoublyNode {
  constructor(data) {
    this.data = data;
    this.prev = null;  // 이전 노드
    this.next = null;  // 다음 노드
  }
}

3. 원형 연결 리스트 (Circular Linked List)

마지막 노드가 첫 번째 노드를 가리켜 원형을 이룹니다.

---

단일 연결 리스트 완전 구현

기본 클래스 구조

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 리스트가 비어있는지 확인
  isEmpty() {
    return this.size === 0;
  }

  // 리스트 크기 반환
  getSize() {
    return this.size;
  }
}

1. 삽입(Insert) 연산

// 맨 뒤에 요소 추가 - O(1)
insert(data) {
  const newNode = new Node(data);

  if (this.head === null) {
    // 첫 번째 노드인 경우
    this.head = newNode;
    this.tail = newNode;
  } else {
    // 기존 노드가 있는 경우
    this.tail.next = newNode;
    this.tail = newNode;
  }

  this.size++;
  return newNode;
}

// 특정 위치에 요소 추가 - O(n)
insertAt(index, data) {
  if (index < 0 || index > this.size) {
    throw new Error('Index out of bounds');
  }

  if (index === 0) {
    return this.prepend(data);
  }

  if (index === this.size) {
    return this.insert(data);
  }

  const newNode = new Node(data);
  let current = this.head;

  // index-1 위치까지 이동
  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }

  newNode.next = current.next;
  current.next = newNode;
  this.size++;

  return newNode;
}

// 맨 앞에 요소 추가 - O(1)
prepend(data) {
  const newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.next = this.head;
    this.head = newNode;
  }

  this.size++;
  return newNode;
}

2. 탐색(Search) 연산

// 값으로 노드 찾기 - O(n)
find(value) {
  let current = this.head;
  let index = 0;

  while (current !== null) {
    if (current.data === value) {
      return { node: current, index: index };
    }
    current = current.next;
    index++;
  }

  return null; // 찾지 못한 경우
}

// 인덱스로 노드 가져오기 - O(n)
get(index) {
  if (index < 0 || index >= this.size) {
    throw new Error('Index out of bounds');
  }

  let current = this.head;
  for (let i = 0; i < index; i++) {
    current = current.next;
  }

  return current;
}

// 값이 존재하는지 확인 - O(n)
contains(value) {
  return this.find(value) !== null;
}

3. 삭제(Delete) 연산

// 특정 값을 가진 노드 삭제 - O(n)
remove(value) {
  if (this.head === null) {
    return false;
  }

  // 첫 번째 노드를 삭제하는 경우
  if (this.head.data === value) {
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return true;
  }

  let current = this.head;
  while (current.next !== null) {
    if (current.next.data === value) {
      // 삭제할 노드가 마지막 노드인 경우
      if (current.next === this.tail) {
        this.tail = current;
      }
      current.next = current.next.next;
      this.size--;
      return true;
    }
    current = current.next;
  }

  return false; // 찾지 못한 경우
}

// 특정 인덱스의 노드 삭제 - O(n)
removeAt(index) {
  if (index < 0 || index >= this.size) {
    throw new Error('Index out of bounds');
  }

  if (index === 0) {
    const removedData = this.head.data;
    this.head = this.head.next;
    if (this.head === null) {
      this.tail = null;
    }
    this.size--;
    return removedData;
  }

  let current = this.head;
  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }

  const removedData = current.next.data;
  if (current.next === this.tail) {
    this.tail = current;
  }
  current.next = current.next.next;
  this.size--;

  return removedData;
}

4. 유틸리티 메서드

// 리스트를 배열로 변환 - O(n)
toArray() {
  const result = [];
  let current = this.head;

  while (current !== null) {
    result.push(current.data);
    current = current.next;
  }

  return result;
}

// 리스트 출력 - O(n)
display() {
  if (this.head === null) {
    console.log('List is empty');
    return;
  }

  const values = this.toArray();
  console.log(values.join(' -> ') + ' -> null');
}

// 리스트 초기화 - O(1)
clear() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}

---

실무에서의 연결 리스트 활용 사례

1. 웹 브라우저의 히스토리 관리

class BrowserHistory {
  constructor() {
    this.history = new SinglyLinkedList();
    this.current = null;
  }

  visit(url) {
    this.history.insert(url);
    this.current = this.history.tail;
    console.log(`Visiting: ${url}`);
  }

  back() {
    if (this.current && this.current.prev) {
      this.current = this.current.prev;
      console.log(`Back to: ${this.current.data}`);
      return this.current.data;
    }
    console.log('No previous page');
    return null;
  }
}

2. 음악 플레이어의 재생 목록

class Playlist {
  constructor() {
    this.songs = new SinglyLinkedList();
    this.currentSong = null;
  }

  addSong(title, artist) {
    const song = { title, artist, id: Date.now() };
    this.songs.insert(song);

    if (!this.currentSong) {
      this.currentSong = this.songs.head;
    }
  }

  nextSong() {
    if (this.currentSong && this.currentSong.next) {
      this.currentSong = this.currentSong.next;
      return this.currentSong.data;
    }
    return null;
  }

  removeSong(songId) {
    // 현재 재생 중인 곡을 삭제하는 경우 처리
    if (this.currentSong && this.currentSong.data.id === songId) {
      this.currentSong = this.currentSong.next;
    }

    // 연결 리스트에서 해당 곡 제거
    let current = this.songs.head;
    while (current) {
      if (current.data.id === songId) {
        this.songs.remove(current.data);
        break;
      }
      current = current.next;
    }
  }
}

3. 실시간 채팅 메시지 관리

class ChatMessageList {
  constructor(maxMessages = 100) {
    this.messages = new SinglyLinkedList();
    this.maxMessages = maxMessages;
  }

  addMessage(user, content) {
    const message = {
      id: Date.now(),
      user,
      content,
      timestamp: new Date().toISOString()
    };

    this.messages.insert(message);

    // 최대 메시지 수 초과 시 오래된 메시지 삭제
    if (this.messages.getSize() > this.maxMessages) {
      this.messages.removeAt(0); // 가장 오래된 메시지 제거
    }

    return message;
  }

  getRecentMessages(count = 10) {
    const allMessages = this.messages.toArray();
    return allMessages.slice(-count); // 최근 메시지만 반환
  }
}

---

연결 리스트 최적화 팁

1. 메모리 풀링 기법

class NodePool {
  constructor() {
    this.pool = [];
  }

  getNode(data) {
    if (this.pool.length > 0) {
      const node = this.pool.pop();
      node.data = data;
      node.next = null;
      return node;
    }
    return new Node(data);
  }

  releaseNode(node) {
    node.data = null;
    node.next = null;
    this.pool.push(node);
  }
}

2. 더미 헤드 노드 활용

class OptimizedLinkedList {
  constructor() {
    this.dummy = new Node(null); // 더미 헤드 노드
    this.tail = this.dummy;
    this.size = 0;
  }

  // 더미 노드 덕분에 삽입/삭제 로직이 단순해짐
  insert(data) {
    const newNode = new Node(data);
    this.tail.next = newNode;
    this.tail = newNode;
    this.size++;
  }
}

---

성능 분석 및 주의사항

시간 복잡도 정리

연산	단일 연결 리스트	이중 연결 리스트	배열
삽입 (맨 앞)	O(1)	O(1)	O(n)
삽입 (맨 뒤)	O(1)	O(1)	O(1) 또는 O(n)
삽입 (중간)	O(n)	O(n)	O(n)
삭제 (맨 앞)	O(1)	O(1)	O(n)
삭제 (맨 뒤)	O(n)	O(1)	O(1)
탐색	O(n)	O(n)	O(1)

주의사항

1. 메모리 오버헤드: 각 노드마다 포인터를 위한 추가 메모리 필요
2. 캐시 지역성: 비연속적 메모리 때문에 캐시 미스 발생 가능
3. 순환 참조: 잘못된 구현으로 무한 루프 발생 위험

---

결론

연결 리스트는 동적 메모리 관리가 필요한 상황에서 매우 유용한 자료구조입니다. 특히 다음과 같은 경우에 활용하면 효과적입니다:

핵심 정리

• 동적 크기 조절: 런타임에 크기를 자유롭게 변경해야 하는 경우
• 효율적인 삽입/삭제: 리스트의 앞부분에서 빈번한 삽입/삭제가 발생하는 경우
• 메모리 효율성: 사용하는 만큼만 메모리를 할당하고 싶은 경우
• 스택/큐 구현: 다른 자료구조의 기반으로 활용

실무 인사이트

모던 프로그래밍에서는 고수준 언어의 동적 배열(Array, List)을 주로 사용하지만, 연결 리스트의 원리를 이해하는 것은 여전히 중요합니다. 시스템 프로그래밍, 메모리 제약이 있는 환경, 또는 특수한 성능 요구사항이 있는 경우에는 직접 구현해야 할 수도 있습니다. 또한 면접에서 자주 출제되는 주제이므로, 구현과 활용법을 정확히 알아두는 것이 좋습니다.

---

참고 자료

• GeeksforGeeks - Linked List Data Structure
• MDN Web Docs - JavaScript Array
• Wikipedia - Linked List
• Visualgo - Linked List Visualization