[자료구조] 연결리스트

여태까지 자료구조 알고리즘 공부는 문제 풀기에 급급했던 것 같다. 지금 여유가 조금 날 때, 자료구조들을 직접 구현해보면서 그 원리를 잘 이해하는 것이 필요하다고 생각했다. 이번에는 가장 기본적인 연결리스트를 구현해본다.

1. 정의

원소를 배치할 때, index에 따라 물리적으로 배치하는 것이 아니라 노드의 포인터가 다음 노드를 가리키는 것으로 배치한다. 이를 통해 원소를 삽입/삭제할 때 데이터 구조를 재정렬하지 않아도 된다.

2. 장단점

2-1. 장점

• 원소 삽입/삭제 용이
• 데이터 구조 재정렬 필요없음

2-2. 단점

• 배열보다 메모리 많이 듬
• 원소 검색시 비효율

3. 구현

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

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

  // 1. 첫번째 삽입
  insertFirst(data) {
    this.head = new Node(data, this.head);
    this.size = this.size + 1;
  }

  // 2. 마지막 삽입
  insertLast(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size += this.size + 1;
  }
  // 3. 중간 삽입
  insertAt(data, index) {
    // 1. index의 값부터 확인
    if (index > 0 && index > this.size) {
      return;
    }

    if (index === 0) {
      this.head = new Node(data, this.head);
      this.size += 1;
      return;
    }

    const node = new Node(data);
    let current, previous;

    current = this.head;
    let count = 0;
    while (count < index) {
      previous = current;
      count++;
      current = current.next;
    }
    previous.next = node;
    node.next = current;
    this.size += 1;
  }

  getAt(index) {
    let count = 0;
    let current = this.head;
    while (current) {
      if (count === index) {
        console.log(current);
        return null;
      }
      count++;
      current = current.next;
    }
    console.log("없습니다.");
    return null;
  }

  removeAt(index) {
    if (index > 0 && index > this.size) {
      return;
    }
    let count = 0;
    let current = this.head;
    let previous = current;

    if (index === 0) {
      this.head = current.next;
    } else {
      while (count < index) {
        count++;
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
    }
    this.size--;
  }

  clearList() {
    // 이렇게 지워도 데이터는 남아있는 거 아니야?
    this.head = null;
    this.size = 0;
  }

  printListData() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}

const a = new LinkedList();
a.insertFirst(100);
console.log(a);

4. 느낀점

linkedList는 데이터 삽입/삭제 후 데이터 재조정을 하지 않아도 돼서 편하다는 것을 많이 느꼈다.

하지만 remove를 할 때나 clearList를 할 때 데이터 간 연결을 끊을 뿐이지 메모리 자체는 남아있을 것으로 보여서 메모리를 많이 잡아 먹지 않나 싶다.
이 메모리 부분에 있어서 각 노드는 data와 next 값을 가지고 있기 때문에 이 부분도 배열보다 메모리를 많이 먹을 것이다.

고로 데이터 삽입/삭제가 빈번한 상황에서 사용하기 적합하고 아니면 커널 모드에서 데이터를 굉장히 빠르게 처리할 수 있는 상황에서 쓰면 좋을 거 같다. 이외에는 배열로 빨리 처리하는 게 좋지 않을까?