자바스크립트로 연결 리스트(Linked List) 구현하기

자바스크립트로도 연결 리스트를 구현할 수 있다. C언어랑 거의 비슷한데 C에서 구조체로 Node를 만들어줬던 것처럼 자바스크립트에서는 클래스로 Node의 구성을 만들어줄 수 있다. 연결 리스트의 기본 클래스 구조와, 원소를 추가하고, 삭제하는 방법을 정리해보았다.

 

참고: C언어로 구현하기 

 

1. 연결 리스트와 노드의 기본 구조

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

단방향 연결 리스트의 경우 뒤 노드의 값을 가리키는 next, 그리고 자신이 가지는 값인 data로 구성된 Node가 줄줄이 연결된 형태를 띠고 있다. 양방향 Node 구조체는 여기에서 자신의 앞 노드를 가리키는 this.prev가 추가된다.

 

class LinkedList {
  constructor() {
    this.head = null; 
    this.rear = null; 
    this.count = 0;
  }
}

연결 리스트의 기본 구조다. 맨 앞 노드인 head, 맨 뒤 노드인 rear, 연결 리스트의 원소의 개수인 size로 나타낸다. 아직 아무 원소도 넣지 않았기 때문에 노드는 모두 null이고, size는 0이다.

 

2. 연결 리스트에 원소 추가하는 함수

 

addFront(data) {
  const node = new Node(data);
  node.next = this.head;
  this.head = node;
  this.count++;
}

연결 리스트의 맨 앞에 원소를 추가하는 함수다. C에서는 새 노드를 위한 메모리를 동적 할당 해주지만 자바스크립트에서는 그럴 필요 없이 생성자 함수로 노드를 만들어서 변수에 할당한다. 연결 리스트의 맨 앞에 노드를 추가할 때는, 먼저 새로운 node가 기존의 head를 가리키게 만든다. 기존의 head 노드의 next가 가리키는 노드를 끊고 기존 head의 next는 새로운 node를 가리키게 한다. 그리고 사이즈를 올린다.

 

addMiddle(prev, data) {
   const node = new Node(data);
   let curNode = this.head;
   
   while (curNode.data !== prev) {
       curNode = curNode.next;
   }
   
   let temp = curNode.next;
   node.next = temp; // 새로운 노드의 next가 prev의 next를 가리키게 함
   curNode.next = node; // prev의 next가 새로운 노드를 가리키게 함
   
   this.count++;
}

중간에 추가하는 함수다. 새로운 node의 next가 prev의 next를 가리키게 한 다음, while문으로 찾아낸 prev의 next가 다시 새로운 노드를 가리키도록 바꿔준다. 

 

3. 연결리스트에서 노드 삭제하는 함수

 

removeMiddle(data) {
    let curNode = this.head;
    if (curNode.data === data) {
    	temp = curNode.next;
        curNode.next = null; // 앞에서 끊어주기
        this.head = temp;
    } else {
        while (curNode.next.data !== data) {
    		curNode = curNode.next;
    	}
    
        temp = curNode.next.next;
        curNode.next.next = null; // 앞에서 끊어주기
        curNode.next = temp;
    }
    this.count--;
}

연결 리스트의 data 원소를 삭제하는 함수다. data 원소가 head인 경우와 그렇지 않은 경우 방법이 차이가 있다. head인 경우에는 head의 next가 null을 가리키도록 하고 기존 head의 next를 head로 바꿔준다. head가 아니라 중간 어딘가 있는 원소라면 while문을 돌면서 조건에 맞는 노드에 도달하면 그 노드와 다음다음 노드를 연결해주면 된다.

 

removeLast() {
	let curNode = this.head;
    while (curNode.next.next !== null) {
    	curNode = curNode.next;
    }
    curNode.next = null;
    this.count--;
}

맨 마지막 원소를 삭제하는 함수다. next의 next가 null이 아닌 조건으로 쭉 연결 리스트를 따라가다가, 마지막에서 두 번째 원소의 next를 null을 가리키도록 만들면 마지막 원소는 자연스레 삭제가 된다.