JavaScript 데이터 구조: 이중 연결 목록: 데이터를 끝까지 푸시/추가

소개

, 우리는 이중 연결 목록을 설정하는 방법을 배웠습니다.

오늘은 이중 연결 목록의 끝에 새 노드를 푸시하는 방법을 배웁니다.

스타터 코드

.

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

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

생각

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

목록이 비어 있는 경우:

새 노드 생성

새 노드는 헤드와 테일이 되어야 합니다

.

목록의 길이를 1 늘립니다

.

새 노드 반환

나머지 모든 경우:

새 노드 생성

현재 꼬리는 새 노드

의 앞(=다음)을 가리켜야 합니다.

새 노드는 현재 테일

을 다시(= prev) 가리켜야 합니다.

새 노드가 새 꼬리가 되어야 합니다

.

목록의 길이를 1 늘립니다

.

새 노드 반환

예: 빈 목록

현재 목록: 비어 있음(헤드 및 테일 없음)

원하는 리스트:A(헤드&테일)

예 2: 1개의 노드가 있는 목록

current List:A(헤드&테일)

원하는 목록: A(머리) <===> B(꼬리)

단계:

current List:A(헤드&테일)

원하는 목록: A(머리) <===> B(꼬리)

the current tail should point forward (= next) to the new node : A(머리와 꼬리) => B

the new node should point back (= prev) to the current tail : A (머리 & 꼬리) <===> B

the new node should become the new tail : A(머리) <===> B(꼬리)

=> 마지막 단계 이후의 목록은 원하는 목록과 같습니다.

구현

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

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

  push(value) {
    // create a new node
    const newNode = new Node(value);

    // if the list is empty,the new node should become the head and the tail
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // the current tail should point forward (= next) to the new node
      this.tail.next = newNode;

      // the new node should point back (= prev) to the current tail
      newNode.prev = this.tail;

      // the new node should become the new tail
      this.tail = newNode;
    }

    // increase length by 1
    this.length += 1;

    // return new node
    return newNode;
  }
}

결과

이중 연결 목록push의 방법과 그 결과를 사용하는 방법을 살펴보겠습니다.

// empty list
const newDLL = new DoublyLinkedList();
console.log(newDLL);
// DoublyLinkedList { length: 0, head: null, tail: null }

// push first new node
console.log(newDLL.push("new node 1"));
//  Node { value: 'new node 1', prev: null, next: null }

console.log(newDLL);
//  DoublyLinkedList {
//    length: 1,
//    head: Node { value: 'new node 1', prev: null, next: null },
//    tail: Node { value: 'new node 1', prev: null, next: null }
//  }

// push second new node
console.log(newDLL.push("new node 2"));
// <ref *1> Node {
//   value: 'new node 2',
//   prev: Node { value: 'new node 1', prev: null, next: [Circular *1] },
//   next: null
// }

console.log(newDLL);
// DoublyLinkedList {
//   length: 2,
//   head: <ref *1> Node {
//     value: 'new node 1',
//     prev: null,
//     next: Node { value: 'new node 2', prev: [Circular *1], next: null }
//   },
//   tail: <ref *2> Node {
//     value: 'new node 2',
//     prev: <ref *1> Node {
//       value: 'new node 1',
//       prev: null,
//       next: [Circular *2]
//     },
//     next: null
//   }
// }

다음 부분

이중 연결 목록에 대한 다음 방법을 구현할 것입니다: pop/끝에서 노드 제거.

알림을 받고 싶다면 subscribe !

작업

결과에서 새로운 내용을 발견했습니까?

무슨 뜻인가요?