JS 알고리즘 공부 3회차 with. BaaaaaaaarkingDog

# 연결 리스트

"원소들을 저장할 때 다음 원소가 있는 위치를 포함시켜 저장하는 자료구조"

 

연결 리스트의 성질

1. O(1)에 임의의 위치에 원소를 추가 및 삭제 가능
2. 원소들이 메모리 상에 연속되어 있지 않아서 할당이 쉽다
3. cache hit rate가 낮다

시간복잡도

• n번째 원소 확인 및 변경 → O(n)
• 임의의 위치에 원소를 추가 및 삭제 가능 → O(1)

연결 리스트의 종류

• 단일 연결 리스트 : 각 원소가 다음 원소의 주소만 가진 연결 리스트
• 이중 연결 리스트 : 각 원소가 다음 원소의 주소뿐만 아니라 이전 원소의 주소까지 가진 연결 리스트
• 원형 연결 리스트 : 마지막 원소가 다음 원소의 주소로 헤더의 주소를 가진 연결 리스트. 단일 연결 리스트와 이중 연결리스트의 형태 모두 가능

배열과의 비교

연결 리스트의 성질을 보면 배열의 성질과 반대되는 것을 알 수 있다.

성질	연결 리스트	배열
n번째 원소 접근 및 변경	O(n)	O(1)
임의의 위치에 원소 추가 및 삭제	O(1)	O(N)
메모리 상의 배치	불연속	연속
Overhead	거의 없다	O(N)

 

실제로 연결 리스트에서 임의의 위치를 제공받을 때 해당 원소의 주소가 아닌 n번째로 주어진다면 실제 시간복잡도는 O(1)이 아니게 된다. 아무튼 n번째 원소에 접근하는데 O(n)이 걸리는 자료구조를 어디다가 사용하는가? 장점이 확실한 임의의 위치에 원소 추가 및 삭제가 많은 연산에서 사용된다.

 

구현

class Node { // 데이터와 다음 원소를 가리키는 주소를 가진 원소
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }
  
  size() {
    let count = 0;
    let node = this.head;
    
    while(node) {
      count++;
      node = node.next;
    }
    
    return count;
  }
  
  traverse() { // 리스트 출력
    if(!this.head) return 'empty';
    let list = '';
    let node = this.head;
    
    while(node) {
      list += node.data+' ';
      node = node.next;
    }
    list -= ' ';
    
    return list;
  }
  
  clear() {
    this.head = null;
  }
  
  get(index) {
    if(!this.head) return 'empty';
    let node = this.head;
    
    for(let i=0; i<index; i++) {
      if(node.next) node = node.next;
      else return 'index too big';
    }
    
    return node;
  }
  
  insert(data, index = 0) {
    if(!this.head) { // 빈 리스트인 경우
      this.head = new Node(data);
      return;
    }
    
    if(index === 0) { // 맨 앞에 원소를 추가하는 경우
      this.head = new Node(data,this.head);
      return;
    }
    
    const prev = this.get(index-1) || this.get(this.size());
    const node = new Node(data, prev.next);
    prev.next = node;
  }
  
  erase(index = 0) {
    if(!this.head) return 'empty';
    
    if(index === 0) { // 맨 앞에 원소를 삭제하는 경우
      this.head = this.head.next;
      return;
    }
    
    const prev = this.get(index-1);
    if(prev === 'index too big' || !prev.next) return `list size : ${this.size()}`;
    const erase_data = prev.data;
    prev.next = prev.next.next;
    
    return erase_data;
  }
}

 

JavaScript에서 연결 리스트를 사용하기에는 주소값을 이용할 수 없기 때문에 n번째로 찾아야 하기 때문에 비효율적이라고 생각이 든다. 또한 해당 코드를 코딩 테스트에서 작성하고 있을 생각을 하니 벌써 머리가 아픈 거 같다... BaaaaaaaarkingDog님이 남긴 문제를 풀어보며 더 느껴봐야겠다.

 

출처 & 참고

연결리스트, BaaaaaaaarkingDog, 2024.04.08

Linked List in JavaScript, Nara Lee, 2024.04.08

연결리스트 삽입, 검색, 삭제, 김알리, 2024.04.08