자바스크립트의 자료구조 3 : 연결 리스트(Linked List)

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 연결 리스트(Linked List)란?

Singly Linked List

Linked List는 1) value와 2) pointer가 한 쌍인 노드가 모여있는 자료구조형을 의미한다. 위 사진에서 푸른색 부분은 data를 저장하고 있고, 초록색 부분은 다음 노드를 가리키는 pointer 역할을 하는 address 부분이다.

Linked List에서 가장 앞 쪽 시작부분(위 사진에서는 10을 가지고 있는 노드)을 Head, 가장 마지막 부분(40을 가지고 있는 노드)을 Tail이라고 부른다. Tail의 pointer는 더 이상 가리킬 노드가 존재하지 않으므로 Null을 가리키게 된다.

 

2. Linked List vs. 배열, 객체

# Linked List vs. 배열

- lookup : 배열은 모든 element가 인덱싱 되어 있기 때문에 특정 값을 살펴볼 경우 시간복잡도는 O(1)이다. 반면 Linked List는 특정 값을 살펴보려면 Head에서부터 시작해서 Linked List내의 노드들을 traversing해야 한다. 따라서 Linked List에서 lookup의 시간복잡도는 O(n)이다.

- insert : 반면 특정 값을 삽입할 경우에는 Linked List가 배열보다 낫다.

 

# Linked List vs. 객체

- delete, insert : Linked List와 객체 모두 빠르다.

- Linked List는 다음 노드를 가리키는 pointer가 있으므로 order가 있는 자료구조인 반면, 객체는 unordered한 자료구조이다.

 

3. Linked List의 작업별 시간복잡도

- prepend(맨 앞에 삽입) : O(1)

- append(맨 뒤에 삽입) : O(1)

- lookup(traversal) : O(n)

- insert : O(n)

- delete : O(n)

 

4. 포인터(pointer)란?

const obj1 = { a: true };
const obj2 = obj1; // 이게 pointer이다. 

포인터는 기본적으로 원하는 데이터가 저장되어 있는 메모리 주소를 referencing 하는 작업이다. 위 코드의 경우 { a: true } 라는 객체는 하나의 메모리 공간만 차지해서 저장되어 있다. 다만 obj1과 obj2가 모두 그 메모리 주소를 참조하고 있을 뿐이다.

참고로 자바스크립트에서는 포인터가 특정 메모리 주소를 참조하고 있을 경우, garbage collector가 해당 메모리 주소가 사용 중인 것으로 간주하여 메모리 공간에서 삭제되지 않는다.

 

const obj1 = {a: true};
const obj2 = obj1;
delete obj1;

console.log(obj1); // ReferenceError
console.log(obj2); // {a: true}

 

5. Linked List 메소드 구현

Linked List의 메소드를 직접 구현하면서 작업별 시간 복잡도를 이해해보자.

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    };
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = {
      value: value,
      next: null
    }
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }
  prepend(value) {
    const newNode = {
      value: value,
      next: null
    }
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }
  printList() {
    const array = [];
    let currentNode = this.head;
    while(currentNode !== null){
        array.push(currentNode.value)
        currentNode = currentNode.next
    }
    return array;
  }
  insert(index, value){
    //Check for proper parameters;
    if(index >= this.length) {
      console.log('yes')
      return this.append(value);
    }
    
    const newNode = {
      value: value,
      next: null
    }
    const leader = this.traverseToIndex(index-1);
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return this.printList();
  }
  traverseToIndex(index) {
    //Check parameters
    let counter = 0;
    let currentNode = this.head;
    while(counter !== index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  remove(index) {
    // Check Parameters      
    const leader = this.traverseToIndex(index-1);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    this.length--;
    return this.printList();
  }
}

let myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);myLinkedList.prepend(1);
myLinkedList.insert(2, 99);
myLinkedList.insert(20, 88);
myLinkedList.remove(2);

 

6. Doubly Linked List

Singly Linked List의 경우 하나의 노드가 value와 다음 노드 pointer 두개로 이루어졌다면, Doubly Linked List는 value, 이전 노드 pointer, 다음 노드 pointer 이렇게 3개의 조각으로 이루어져 있다.

 

7. 결론

- 장점 : Fast Insertion, Fast Deletion, Ordered, Flexible Size

- 단점 : Slow lookup, More Memory