무엇이 체인 시계입니까?

단일 체인 테이블은 데이터 구조로 일련의 노드를 나타내는데 그 중에서 각 노드는 목록의 다음 노드를 가리킨다.비교해 보면, 쌍사슬표의 노드는 그것의 앞과 뒤의 원소를 가리킨다.
그룹과 달리, 체인 테이블은 목록에 있는 특정한 인덱스에 대한 고정 시간 접근을 제공하지 않습니다.따라서 목록의 세 번째 요소가 필요하다면 첫 번째와 두 번째 노드를 교체해야만 도착할 수 있다.
체인 테이블의 장점 중 하나는 고정된 시간 안에 목록의 시작과 끝에서 항목을 추가하고 삭제할 수 있다는 것이다.
이것들은 모두 기술 면접에서 의심받는 유행 데이터 구조이기 때문에 우리가 직접 삽입할 수 있다.
단일 체인 시계는 후진 선출 또는 선진 선출이 될 수 있다.목록이 후진 선출 방법을 사용하면 노드가 같은 끝에 추가되고 같은 쪽에서 삭제됩니다.FIFO를 사용하면 노드가 한쪽 끝에 추가되고 다른 쪽에서 제거됩니다.
이 밖에 체인 시계를 정렬할 수 있다.이것은 모든 노드가 목록에 추가될 때 다른 노드에 비해 적당한 위치에 배치된다는 것을 의미한다.

노트

체인 테이블은 일련의 노드일 뿐이니 노드의 대상부터 시작합시다.

노드에는 다음과 같은 두 가지 정보가 있습니다.

목록의 다음 항목에 대한 지침이나 인용

노드 값

우리의 노드에 대해 우리는 함수를 만들기만 하면 된다. 이 함수는 하나의 값을 받아들이고 상기 두 개의 값을 포함하는 대상을 되돌려준다. 바로 다음 노드를 가리키는 바늘과 노드의 값이다.주의, 우리는 value만 성명할 수 있다value: value.변수의 이름이 같기 때문이다.객체 속성 속기here에 대한 자세한 내용을 확인할 수 있습니다.

function Node(value) {
  return {
    value,
    next: null
  }
}

NodeList

이제 노드 목록류를 깊이 연구합시다.이것은 단지 노드 목록일 뿐이다.

노드 목록에는

push(value): 값을 체인 테이블

의 끝으로 밀어넣기

pop(): 팝업 목록의 마지막 값

get(index): 주어진 색인에 있는 항목을 되돌려줍니다

delete(index): 주어진 인덱스에서 항목 삭제

isEmpty(): 목록이 비어 있는지 여부를 표시하는 부울 값을 되돌려줍니다

printList(): 체인 테이블의 고유한 방법이 아니라 우리의 목록을 출력할 수 있습니다.이것은 주로 디버깅 목적

에 사용됩니다.

건조사

JavaScript 클래스 구문을 사용하지만 닫기를 사용하여 링크 목록을 만들 수도 있습니다.구조 함수를 설정합니다.
다음 세 가지 정보가 필요합니다.

head: 목록

의 시작 노드에 대한 인용

tail: 목록

의 끝 노드에 대한 인용

길이: 목록의 노드 수

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

비어 있음

isEmpty() 방법은 도움말 함수입니다. 목록이 비어 있으면true를 되돌려줍니다.

isEmpty() {
  return this.length === 0;
}

인쇄 목록

이 유틸리티 방법은 목록의 노드를 인쇄합니다.이것은 디버깅 목적에만 사용됩니다.

printList () {
  const nodes = [];
  let current = this.head;
  while (current) {
    nodes.push(current.value);
    current = current.next;
  }
  return nodes.join(' -> ');
}

밀다

우리의push 방법은 새 노드를 추가하기 전에 목록이 비어 있는지 확인해야 합니다.우리는 목록이 비어 있는지 어떻게 알 수 있습니까?두 가지 방법:

우리isEmpty() 방법은true(목록의 길이는 0)

로 되돌아갑니다

머리 포인터가 비어있음

이 예에서, 우리는 이 두 가지 해결 방안이 모두 정상적으로 작동할 수 있지만, 헤드가null인지 검사할 것이다.
목록에 항목이 없으면, 새 노드를 가리키는 헤더와 꼬리를 간단하게 설정하고, 목록의 길이를 업데이트할 수 있습니다.

if (this.head === null) {
  this.head = node;
  this.tail = node;
  this.length++;
  return node;
}

목록이 비어 있지 않으면 다음을 수행해야 합니다.

tail.next를 새 노드로 설정

tail를 새 노드로 설정

목록 길이 증가

다음은 완전한 푸시 방법입니다.

push(value) {
  const node = Node(value);
  // The list is empty
  if (this.head === null) {
    this.head = node;
    this.tail = node;
    this.length++;
    return node;
  }
  this.tail.next = node;
  this.tail = node;
  this.length++;
}

팝송 팝송

목록의 마지막 항목을 삭제하기 전에 pop 방법은 다음 두 가지를 검사해야 합니다.

목록이 비어 있는지 확인

목록에 하나만 있는지 확인

우리는 isEmpty 방법으로 목록에 노드가 포함되어 있는지 검사할 수 있다.

if (this.isEmpty()) {
  return null;
}

우리는 목록에 단지 하나의 노드만 있는지 어떻게 알 수 있습니까?머리와 꼬리가 같은 노드를 가리키면그런데 이 상황에서 저희가 뭘 해야 될까요?유일한 노드를 삭제하는 것은 우리가 실제로 목록을 리셋하고 있다는 것을 의미한다.

if (this.head === this.tail) {
  this.head = null;
  this.tail = null;
  this.length--;
  return nodeToRemove;
}

목록에 여러 요소가 있는 경우 다음을 수행할 수 있습니다.

while there are nodes in the list
  if the next node in the list is the tail
    update tail to point to the current node
    set the current node to point to null
    decrement the length of the list
    return the previous tail element

그것은 이렇게 보인다.

let currentNode = this.head;
let secondToLastNode;

// Start at the front and iterate until
// we find the second to last node
while (currentNode) {
  if (currentNode.next === this.tail) {
    // Move the pointer for the second to last node
    secondToLastNode = currentNode;
    break;
  }
  currentNode = currentNode.next;
}
// Pop off that node
secondToLastNode.next = null;
// Move the tail to the second to last node
this.tail = secondToLastNode;
this.length--;

// Initialized to this.tail
return nodeToRemove;

만약 네가 시각적으로 어려움이 있다면, 우리 한번 보자.
6-10 줄: 목록의 다음 노드가 마지막 항목이라면 현재 항목은 새로운 '꼬리' 이기 때문에 인용을 저장해야 합니다.

if (currentNode.next === this.tail) {
  secondToLastNode = currentNode;
}

list
15행: 업데이트 secondToLastNode는null을 가리킵니다.팝업 목록에서 마지막 요소의 동작입니다.

secondToLastNode.next = null;

16행: tail를 지향secondToLastNode으로 업데이트합니다.

this.tail = secondToLastNode;

17줄: 목록의 길이를 줄여라. 우리가 노드를 방금 삭제했기 때문이다.
18행: 방금 팝업한 노드를 되돌려줍니다.
다음은 우리의 완전한 유행 방법이다.

pop() {
  if (this.isEmpty()) {
    return null;
  }
  const nodeToRemove = this.tail;
  // There's only one node!
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
    this.length--;
    return nodeToRemove;
  }

  let currentNode = this.head;
  let secondToLastNode;

  // Start at the front and iterate until
  // we find the second to last node
  while (currentNode) {
    if (currentNode.next === this.tail) {
      // Move the pointer for the second to last node
      secondToLastNode = currentNode;
      break;
    }
    currentNode = currentNode.next;
  }
  // Pop off that node
  secondToLastNode.next = null;
  // Move the tail to the second to last node
  this.tail = secondToLastNode;
  this.length--;

  // Initialized to this.tail
  return nodeToRemove;
}

얻다

우리의 get 방법은 반드시 세 가지 상황을 검사해야 한다.

요청한 인덱스가 목록

의 범위를 넘어섰습니다.

목록이 비어 있음

첫 번째 요소가 필요합니다

목록에 요청한 인덱스가 존재하지 않으면null로 되돌아옵니다.

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

목록이 비어 있으면,null로 돌아갑니다.너는 이if문장들을 조합할 수 있지만, 명확하게 유지하기 위해서 나는 그것들을 분리했다.

if (this.isEmpty()) {
  return null;
}

만약 우리가 첫 번째 원소를 요구한다면, 머리로 돌아가라.

// We're at the head!
if (index === 0 )  {
  return this.head;
}

그렇지 않으면, 색인을 찾을 때까지 목록을 하나하나 훑어보기만 하면 된다.

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;

다음은 전체 get(index) 방법입니다.

get(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

if (this.isEmpty()) {
  return null;
}

// We're at the head!
if (index === 0 )  {
  return this.head;
}

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;
}

삭제

우리의 삭제 방법은 세 가지 특수한 용례를 고려해야 한다.

삭제할 인덱스가 목록

의 범위를 넘어섰습니다.

목록이 비어 있음

제목을 삭제하고 싶습니다

삭제할 인덱스가 목록에 존재하지 않으면,null을 되돌려줍니다.

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

목록이 비어 있으면,null로 돌아갑니다.색인이 목록의 경계 밖에 있는지 확인하기 위해 이 논리와 논리를 결합할 수 있지만, 명확하게 보기 위해서 분리합니다.

if (this.isEmpty()) {
  return null;
}

헤더를 삭제하려면 head를 목록의 다음 값으로 설정하고 길이를 줄인 다음 방금 삭제한 값을 되돌려줍니다.

if (index === 0) {
  const nodeToDelete = this.head;
  this.head = this.head.next;
  this.length--;
  return nodeToDelete;
}

이러한 부울 값이 모두 사실이 아니라면 노드를 삭제하는 논리는 다음과 같습니다.

while the iterator isn't the index we're looking for
  increase the iterator
  move the previous and current pointers up by one
save the current value as the node to be deleted
update the previous node's pointer to point to the next node
if the next value is null
  set tail to the new last node
decrement list length
return the deleted node

시각화에 도움이 필요하면 Pop 섹션의 차트를 참조하십시오.
delete 방법과 pop 방법의 차이는 pop 방법이 항상 목록의 마지막 항목을 삭제하는 데 있다.이에 비해 delete 방법은 0과 목록 길이 사이의 인덱스를 삭제할 수 있습니다.
다음은 전체 삭제 방법입니다.

delete(index) {
   // Index is outside the bounds of the list
  if (index < 0 || index > this.length - 1) {
    return null;
  }

  if (this.isEmpty()) {
    return null;
  }

  if (index === 0) {
    const nodeToDelete = this.head;
    this.head = this.head.next;
    this.length--;
    return nodeToDelete;
  }

  let current = this.head;
  let previous;
  let iterator = 0;

  while (iterator < index) {
    iterator++;
    previous = current;
    current = current.next;
  }
  const nodeToDelete = current;
  // Re-direct pointer to skip the element we're deleting
  previous.next = current.next;

  // We're at the end
  if(previous.next === null) {
    this.tail = previous;
  }

  this.length--;

  return nodeToDelete;
}

코드를 가지고 놀고 싶으면 제 것을 마음대로 사용하세요. CodePen