[JavaScript] 연결리스트 Linked List in JS

Today, What I learned?

어제에 이어서 알고리즘 공부를 계속!...

자료구조 중 연결 리스트에 대해 정리해보고 구현해보는 시간을 가졌다.

튜터님의 알고리즘과 자료구조에 대한 코멘트와 연결 리스트에 대해 정리해보려 한다. 🙌

 

시간 복잡도와 공간 복잡도

시간 복잡도와 관련해서는 예전에 블로깅을 한 적이 있다.

https://i-ten.tistory.com/154

알고리즘의 시간복잡도와 Big-O

 

알고리즘에서는 이제 공간복잡도보다 시간 복잡도를 더 필수적으로 챙겨야 하는데,

공간 복잡도는 데이터의 크기가 훨씬 중요해서, 리소스를 얼마나 잡아먹느냐? 의 문제다.

물론 공간 복잡도도 낮을수록 좋다!

 

 

자료구조를 어떤 것을 기준으로 선택해야 할까?

자료구조를 선택할 때 고려해야 할 요소는 네 가지 정도가 있다.

1. 삽입 시간

2. 삭제 시간

3. 검색시간

4. 정렬 여부

 

자료구조는 데이터를 효율적으로 사용하고 관리하기 위해 사용하는 것이기 때문에, 우선순위를 따져서 적절한 자료구조를 선택하는 것이 좋을 것이다! 👏

 

 

연결 리스트 Linked List

연결 리스트는 O(N)의 시간 복잡도를 가지고 있고, 배열(Array)과 함께 비교가 많이 된다.

크기가 고정이 되어있는 배열과 다르게 앞 뒤의 포인터를 변경해서 원소를 유연하게 삽입/삭제할 수 있다.

 

연결 리스트를 기준으로 정리해보면 이렇다.

• 특정 원소를 조회할 때, 해당 노드까지 탐색해야 하기 때문에 시간 복잡도는 O(N)이다.
  • 배열은 인덱스로 바로 조회가 가능하기 때문에 O(1)
• 중간에 삽입/삭제가 이루어질 때의 시간 복잡도는 O(1)이다.
  • 배열의 경우 모든 원소를 옮겨야 하는 경우도 있기 때문에 O(N)
• 모든 공간이 다 찼어도 노드를 동적으로 추가할 수 있다.

따라서 데이터의 삽입과 삭제가 많은 경우라면 연결 리스트를 쓰는 것이 좋으며, 데이터에 접근하는 경우가 많은 경우라면 배열을 쓰는 것이 더 적합하다.

 

 

자바스크립트로 연결 리스트 구현하기

자바스크립트로 연결 리스트와 몇 가지 함수를 구현해보았다.
구현한 것은 단방향 연결 리스트!

 

Node

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

우선 노드 클래스.
초기값으로 다음 노드가 없기 때문에 null 값을 넣는다.

 

Linked List

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

초기 연결 리스트 클래스.
맨 앞, 맨 뒤를 나타내는 head와 tail. 길이를 나타내는 size 모두 초기값이다.

 

append()

  append(data) {
    let node = new Node(data);
    this.tail.next = node; // 마지막 노드에 새로운 노드 추가!
    this.tail = node; // 전체 리스트의 마지막 설정
    this.size += 1;
  }

마지막에 새로운 노드를 추가하는 append 함수
현재 마지막 노드의 포인터를 새로 생성된 노드로 향하게 만든다.
마지막 노드를 새로운 노드로 지정하고 전체 사이즈를 하나 늘려서 추가 마무리.

 

toString()

toString() {
    for (let node = this.head; node != null; node = node.next) {
      console.log(`${node.data} -> `);
    }
  }

모든 노드를 출력하기 위한 toString 함수.
출력을 위한 방법은 여러 가지지만, 나는 for문을 통해 노드를 마지막 노드까지 이동해가며 출력하는 방법을 선택했다.

 

insert()

insert(position = 0, data) {
    if (position < 0 || position > this.size) {
      return false;
    }

    let node = new Node(data);
    let curr = this.head;
    let prev,
      index = 0;

    if (position === 0) {
      node.next = curr;
      this.head = node;
    } else {
      while (index++ < position) {
        prev = curr;
        curr = curr.next;
      }
    }

    node.next = curr; // 새로운 노드에 next를 다음 노드로 지정 (중간에 끼어든 상태)
    prev.next = node; // 현재 노드를 새로운 노드에 가리켜서 중간에 끼어든 것 마무리

    this.size++;

    return true;
  }

원하는 위치에 값을 추가하는 insert 함수.

insert 되는 과정을 이해하는데 시간이 좀 걸렸다. 😇

먼저 해당 위치가 올바른 값이 아닐 경우에 대한 에러 처리를 해주었다.

 

원하는 위치가 0일 경우에는 바로 새로운 노드를 추가할 수 있도록 했고,
아닌 경우에는 해당 위치까지 이동을 하는데 이때 prev 라는 변수에 현재 노드를 담아가며 이동한다.

원하는 위치에 도착했을 때, 새로운 노드의 포인터를 끼어들 위치의 다음 노드를 향하게 한다.

새로 끼어드는 62번의 포인터가 6을 향하는 중!

그리고 기존 노드의 포인터가 새로운 노드를 가리키도록 한다.

기존 노드 77이 새로운 노드 62를 가리킨다

추가 완!

그럼 추가 완.

 

removeAt()

removeAt(position = 0) {
    if (position < 0 || position >= this.size) {
      return false;
    }

    let current = this.head;
    let index = 0;
    let prev;

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

      prev.next = current.next; // 이전 노드가 다음 노드 가리키도록 함
    }
    this.length--;
  }

원하는 위치의 노드를 삭제하는 removeAt 함수.
위치에 대한 에러 처리와 해당 노드를 탐색하는 과정은 위와 동일하다.

다만 삭제할 때는 삭제하려는 노드를 current라고 했을 때,
이전 노드의 포인터가 current의 다음 노드를 향하도록 한다.

 

삭제되는 중인 62

더 이상 head로부터 탐색이 불가능하게 된 62는 자연스레 삭제!.. 

삭제 완.

 

 

이제 이걸 기반으로 여러 함수를 짜 볼 수 있겠지만 오늘은 이만큼 이해하기도 벅차다 벅차 😇...

연결 리스트 문제를 조금이나마 건드려볼 수 있기를 희망하며 오늘 TIL을 마친다!.. 👏