자료구조와 알고리즘, 링크드 리스트, Single Linked List

JavaScript에서 링크드 리스트(Linked List)는 노드(Node)들이 포인터로 연결된 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 링크드 리스트는 배열(Array)과 비교했을 때 몇 가지 주요 차이점이 있습니다.

기본 개념

• 노드(Node): 링크드 리스트의 각 요소는 노드라고 불리며, 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
• 헤드(Head): 링크드 리스트의 시작 노드를 가리킵니다.
• 테일(Tail): 링크드 리스트의 마지막 노드를 가리킵니다.
• 포인터(Next): 각 노드는 다음 노드를 가리키는 포인터를 포함합니다.

링크드 리스트의 구조

링크드 리스트는 주로 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)로 나뉩니다. 단일 연결 리스트에서는 각 노드가 다음 노드만 가리키지만, 이중 연결 리스트에서는 각 노드가 다음 노드와 이전 노드를 모두 가리킵니다.

자바스크립트로 구현한 링크드 리스트

다음은 자바스크립트로 단일 연결 리스트를 구현한 예제입니다:

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

class SingleLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(data) {
    var newNode = new Node(data);
    // list가 비어 있다면, head와 tail을 모두 새 노드로 설정합니다.
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 기존 node - tail의 next에 newNode 삽입
      this.tail.next = newNode;
      // 리스트의 끝이므로 tail에 newNode 삽입
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  traverse() {
    var current = this.head;
    while (current) {
      console.log('current:', current);
      current = current.next;
    }
  }

  pop() {
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = this.head;

    // while 문 조건 이해하기
    while (current.next) {
      newTail = current;
      current = current.next;
    }

    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }

    return current;
  }

  shift() {
    // if there are no nodes, return undefined
    // Store the current head property in a variable
    // Set the head property to be the current head's next property
    // Decrement the length by 1
    // Return the value of the node removed

    if (!this.head) return undefined;

    let currentHead = this.head;

    this.head = currentHead.next;
    this.length--;

    if (this.length === 0) {
      this.tail = null;
    }

    return currentHead;
  }

  unshift(data) {
    // This function should accept a value
    // Create a new node using the value passed to the function
    // If there is no head property on the list, set the head and tail to be the newly created node
    let newNode = new Node(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;

    return this;
  }

  get(index) {
    // 인덱스가 음수이거나 리스트의 길이보다 큰 경우 null을 반환합니다.
    if (index < 0 || index >= this.length) return null;

    let cnt = 0;
    let currentHead = this.head;

    while (cnt !== index) {
      currentHead = currentHead.next;
      cnt++;
    }

    return currentHead;
  }

  set(index, data) {
    // This function should accept a data an an index
    // Use your get function to find the specific node
    // If the node is not found, return false
    // If the node is found, set the value of that node to be the value passed to the function and return true
    if (index < 0 || index >= this.length) return null;

    let current = this.get(index);
    if (!current) return false;

    current.data = data;

    return true;
  }

  insert(index, data) {
    // If the index is less than zero or greater than the length, return false
    // If the index is the same as the length, push a new node to the end of the list
    // If the index is 0, unshift a new node to the start of the list
    // Otherwise, using the 'get' method, access the node at the index -1
    // Set the next property on that node to be the new node
    // Set the next property on the new node to be the previous next
    // Increment the length
    // Return true;

    if (index < 0 || index > this.length) return false;

    if (index === this.length) {
      // 'push'
      this.push(data);
      return true;
    }

    if (index === 0) {
      // 'unshift'
      this.unshift(data);
      return true;
    }

    // 'normal case'
    let newNode = new Node(data);

    let prevNode = this.get(index - 1);
    newNode.next = prevNode.next;
    prevNode.next = newNode;

    this.length++;
    return true;
  }

  remove(index) {
    // If the index is less than zero or greater than the length, return undefined
    // If the index is the same as the length-1, 'pop'
    // If the index is 0, 'shift'
    // Otherwise, using the 'get' method, access the node at the index -1
    // Set the next property on that node to be the next of the next node
    // Decrement the length
    // Return the value of the node removed

    if (index < 0 || index > this.length) return false;

    if (index === this.length - 1) {
      // 'pop'
      this.pop();
      return true;
    }

    if (index === 0) {
      // 'shift'
      this.shift();
      return true;
    }

    let prevNode = this.get(index - 1);
    let nextNode = prevNode.next.next;

    prevNode.next = nextNode;

    this.length--;
    return true;
  }

  reverse() {
    // Swap the head and tail
    // Create a variable called next
    // Create a variable called prev
    // Create a variable called node and initialize it to the head property
    // Loop through the list
    // See the next to be the next property on whatever node is
    // Set thee next property on the node to be whatever prev is
    // Set prev to be the value of the node variable
    // Set the node variable to be the value of the next variable

    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    let next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }
    return this;
  }
}

var list = new SingleLinkedList();

list.push('Hi');
list.push('there');
list.push('!');
list.unshift('Yo');

console.log(list.set(0, 'Yo Bro'));

console.log('-- list:', list);
list.insert(0, 'Wassup');
console.log('--- list:', list);
list.insert(5, '💓');
console.log('--- list', list);
list.insert(1, '❤️');
console.log('--- list', list);

list.remove(7);
console.log('--- list', list);
list.remove(0);
console.log('--- list', list);
list.remove(1);
console.log('--- list', list);

배열(Array)와의 차이점

1. 메모리 할당 방식:
   • 배열: 연속된 메모리 공간에 요소들이 저장됩니다. 인덱스를 통해 빠르게 접근할 수 있습니다.
   • 링크드 리스트: 요소들이 불연속적인 메모리 공간에 저장됩니다. 각 요소는 포인터를 통해 연결됩니다.
2. 접근 시간:
   • 배열: 인덱스를 통해 O(1) 시간 복잡도로 임의의 요소에 접근할 수 있습니다.
   • 링크드 리스트: 특정 요소에 접근하려면 첫 번째 노드부터 순차적으로 탐색해야 하므로, 평균적으로 O(n) 시간 복잡도가 소요됩니다.
3. 삽입 및 삭제:
   • 배열: 특정 위치에 요소를 삽입하거나 삭제하려면 요소들을 이동해야 하므로, 평균적으로 O(n) 시간이 걸립니다.
   • 링크드 리스트: 특정 위치에 요소를 삽입하거나 삭제할 때 요소들을 이동할 필요가 없으므로, 삽입과 삭제는 O(1) 시간 복잡도로 수행됩니다. 단, 삽입 또는 삭제할 위치를 찾기 위해 O(n) 시간이 소요될 수 있습니다.
4. 메모리 사용:
   • 배열: 메모리를 효율적으로 사용하지만, 크기를 변경할 때는 새로운 메모리 할당이 필요할 수 있습니다.
   • 링크드 리스트: 각 요소마다 추가적인 포인터를 저장하기 위한 메모리가 필요하므로, 배열보다 메모리 사용량이 많을 수 있습니다.
5. 연결성:
   • 배열: 고정된 크기의 데이터 구조로, 크기를 변경하려면 새로운 배열을 할당하고 기존 요소들을 복사해야 합니다.
   • 링크드 리스트: 동적으로 크기를 변경할 수 있으며, 노드를 추가하거나 제거하는 것이 상대적으로 간단합니다.

결론

링크드 리스트와 배열은 각기 다른 장점과 단점을 가지고 있으며, 사용 목적에 따라 적절한 데이터 구조를 선택하는 것이 중요합니다. 배열은 빠른 접근 시간이 필요한 경우에 적합하고, 링크드 리스트는 빈번한 삽입과 삭제가 필요한 경우에 유리합니다.