[자료구조와 알고리즘] Linked List 구현해보기

이미지 출처: wikipedia

자바스크립트에서 Linked List 를 구현하는 방법은 클래스 문법을 사용할 수도 있고 기본 함수를 사용할 수도 있습니다.

Class 문법

편의를 위해서 탄생한 클래스 문법은 함수의 프로토타입을 이용해서 만들어졌고 ES2015에서 도입되었습니다. "use strict" 문구가 없어도 클래스의 본문에서는 strict mode로 실행됩니다. 그리고 클래스는 함수와는 다르게 호이스팅되지 않습니다.

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

class LinkedList {
  	// 생성자 함수
    // head 와 tail 은 고정되어 있고 그 사이에 노드를 생성하는 형태
    constructor() {
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.length = 0;
    }

    addFirst(data){
      	// head 는 위치가 고정되어 있기 때문에 head의 다음에 위치시킵니다. 
        const newNode = new Node(data);
        newNode.next = this.head.next;
        this.head.next = newNode;
        this.length++;
    }

    addLast(data) {
      	// tail의 바로 앞 노드까지 찾아서 다음 노드로 위치시킵니다.
        const newNode = new Node(data);
        let prevNode = this.head;
        for (let i=0; i<this.length; i++) {
            prevNode =  prevNode.next;
        }
        prevNode.next = newNode;
        newNode.next = this.tail;
        this.length++;
    }

    // 특정 위치에 데이터 추가
    add(idx, data) {
        const newNode = new Node(data);
        let prevNode = this.head;
        for (let i=0; i<idx; i++) {
            prevNode =  prevNode.next;
        }
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        this.length++;
    }

    get(idx) {
        let node = this.head;
        for (let i=0; i<=idx; i++) {
            node =  node.next;
        }
        return node.data;
    }

    // 특정 위치에 데이터 변경
    set(idx, data) {
        let node = this.head;
        for (let i=0; i<=idx; i++) {
            node =  node.next;
        }
        node.data = data;
        return node.data;
    }

    remove(idx) {
        let prevNode = this.head;
        for (let i=0; i<idx; i++) {
            prevNode =  prevNode.next;
        }
      	// 삭제할 노드의 데이터를 반환하기 위해 변수에 잠시 담아둡니다.
        const deletedNode = prevNode.next;
        prevNode.next = deletedNode.next;
        return deletedNode.data;
    }
}

Function

클래스 문법에 익숙하시다면 클래스 문법의 생성자 함수가 따로 떨어져나왔다고 생각할 수 있습니다!

// LeetCode 에서 제시되는 singly-linked list
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

함수를 사용해서 각 노드마다 생성하면서 다음 노드를 연결시켜주면 링크드 리스트를 생성할 수 있습니다.

const listNode1 = new ListNode(3)
const listNode2 = new ListNode(2, listNode1)
const listNode3 = new ListNode(1, listNode2)
console.log(listNode3)
/*
ListNode {
  val: 1,
  next: ListNode { val: 2, next: ListNode { val: 3, next: null } }
}
*/