연결리스트 Linked list

 

이번엔 자료구조 중 연결리스트에 대해 정리해본다.

 

연결리스트(Linked list)란?

 

연결리스트는 여러 개의 노드로 이루어져 있다. 각각의 노드는 객체로 value와 다음 노드가 뭔지 알려주는 주소를 가지고 있다.

또한 연결리스트에는 데이터를 추가(add), 조회(search), 제거(remove) 기능이 있어야 한다.

 

예를 들어 1 -> 2 -> 3 -> 4 -> 5 라는 연결 리스트가 있다면 데이터는 1, 2, 3, 4, 5가 되겠고 ->는 주소가 된다.

자바스크립트는 이것이 배열로서 구현이 되어 있다. 좀더 이해하기 쉽게

 

const arr = [1, 2, 3, 4, 5]에서

1, 2, 3, 4, 5는 데이터!

arr[0], arr[1] 등은 해당 데이터가 담긴 위치!.

물론 push, splice 등으로 추가 삭제도 가능하다.

 

이런 날먹을 사용하면 학습이 되지 않기 때문에 직접 만들어 본다.

 

노드와 연결리스트를 만들고

 

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

class LinkedList {
  length = 0;
  head = null;    
}

 

LinkedList의 length는 노드의 갯수, head가 첫 노드의 주소를 가르킨다.

이제 추가 검색 삭제 기능을 넣어보자

 

추가(add)

 

add(value) {
    if (this.head) {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = new Node(value);
    } else {
      this.head = new Node(value); 
    }
    this.length++;
    return this.length;
  }

head가 없다면(length가 0인 경우) 새로운 노드를 head 값에 넣어주고 length + 1

head가 있다면? 리스트를 순회(다음 노드가 존재하는 동안)

순회가 끝나면 current는 마지막 노드를 가리킬거고 마지막 노드의 next에 새로운 노드값을 넣어준다.

 

조회(search)

 

search(index) {
    return this.#search(index)[1]?.value;
  }
#search(index) {
    let count = 0;
    let prev;
    let current = this.head;
    while (count < index) {
      prev = current;
      current = current?.next;
      count++;
    }
    return [prev, current];
  }

카운트와 이전값에 사용할 변수를 선언해주고

내가 찾는 index 값에 다다를때까지

prev에는 현재 값 current에는 next 값을 넣어주며 순회한다.

배열 const arr =[1, 2, 3, 4, 5]에서 search(1)을 하게 된다면

this.#search(1)은

prev = arr[0] current는 prev의.next 이기에 arr[1]의 값이 들어가게 될거다.

[arr[0], arr[1]][1].value는 2가 나오게 된다.

 

마지막 제거(remove)

 

  remove(index) {
    const [prev, current] = this.#search(index);
    if (prev && current) {
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if (current) {
      this.head = current.next;
      this.length--;
      return this.length;
    }
  }
  
  일단 조회(search)를 통해 해당 index 값을 가져온다. #search가 prev값을 같이 반환해주는 이유
  
  prev와 current 둘다 있는경우 prev.next 값엔 current가 담겨있던걸 current.next로 교체

  length를 -1 해주고

  prev가 없고 current만 있는경우는? 인덱스가 0 인경우!
  
  prev 값을 바꿀 필요 없이 this.head엔 current의 next 값을 넣어주고 length를 -1 해주면 끝!

이 코드의 동작들에 시간 복잡도를 생각해본다면? 맨 앞에 추가하거나 조회하는건 O(1), 맨 뒤에 추가하거나 맨 뒤 값을 조회하는건 O(n)이 되겠다.

이 뿐만 아니라 이중 연결리스트, 다중 연결 리스트도 있다. 이중 연결 리스트의 차이점은 next값 외에도 prev을 넣어 이전 노드를 가리키게 하는 방법이고 다중 연결 리스트는 한 노드에서 next값을 배열로 만들어 여러 노드를 연결하는 방법이다.

이번 글은 제일 기본적인 연결리스트에 대해 다루었다.