21. 8. 4(수) TIL(Javascript 단일 연결 리스트 구현)

배준형·2021년 8월 4일

TIL

목록 보기

3/21

📌 연결리스트

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

연결 리스트의 종류

단일 연결 리스트(Singly Linked List) : 각 노드의 포인트는 다음 노드를 가리킨다.
이중 연결 리스트(Doubly Linked List) : 각 노드의 포인트는 다음, 이전 노드를 가리킨다.
원형 연결 리스트(Circular Linked List) : 처음, 마지막 노드가 연결되어 있다.

연결 리스트의 시간복잡도

요소 탐색에 O(n)의 시간 복잡도를 갖는다.
요소 추가 및 삭제에 O(1)의 시간 복잡도를 갖는다.

Javascript 연결리스트 구현

// 노드 객체
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 단일 연결 리스트 객체
class SinglyLinkedList {
  constructor() {
    this.head = null; // 초기값 head, tail = null, size = 0 초기화
    this.tail = null;
    this.size = 0;
  }
  
  // 요소 추가 메서드
  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size += 1; // 추가로 인한 size 1개 증가
  }
  
  // 요소 찾기 메서드
  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
      if (currNode === null) return null; // 연결 리스트에 입력된 value가 없을 때
    }
    
    return currNode;
  }
  
  // 요소 삭제 메서드
  remove(value) {
    if (this.find(value) === null) console.log(null); // 연결 리스트에 값이 없을 때
    else { // 연결 리스트에 값이 있을 때
      let prevNode = this.head;
      while (prevNode.next.value !== value) {
        prevNode = prevNode.next;
      }

      if (prevNode.next !== null) {
        prevNode.next = prevNode.next.next;
      }
      this.size -= 1; // 삭제로 인한 size 1개 감소
    }
  }
  
  // 요소 삽입 메서드
  insert(node, value) {
    if (node === null) console.log(null); // 입력된 node가 연결 리스트에 없을 때
    else { // 입력된 node가 연결 리스트에 있을 때
      const newNode = new Node(value);
      newNode.next = node.next;
      node.next = newNode;
      this.size += 1; // 삽입으로 인한 size 1개 증가
    }
  }
  
  // 요소 표시 메서드
  display() {
    let displayString = "["
    let currNode = this.head;
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    
    if (displayString.length === 1) console.log("[]"); // 만약 size = 0일 때 display() 호출 시 "[]" 표시
    else {
      displayString = displayString.substr(0, displayString.length - 2);
      displayString += "]";
      console.log(displayString);
    }
  }
}

📌 구현하면서 느낀 점

Javascript를 이용하여 자료구조, 알고리즘 문제를 풀 때 대부분 배열과 배열 메서드를 이용해서 문제를 풀었었는데 연결 리스트를 class로 구현해본 후 알고리즘 문제를 다시 풀어보았다.

처음엔 코드가 많이 복잡해 보였고 눈에 잘 들어오지 않았는데, 하나씩 써내려가면서 코드 한줄한줄 천천히 이해하면서 넘어가니 조금씩 이해가 되었다. 결과적으로 배열을 사용했을 때 보다 Processing 시간을 줄일 수 있어서 다양한 자료구조와 알고리즘을 더욱 공부해야 함을 느꼈다.

오늘 8/4 TIL을 작성하면서 코드를 보지 않고 하나씩 작성해 보았는데 아직 완전하게 익힌 것은 아닌 것 같다.

📌 앞으로

아직은 익숙하지 않지만 코드를 보지 않고 반복적으로 구현해보면서 연결 리스트를 익혀야겠다. 연결 리스트를 숙달하기 위함이 아니라 이러한 과정을 통해서 다음에 배우거나 학습할 자료구조나 알고리즘을 더욱 접근하기 수월하게 하기 위해선 꼭 필요한 과정이라고 생각한다. 위 단일 연결 리스트 구현 후 이중 연결 리스트(Doubly Linked List)를 도전해보다가 아직 구현하지 못했는데, 최대한 답을 찾지않고 스스로 구현해보는 과정을 거쳐야겠다.