JavaScript 데이터 구조: 단일 연결 목록: 푸시

소개

Last time , 우리는 단일 연결 목록을 설정했습니다.

오늘 우리는 목록에 무언가를 푸시하는 방법을 배웁니다. Push는 add something to the end를 의미합니다.

지난 시간 요약

클래스를 만들었습니다 Node

클래스를 만들었습니다 Singly Linked List

우리는 Node 클래스

의 인스턴스를 만드는 방법을 배웠습니다.

우리는 Singly Linked List 클래스

의 인스턴스를 만드는 방법을 배웠습니다.

현재 코드

// name of the class
class Node {
  // the constructor runs when using the class with `new` (see later)
  constructor(value) {
    // set this nodes value property to the instantiation value
    this.value = value;
    // set this nodes next property to `null`
    this.next = null;
  }
}

// name of the class
class SinglyLinkedList {
  // the constructor runs when using the class with `new`
  constructor() {
    // set this lists length property to `0`
    this.length = 0;
    // set this lists head property to `null`
    this.head = null;
    // set this lists tail property to `null`
    this.tail = null;
  }
}

생각

먼저 제약 조건과 가능성에 대해 생각해야 합니다.

Singly Linked List에 이미 하나 이상의 다른 노드가 있는 경우:

입력 값으로 새 노드를 만듭니다.

현재 꼬리next 속성이 새 노드를 가리키도록 합니다(따라서 새 노드가 현재 꼬리 뒤에 옵니다).

단일 연결 목록tail을 새 노드

로 설정합니다.

단일 연결 목록의 길이를 1만큼 늘림

새 노드를 반환합니다(추가한 내용을 알 수 있도록).

현재 단일 연결 목록에 다른 노드가 없는 경우(따라서 현재 비어 있음):

입력 값으로 새 노드를 만듭니다.

단일 연결 목록head을 새 노드

로 설정합니다.

단일 연결 목록tail을 새 노드

로 설정합니다.

단일 연결 목록의 길이를 1만큼 늘림

새 노드를 반환합니다(추가한 내용을 알 수 있도록).

차이점들?

Singly Linked List가 비어 있으면 헤드가 필요합니다(새로운 노드가 유일한 노드이기 때문에).

단일 연결 목록에 이미 하나 이상의 노드가 있는 경우 마지막 노드는 새 노드를 가리켜야 하며 이 새 마지막 노드는 새 꼬리입니다

.

예시:

노드 0개: 이전: null(머리 및 꼬리) => 이후: A(머리 및 꼬리)

1노드: 전: A(머리&꼬리) => 후: A(머리) -> B(꼬리)

2노드: 전: A(머리) -> B(꼬리) => 후: A(머리) -> B -> C(꼬리)

n 노드: 이전: A(머리) -> ... -> n(꼬리) => 이후: A(머리) -> ... -> n -> n+1(꼬리)

따라서 A 는 항상 헤드를 유지하며 0 노드가 있는 경우에만 A 를 새 head 로 설정해야 합니다.
다른 모든 상황에서는 현재tail가 새 노드를 가리키도록 하고 새 노드를 새 노드tail로 만들어야 합니다.

구현(긴 버전, DRY 없음)

섹션의 댓글Thoughts

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

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

  push(value) {
    /*
     * 1. If there is already at least one other node in the Singly Linked List
     */
    if (this.length > 0) {
      // create a new node with an input value
      const newNode = new Node(value);
      // point the current tails `next` property to the new node
      this.tail.next = newNode;
      // set the Singly Linked List's `tail` to the new node
      this.tail = newNode;
      // increase the Singly Linked List's length by 1
      this.length += 1;
      // return the new node
      return newNode;
    } else {
      /*
       * 2. If there is currently NO other node in the Singly Linked List (so it is currently empty):
       */
      // create a new node with an input value
      const newNode = new Node(value);
      // set the Singly Linked List's `head` to the new node
      this.head = newNode;
      // set the Singly Linked List's `tail` to the new node
      this.tail = newNode;
      // increase the Singly Linked List's length by 1
      this.length += 1;
      // return the new node (so that we knew what we added)
      return newNode;
    }
  }
}

구현(짧은 버전, DRY)

대부분의 논리가 동일하기 때문에 중복 코드가 많습니다.

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

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

  push(value) {
    const newNode = new Node(value);
    if (this.length > 0) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.length += 1;
    return newNode;
  }
}

결과

Singly Linked Listpush 방법과 그 결과를 살펴보자.

const newSLL = new SinglyLinkedList();
console.log(newSLL);
/*
 * SinglyLinkedList {
 *   length: 0,
 *   head: null,
 *   tail: null
 * }
 */

newSLL.push("A");
console.log(newSLL);
/*
 * SinglyLinkedList {
 *   length: 1,
 *   head: Node { value: 'A', next: null },
 *   tail: Node { value: 'A', next: null }
 * }
 */

newSLL.push("B");
console.log(newSLL);
/*
 * SinglyLinkedList {
 *   length: 2,
 *   head: Node { value: 'A', next: Node { value: 'B', next: null } },
 *   tail: Node { value: 'B', next: null }
 * }
 */

다음 부분

Singly Linked List의 끝에서 노드를 제거하는 방법을 구현합니다. 알림을 원하시면 subscribe :)