TypeScript의 데이터 구조 - 연결된 목록

연결 리스트는 선형 순서로 배열된 개체를 보유하는 데이터 구조이며, 이 순서는 각 노드의 포인터에 의해 결정됩니다.
배열과 달리 연결된 목록은 특정 인덱스에 대한 지속적인 액세스를 제공하지 않습니다. 요소를 찾기 위해 목록을 반복해야 합니다. 반면에 목록의 시작 부분에서 항목을 추가하거나 제거할 수 있습니다. 일정한 시간에.
연결 목록은 스택, 대기열 및 그래프와 같은 다른 데이터 구조를 구현하는 데 사용할 수 있습니다.

몇 가지 유형의 연결 목록이 있습니다.

단일 연결 목록 - 각 노드에는 다음 노드에 대한 포인터만 있습니다.

이중 연결 리스트 - 각 노드에는 이전 노드와 다음 노드 모두에 대한 포인터가 있습니다.

원형 연결 목록 - 마지막 노드가 첫 번째 요소를 가리킵니다.

대표

헤드 - 첫 번째 노드

꼬리 - 마지막 노드

기본 조작

삽입 - 목록의 아무 곳에나 새 요소를 삽입할 수 있습니다. 포인터만 주의하면 됩니다. 처음에 요소를 추가하는 경우 새 노드는 이전 헤드 노드를 가리킵니다. 꼬리에 추가하는 경우 이전 꼬리 노드가 새 노드를 가리킵니다. 이제 노드 사이에 삽입하는 경우 이전 노드는 다음 노드를 가리키는 새 노드를 가리켜야 합니다.

삭제 - 유사한 삽입 논리를 따르십시오. 목록 중간에서 노드를 제거하려면 대상의 이전 노드가 대상의 다음 노드를 가리키도록 해야 합니다. 이중 연결 목록에서는 이전 포인터도 관리해야 합니다.

트래버스 - 각 노드에는 다음을 가리키는 지점이 있으므로 노드 헤드에서 시작하여 마지막 노드까지 포인터를 따라갑니다. 이 노드는 어떤 노드도 가리키지 않습니다(비원형 연결 목록에서).

n = list.head

while n != null
    n = n.next

다음은 단일 연결 목록의 구현입니다.

class Node<T> {
  data: T;
  next: Node<T> | null = null;

  constructor(data: T) {
    this.data = data;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;
  comparator: (a: T, b: T) => boolean;

  constructor(comparator: (a: T, b: T) => boolean) {
    this.comparator = comparator;
  }

  append(data: T): void {
    if (!this.head) {
      this.head = new Node(data);
    } else {
      let current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = new Node(data);
    }
  }

   delete(data: T): void {
    if (!this.head) return;

    // Check if the head node is the node to be removed
    if (this.comparator(this.head.data, data)) {
      this.head = this.head.next;
      return;
    }

    let current = this.head.next;
    let previous = this.head;

    /**
     * Search for the node to be removed and keep track of its previous node
     *
     * If it were a double linked list, we could simply search the node
     * and it would have a pointer to the previous node
     **/
    while (current) {
      if (this.comparator(current.data, data)) {
        current = null;
      } else {
        previous = current;
        current = current.next;
      }
    }

    /**
     * set previous.next to the target.next, if the node target is not found,
     * the 'previous' will point to the last node,
     * since the last node hasn't next, nothing will happen
     **/
    previous.next = previous.next ? previous.next.next : null;
  }

  search(data: T): Node<T> | null {
    let current = this.head;
    while (current) {
      if (this.comparator(current.data, data)) {
        return current;
      }
      current = current.next;
    }
    return null;
  }

  traverse() {
    let current = this.head;
    while (current != null) {
      console.log(current.data);
      current = current.next;
    }
  }
}

러너 기술

이 기술은 두 개의 포인터(느린 포인터보다 n 노드만큼 앞서 있는 느린 포인터와 빠른 포인터)가 있는 연결 목록을 통해 반복하는 것으로 구성됩니다.



이는 연결 목록의 크기를 모를 때 순환 감지 또는 연결 목록의 중간 노드 찾기와 같은 연결 목록의 일부 문제를 해결하는 데 유용합니다.

/** Finding the middle node of a linked list **/

let slow: LinkedListNode<number> | null | undefined = linkedList.head;
let fast: LinkedListNode<number> | null | undefined = linkedList.head?.next;

/**
 * The "fast" will move twice as fast as the "slow" one,
 * so at the moment the "fast" reaches the end of the list,
 * the "slow" will be in the middle of the list
 **/

while (fast) {
  slow = slow?.next;
  fast = fast?.next?.next;
}

console.log(slow);