연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드에 대한 참조(포인터)를 함께 저장하는 선형 자료구조입니다. 배열과 달리 요소를 삽입하거나 삭제할 때 나머지 요소를 한 칸씩 이동시킬 필요가 없으므로, 데이터의 동적인 추가와 삭제가 빈번한 상황에서 효율적으로 동작합니다.
LinkedList 클래스 전체 구현
다음은 자바스크립트로 작성한 LinkedList 클래스의 완전한 구현 코드입니다. 리스트 초기화를 담당하는 생성자, 노드 삽입(insert), 노드 삭제(remove), 리스트 출력(display) 메서드와 내부에서 사용되는 Node 클래스로 구성되어 있습니다.
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
insert(data, position = this.length) {
let node = new this.Node(data);
if (this.head === null) {
this.head = node;
this.length++;
return this.head;
}
let iter = 1;
let currNode = this.head;
while (currNode.next != null && iter < position) {
currNode = currNode.next;
iter++;
}
node.next = currNode.next;
currNode.next = node;
this.length++;
return node;
}
remove(data, position = 0) {
if (this.length === 0) {
console.log('List is already empty');
return;
}
this.length--;
let currNode = this.head;
if (position <= 0) {
this.head = this.head.next;
} else if (position >= this.length - 1) {
while (currNode.next.next != null) {
currNode = currNode.next;
}
currNode.next = null;
} else {
let iter = 0;
while (iter < position) {
currNode = currNode.next;
iter++;
}
currNode.next = currNode.next.next;
}
return currNode;
}
display() {
let currNode = this.head;
while (currNode != null) {
console.log(currNode.data + ' -> ');
currNode = currNode.next;
}
}
}
LinkedList.prototype.Node = class {
constructor(data) {
this.data = data;
this.next = null;
}
};
코드 동작 원리
생성자(constructor) : 리스트의 시작점인 head를 null로 초기화하고, 현재 노드 개수를 저장하는 length를 0으로 설정합니다.
insert() : 새 노드를 지정한 위치에 삽입합니다. 위치를 생략하면 리스트 맨 뒤에 추가됩니다. 리스트가 비어 있으면 새 노드가 곧 head가 되고, 그렇지 않으면 대상 위치 앞의 노드를 찾아 참조를 재연결하여 노드를 끼워 넣습니다.
remove() : 지정한 위치의 노드를 삭제합니다. 리스트가 비어 있으면 콘솔에 안내 메시지를 출력하고 종료합니다. 위치가 0 이하이면 첫 번째 노드를 제거하고 head를 다음 노드로 이동하며, 맨 뒤 노드를 삭제하는 경우 마지막 노드 앞 노드의 참조를 null로 만듭니다. 그 외의 경우에는 해당 위치의 노드를 건너뛰도록 참조를 재연결합니다.
display() : head부터 시작하여 각 노드의 데이터를 순서대로 콘솔에 출력합니다.
Node 클래스 : LinkedList.prototype.Node 형태로 정의되어 있으며, 실제 데이터(data)와 다음 노드에 대한 참조(next)를 저장합니다. 프로토타입에 정의해 두면 new this.Node(data)처럼 LinkedList 내부에서 바로 노드를 생성할 수 있습니다.
사용 예제
const list = new LinkedList(); list.insert(10); // 리스트: 10 list.insert(20); // 리스트: 10 -> 20 list.insert(30); // 리스트: 10 -> 20 -> 30 list.display(); // 출력: 10 -> 20 -> 30 -> list.remove(30, 0); // 첫 번째 노드 삭제 list.display(); // 출력: 20 -> 30 ->
이 구현은 연결 리스트의 기본 동작을 익히기 위한 학습용 예제입니다. 실무에서는 양방향 탐색이 가능한 이중 연결 리스트나, 헤드와 테일 포인터를 함께 관리하는 구조 등을 활용하면 더 다양한 요구 사항을 효율적으로 처리할 수 있습니다.