연결리스트(Linked List)

1. 연결리스트란?

연결리스트는 각 노드가 오직 한 방향(다음 노드)으로만 연결되어 있는 선형 자료구조
각 노드는 두 가지 정보를 가짐.

• 데이터(Data): 저장하고자 하는 값
• 포인터(Next): 다음 노드를 가리키는 참조(주소)

리스트의 시작은 헤드(Head) 노드로, 끝은 null(혹은 None)로 표시함.

구조 예시

[Head] -> [Node1] -> [Node2] -> [Node3] -> null

2. 연결리스트의 장점과 단점

장점

• 동적 크기: 필요에 따라 노드를 추가/삭제할 수 있어 메모리 효율적
• 빠른 삽입/삭제: 특정 위치(특히 맨 앞)에서의 삽입/삭제가 빠름 (O(1))

단점

• 느린 탐색: 임의 접근이 불가능해, 원하는 위치까지 순차적으로 접근해야 함 (O(n))
• 추가 메모리 사용: 데이터 외에 포인터를 위한 메모리 필요

3. 연결리스트의 활용 예시

1) 스택(Stack)과 큐(Queue) 구현

• 스택: Head에 push/pop을 하면 LIFO 구조를 쉽게 구현 가능
• 큐: Head와 Tail 포인터를 활용해 FIFO 구조 구현

2) 동적 데이터 관리

• 실시간 데이터 추가/삭제가 빈번한 작업
  예: 작업 리스트, 대기열 등

3) 해시 테이블의 체이닝

• 해시 충돌 시, 같은 해시값을 가진 데이터를 단일 연결리스트로 관리

4. 연결리스트의 한계와 개선 방향

• 역방향 탐색 불가: 한 방향으로만 이동 가능, 이전 노드로 돌아갈 수 없음
• 임의 접근 비효율: 인덱스 기반 접근이 느림

이런 한계를 극복하기 위해 이중 연결리스트(Doubly Linked List), 원형 연결리스트(Circular Linked List) 등이 고안됨.

구현

// Node() : data와 point를 가지고 있는 객체
function Node(data) {
  this.data = data;
  this.next = null;
}

// LinkedList(): head와 length를 가지고 있는 객체
function LinkedList() {
  this.head = null;
  this.length = 0;
}

// size() : 연결 리스트 내 노드 개수 확인
LinkedList.prototype.size = function () {
  return this.length;
}

// isEmpty() : 객체 내 노드 존재 여부 파악
LinkedList.prototype.isEmpty = function () {
  return this.length === 0;
}

// printNode() : 노드 출력
LinkedList.prototype.printNode = function () {
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(`${node.data} -> `);
  }
  console.log("null");
}

// append() : 연결 리스트 가장 끝에 노드 추가
LinkedList.prototype.append = function (value) {
  let node = new Node(value),
    current = this.head;

  if (this.head === null) {
    this.head = node;
  } else {
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }

  this.length++;
};

// insert() : position 위치에 노드 추가
LinkedList.prototype.insert = function (value, position = 0) {
  if (position < 0 || position > this.length) {
    return false;
  }

  let node = new Node(value),
    current = this.head,
    index = 0,
    prev;

  if (position == 0) {
    node.next = current;
    this.head = node;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    node.next = current;
    prev.next = node;
  }

  this.length++;

  return true;
};

// remove() : value 데이터를 찾아 노드 삭제
LinkedList.prototype.remove = function (value) {
  let current = this.head,
    prev = current;

  while (current.data != value && current.next != null) {
    prev = current;
    current = current.next;
  }

  if (current.data != value) {
    return null;
  }

  if (current === this.head) {
    this.head = current.next;
  } else {
    prev.next = current.next;
  }

  this.length--;

  return current.data;
};

// removeAt() : position 위치 노드 삭제
LinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    return null;
  }

  let current = this.head,
    index = 0,
    prev;

  if (position == 0) {
    this.head = current.next;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    prev.next = current.next;
  }

  this.length--;

  return current.data;
}

// indexOf() : value 값을 갖는 노드 위치 반환
LinkedList.prototype.indexOf = function (value) {
  let current = this.head,
    index = 0;

  while (current != null) {
    if (current.data === value) {
      return index;
    }

    index++;
    current = current.next;
  }

  return -1;
}

// remove2() : indexOf + removeAt = remove
LinkedList.prototype.remove2 = function (value) {
  let index = this.indexOf(value);
  return this.removeAt(index);
};