ES6의 연결 목록 소개

나는 지난 한 달 동안 leetcode 및 codewars과 같은 사이트에서 코딩 과제를 해결하는 데 보냈으며 연결 목록과 관련된 문제가 꽤 인기가 있다는 것을 알게 되었습니다. 실제로 leetcode의 가장 인기 있는 인터뷰 질문 상위 25개 중 6개는 어떤 형태로든 링크 목록을 포함합니다. 이 게시물에서는 단일 및 이중 연결 목록의 기본 사항을 다루고 Javascript ES6에서 인기 있는Class 키워드를 활용하는 간단한 구현을 살펴봅니다.

연결된 목록이란 무엇입니까?

연결된 목록은 노드라고 하는 각 데이터 조각이 메모리에서 다른 노드의 위치에 대한 참조도 포함하는 선형 데이터 구조입니다. 일반 영어에서 목록의 각 요소는 다음 요소의 위치를 ​​알고 있습니다. 연결 목록은 생각보다 일반적입니다. 음악 앱은 노래 재생 목록에 연결 목록을 통합하고, ticketmaster과 같은 사이트는 이를 사용하여 고객의 가상 회선을 추적합니다("구매를 완료하는 데 5분 남았습니다"라는 메시지를 본 적이 있음). ?).

링크 목록은 단일 연결 목록과 이중 연결 목록의 두 가지 형태로 제공됩니다. 각각의 시각적 및 코드 예제를 살펴보겠습니다.

단일 연결 목록

목록의 시작 부분을 헤드라고 합니다. 각 후속 노드는 다음 위치에 대한 참조만 유지합니다. 목록 끝에 있는 노드를 꼬리라고 합니다. 다른 노드에 대한 참조는 포함하지 않습니다.

ES6에서는 class 키워드를 사용하여 기본 단일 연결 목록을 구성할 수 있습니다.

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

head, tail 및 선택적 길이 속성이 있는 javascript 객체를 생성하는 실행const SLL = new SinglyLinkedList()을 통해 목록을 생성합니다. 노드를 생성하기 위해 다른 생성자 함수를 작성하는 것이 일반적입니다.

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

연결된 목록에 값을 추가하기 위해 SinglyLinkedList 클래스에 인스턴스 메서드를 추가할 수 있습니다. 목록의 시작 부분에 노드를 추가하는 unshift 메서드를 만들어 보겠습니다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    const node = new Node(val)
    //if no head
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }
}

목록의 시작 부분에 노드를 추가하려면 먼저 new Node() 를 호출하고 값을 전달하여 노드를 만들어야 합니다. 이렇게 하면 Node 클래스에서 상속되는 객체가 생성됩니다. 그런 다음 생성되는 노드가 목록의 첫 번째 노드인 경우 헤드와 테일을 새 노드로 설정해야 합니다. 첫 번째 노드가 아닌 경우 새 노드의 다음 속성을 이전 헤드의 속성으로 지정하여 헤드만 업데이트하면 됩니다. 마지막으로 count 속성을 증가시켜 목록의 총 노드 수를 추적하고 선택적으로 업데이트 목록을 반환합니다( this 로 표시됨). 자바스크립트 배열과 달리 연결된 목록의 앞에 추가하는 데는 일정한 (O(1)) 시간이 걸리므로 줄 뒤에 추가하는 것이 바람직할 때 연결 목록을 사용하는 주요 이점 중 하나를 보여줍니다. 대조적으로 배열은 선형(O(n)) 시간으로 이동하지 않습니다.

이중 연결 목록

헤드와 테일 사이에 있는 각 노드가 바로 전후 위치의 노드를 추적하는 방법에 주목하십시오. 이전의 단일 연결 목록 코드에서 몇 가지만 수정하면 됩니다.

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    const node = new Node(val)
    //if no head
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.head.previous = node;
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }
}
//Node class constructor
class Node {
  constructor(val) {
    this.val = val;
    this.previous = null;
    this.next = null;
  }
}

이중 연결 목록에서 이동하지 않을 때 연결 목록의 헤드 속성을 새 노드로 업데이트하기 전에 이전 헤드의 속성previous이 새 노드를 가리키도록 설정해야 합니다. 이것은 약간 더 많은 코드처럼 보일 수 있지만 이중 연결 목록은 앞과 뒤로 모두 순회할 수 있지만 단일 연결 목록은 헤드에서만 순회할 수 있습니다. 앞으로 및 뒤로 화살표를 사용하여 브라우저에서 앞뒤로 탐색할 때 매일 이중 연결 목록 유형 구조를 사용합니다.

합산

이 게시물은 실제로 이러한 데이터 구조가 어떻게 생겼고 어떻게 작동하는지에 대한 표면을 긁는 것입니다. 더 자세히 알아보려면 다른 많은 방법에 대한 visualgo's 애니메이션을 확인하는 것이 좋습니다. 몇 가지 인터뷰 질문을 할 준비가 되면 leetcode's 상위 100개의 인터뷰 질문에서 다음을 시도해 보십시오.
1. Add two numbers
2. Remove Nth Node From End of List
3. Merge two sorted lists
4. Merge k sorted lists
5. Swap nodes in pairs
6. Reverse nodes in k group