[자료구조] 자바스크립트로 Linked List(단일 연결 리스트) 구현하기

안녕하세요!

오늘은 이선협 강사님의 자바스크립트 알고리즘 / 자료구조 강의 중 단일 연결리스트 구현 부분을 정리해보았습니다.

이해하는 데 조금 시간이 걸렸지만, 어떤 식으로 로직이 짜여지는지 알게 되었네요 :)

코멘트나 궁금하신 점은 댓글로 남겨주세요!  ⭐️

 

---

 

학습 목표: 단일 연결 리스트를 자바스크립트로 구현해보자!

 

---

 

단일 연결 리스트는 Node 클래스와 SinglyLinkedList 클래스로 구성된다.

 

먼저, 생성자 부분을 살펴보자.

 

 

생성자 부분

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

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

Node 클래스의 생성자 부분은 값(value)과 포인터(next)로 구분되어 있다. 

노드가 생성되는 시점에는 포인터가 아무것도 가리키지 않는다.

 

SinglyLinkedList 클래스는 head 와 tail 포인터로 이루어져있는데

해당 클래스는 노드와 노드끼리 역어주는 역할만 할 뿐, 그 자체로 노드를 가지진 않는다.

 

 

찾기 로직

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

  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode;
  }
}

일단 currNode 에 head 요소의 값을 담았고, while 문을 돌려 값을 찾기 전까지 계속 순회하게 될 것이다.

만약 값을 찾으면 루프는 종료되고, 해당 노드를 반환한다.

 

 

추가 로직

추가 로직은 끝 부분에 추가하는 append 로직과 중간에 끼워넣는 insert 로직으로 나누었다.

  //끝부분에 추가하는 append 로직
  append(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        this.tail = newNode;
    }
  }

 

append 로직을 살펴보면,

받은 값을 그대로 사용하여 Node 를 생성해준다.

head가 비어있다면 head와 tail 포인터에 생성된 Node를 가리키게 만든다.

변수에 객체를 대입하면 참조관계가 이루어진다.

this.tail.next = newNode 라는 건 대입이 아니고 this.tail.next는 newNode를 바라본다(참조한다.)라는 걸 이해하는 게 중요하다.

this.tail.next에 대입한 값을 바꾸는 것 같지만 사실은 이전에 생성했던 newNode의 값을 변경하는 것이기 때문이다.

(A to Z 강의 질문 목록에서 참고!)

 

순서로 보면 다음과 같다.

1. 처음에 head와 tail은 null

2. Node가 하나 추가되면 head와 tail은 추가된 Node를 바라봄.

3. 다시 Node가 추가되면 tail.next는 Node를 바라보고 tail도 Node를 바라봄

1. 이 과정에서 2에 해당하는 과정으로 인해 head = tail 이었기 때문에 head.next 와 tail.next 가 같음.
2. 따라서 head.next는 추가된 Node가 됨.
3. 결과적으로 head -> head.next -> tail 형태가 됨

// 중간에 끼워넣는 insert 로직 
 insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

단순하기 때문에 코드도 굉장히 단순하다.

첫번째 파라미터는 이전의 node를 가리키며, 이 node 다음에 끼워넣을 것이다.

 

1. 먼저 입력받은 값으로 Node를 생성한다.

2. 생성된 노드의 다음을 입력받은 Node의 다음으로 가리키게 만든다. (그림을 그려 이해하면 쉽다.)

3. 입력 받은 노드의 다음을 새로 생성된 노드를 가리키게 만들면 생성된 노드가 중간 사이에 끼워 넣어지게 된다!

 

 

삭제 로직

  remove(value) {
    let prevNode = this.head;
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }

여기에서는 값을 찾은 후 삭제하도록 로직을 작성했다. 따라서 해당 로직은 O(N) (선형 시간)이 소요된다. 

만약 O(1) (상수 시간)으로 삭제하고 싶다면 삭제할 노드의 이전 노드를 입력값으로 넣어주면 된다.

 

아래의 로직이 이해가 어렵다면 1, 2, 3, 4, 5 가 있는데 remove(3)을 실행한다고 생각하고 차근차근 따라가보면 이해가 될 것이다.

 

이제 로직을 살펴보자.

1. 먼저, 삭제할 노드의 이전 노드를 찾기 위해 prevNode 변수를 생성해준다.

    이때 앞서 살펴본 찾기 로직과 마찬가지로 Loop를 돌며 찾았다.

2. 이전 노드를 찾았다면, 이전 노드의 다음을 다음의 다음을 가리키도록 수정한다.

    그러면 중간 노드가 아무런 노드와 연결되지 않기 떄문에 자연스럽게 삭제된다.

     ✅ 참고로 해당 노드는 나중에 가비지 컬렉션을 통해 메모리에서 자동으로 삭제된다.

 

---

전체 코드

 

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

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

  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode;
  }

  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }

  remove(value) {
    let prevNode = this.head;
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }
}

---

 

 

이렇게 작성하면 이제 단일 연결 리스트를 사용할 수 있게 된다! 👏🏻

코딩테스트에서 직접 연결 리스트를 구현해서 사용하는 경우는 많지 않다.

그렇기 때문에 크게 외워둘 필요는 없지만, 한번쯤은 이 코드를 직접 타이핑하면서 이해하면 좋을 것 같다. :)