Javascript 자료구조 시리즈(4) Linked List

 

Linked List는 배열과 유사한 선형 데이터 구조입니다. 그러나 배열과 달리 요소는 특정 메모리 위치나 인덱스에 저장되지 않습니다.
오히려 각 요소는 해당 목록의 다음 개체에 대한 포인터 또는 링크를 포함하는 별도의 개체입니다. 노드 그룹으로 구성되며 각 노드에는 다음 노드에 대한 고유한 데이터와 주소가 있습니다.

배열에서 요소는 인덱싱되며 즉시 요소에 도달할 수 있지만 Linked List에서는 머리부터 시작하여 원하는 요소에 도달할 때까지 계속 작업해야 합니다.

Linked List의 장점은 Linked List에서 삽입 및 삭제가 배열보다 쉽다는 것입니다. 배열은 단 한개의 원소 추가할 때도 뒷쪽에 있는 원소들이 모두 변경되어야 되며 10만개 이상의 배열이면 시간이 많이 소모됩니다. 왜나하면 배열의 요소가 연속적인 위치에 저장되기 때문입니다.

 

각 요소(일반적으로 노드라고 함)에는 저장된 데이터와 다음 노드에 대한 링크라는 두 가지 항목이 포함됩니다.
데이터는 모든 유효한 데이터 유형이 될 수 있습니다. 아래 다이어그램에서 이를 확인할 수 있습니다.

 

 

연결 리스트의 진입점을 헤드라고 합니다. 헤드는 연결 목록의 첫 번째 노드에 대한 참조입니다.
목록의 마지막 노드는 null을 가리킵니다. 목록이 비어 있으면 헤드는 null 참조입니다.

 

JavaScript에서 linked list는 이렇게 생겼습니다.

const list = {
    head: {
      value: 1,
      next: {
        value: 2,
        next: {
          value: 3,
          next: {
            value: 4,
            next: null
          }
        }
      }
    }
  }

 

Linked List의 장점
- 전체 데이터 구조를 재구성하지 않고도 Linked List에서 노드를 쉽게 제거하거나 추가할 수 있습니다. 이것은 배열에 비해 한 가지 장점입니다.

Linked List의 단점
- Linked List에서 검색 작업이 느립니다. 배열과 달리 데이터 요소에 대한 임의 액세스는 허용되지 않습니다. 노드는 첫 번째 노드부터 순차적으로 액세스됩니다.
- 포인터의 저장으로 인해 배열보다 더 많은 메모리를 사용합니다.

Linked List의 유형
Linked List에는 세 가지 유형이 있습니다.
- 단방향 Linked List: 각 노드에는 다음 노드에 대한 포인터가 하나만 포함됩니다.
- 양방향 Linked List: 각 노드는 두 개의 포인터, 다음 노드에 대한 포인터와 이전 노드에 대한 포인터를 포함합니다.
- 원형 Linked List(Circular Linked List): 원형 Linked List는 마지막 노드가 첫 번째 노드 또는 그 이전의 다른 노드를 가리키며 루프를 형성하는 Linked List의 변형입니다.

JavaScript에서 List 노드 구현
앞에서 언급했듯이 List 노드에는 데이터와 다음 노드에 대한 포인터라는 두 가지 항목이 있습니다. 다음과 같이 JavaScript에서 List 노드를 구현할 수 있습니다.

 

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

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

  // list에 있는 노드 수를 반환합니다.
  size() {
    let count = 0;
    let node = this.head;
    while (node) {
      count++;
      node = node.next
    }
    return count;
  }

  // list를 비웁니다.
  clear() {
    this.head = null;
  }

  // list의 마지막 노드를 반환합니다.
  getLast() {
    let lastNode = this.head;
    if (lastNode) {
      while (lastNode.next) {
        lastNode = lastNode.next
      }
    }
    return lastNode
  }

  // list의 첫 번째 노드를 반환합니다.
  getFirst() {
    return this.head;
  }
}

 

사용법은 다음과 같습니다.

우선 Linked List에 추가할 node를 생성합니다.

    let node1 = new ListNode(1)
    console.log('노드 추가 전 node1 : ', node1)
    /*
      LOG RESULT
      노드 추가 전 node1 :  ListNode{data: 1, next: null}    
    */

    let node2 = new ListNode(2)
    node1.next = node2
    console.log('노드 추가 후 node1 : ', node1.data)
    /*
      LOG RESULT
      노드 추가 후 node1 :  ListNode{
                              data: 1,
                              next: {
                                data: 2,
                                  next: null
                              }
                            }
    */

    let node3 = new ListNode(3)
    node2.next = node3
    let node4 = new ListNode(4)
    node3.next = node4
    console.log('최종 노드 추가 후 node1 : ', node1)
    /*
      LOG RESULT
      최종 노드 추가 후 node1 :  ListNode {
                                data: 1
                                next: {
                                  data: 2
                                  next: {
                                    data: 3
                                    next: {
                                      data: 4
                                      next: null
                                    }
                                  }
                                }
                             }
    */

 

생성된 node를 Linked List에 넣고 활용하면 됩니다.

    const linkedList = new LinkedList(node1)
    console.log('linkedList.size() : ', linkedList.size());
    console.log('linkedList.getFirst() : ', linkedList.getFirst());
    console.log('linkedList.getLast() : ', linkedList.getLast());
    linkedList.clear()
    console.log('after clear linkedList.size() : ', linkedList.size());

    /*
      LOG RESULT
      linkedList.size() :  4
      linkedList.getFirst() :  ListNode{data: 1, next: ListNode}
      linkedList.getLast() :  ListNode{data: 4, next: null}
      after clear linkedList.size() :  0
    */