JS의 체인 테이블 소개

개요

"체인 테이블은 질서정연한 데이터 집합입니다. 이 집합은 여러 개의 다른 노드를 포함합니다. 각 노드는 일정한 수량의 데이터와 다음 노드에 대한 인용을 포함합니다. 우리가 이 노드를 함께 놓을 때, 우리는 그것을 체인 테이블이라고 합니다. 이것은 실제로 연결된 노드 목록이기 때문입니다. 우리는 그것을 체인이라고 자주 부릅니다. 체인을 구성하는 노드 목록갑작스럽거나 무작위로 바뀌지 않는 주문서로서, 물론 우리가 그것을 바꾸고 싶지 않으면.각 체인 테이블에는 두 개의 특수 노드가 있다.머리와 꼬리.머리 노드는 항상 목록의 첫 번째 노드입니다.끝 노드는 항상 목록의 마지막 노드입니다.꼬리 노드는 항상 다른 노드에 대한 인용이 없기 때문에 식별할 수 있다."

노드에 포함될 수 있는 데이터는 우리가 원하는 모든 데이터 형식일 수 있다.문자열, 숫자, 배열, 객체, 모든 유형의 JS 값이 이러한 노드에 포함될 수 있습니다.노드의 다른 부분은 다음 노드에 대한 인용이다.
체인 시계를 사용하는 것도 유리하고 폐단도 있다.위에 있는 이 Quora forum 봐!
나는 체인표(그리고 대부분의 데이터 구조/알고리즘 문제)를 배우는 가장 좋은 방법은 직접 실천하는 것이라고 생각한다.가장 기본적인 체인 테이블을 만드는 것부터 시작하겠습니다.

const nodeOne = {
  data: "Hi"
}

const nodeTwo = {
  data: "Sofia"
}

nodeOne.next = nodeTwo

console.log(nodeOne) // => { data: 'Hi', next: { data: 'Sofia' } }

기본적으로 우리는 방금 자신의 링크 목록을 만들었습니다...나는 정말 너희들이 스스로 하도록 격려한다. 그것이 어떻게 일을 하는지 보자. 왜냐하면 우리는 이곳에서 좀 깊이 파고들 것이다.
앞에서 말한 바와 같이 체인표는 노드로 구성된다.이것은 우리가 폭발할 수 있는 일로 들린다.그러면 Node와 LinkedList 함수를 만듭니다.하지만, 내가 쓰기 전에...이 함수들이 어떤 내용을 포함할 수 있는지 생각해 보세요.우리는 하나의 노드에 대한 데이터와 다음 노드에 대한 인용이 있다는 것을 안다.우선, 우리는 체인 시계가 머리가 있다는 것을 안다.번영여기서부터 시작합시다.

function Node(data, next = null) {
  this.data = data,
  this.next = next
}

function LinkedList() {
  this.head = null
}

이제 체인 시계를 살짝 시험해 보고 조작을 해 봅시다.이곳에서 나는 원형 의뢰를 사용할 것이다.만약 당신이 이것이 무엇인지 확실하지 않다면, 나는 당신이 다른 시간에 클래스와 원형 계승here의 장단점과 차이를 깊이 이해하는 것을 강력히 건의하지만, 걱정하지 마세요...너는 여전히 따를 수 있다.
그리고 한마디 더 하고 싶은데 이 정도는 할 수 있는 방법이 많아요. 다른 방식으로 하면 왜 그런지 듣고 싶어요.
우리가 하고 싶은 첫 번째 일은 목록 앞에 노드를 추가하는 것이다.이 점에서, 나는 당신이 리플에서 따르고 있다고 가정합니다.
체인 테이블의 헤더를 새 노드로 설정하는 함수addToFront를 만듭시다!

LinkedList.prototype.addToFront = function(data) {
  this.head = new Node(data, this.head)
}

let list = new LinkedList()
let node = new Node(5)
list.head = node
list.addToFront(10)
console.log(list) // => LinkedList { head: Node { data: 10, next: Node { data: 5, next: null } } }

// You should continuously be testing in your repl like above ^^

지금, 아마도 우리는 체인 시계의 크기를 검사하고 싶을 것이다.우리는 목록의 모든 노드를 계산하기 위해size라는 함수를 만들 수 있습니다!

LinkedList.prototype.size = function() {
  let counter = 0
  let node  = this.head

  while (node) {
    counter++;
    node = node.next
  }
  return counter
}

주의해라, 우리는 여기에서 while 순환을 사용했다.이것은 매우 교묘한 기술로 많은 다른 문제에 모두 도움이 될 것이다.우리는 계수기와 노드 변수를 첫 번째 노드로 설정할 것이다.우리의 목록에 노드 (또는 노드 =null) 가 있을 때, 우리는 계수기를 추가하고, 동시에 우리의 노드 변수를 목록의 다음 노드로 초기화합니다.마지막으로, 우리는 계수기로 돌아왔다.
아마도 우리는 첫 번째와 마지막 노드를 검색하기 위해 다른 함수를 원할 것이다.따라서,retrieveFirst와retrieveLast 함수를 만들었습니다.공간을 절약하기 위해 첫 번째 노드를 검색하면 이것만 되돌려줍니다.머리, 그래서 우리는 쓰지 않겠지만, 너는 마땅히 써야 한다.그러나retrieveLast에 대해 우리는 크기 함수와 유사한 일을 해야 한다.

LinkedList.prototype.retrieveLast = function() {
  let node = this.head
  if (!node) {
    return null
  }

  while(node) {
    if (node.next === null) {
      return node
    }
      node = node.next
  }
}

우리가 해야 할 일은 목록의 마지막 노드를 되돌려주는 것이다...꼬리.단, 첫 번째 노드가 없으면null로 돌아갑니다.만약 있다면, 우리는while 순환에 들어갑니다. 이번 한 번만 다음 노드가 거기에 있는지 확인하십시오.만약 다음 노드에 대한 인용이 없다면, 우리는 우리가 끝부분을 명중시키고 그것을 되돌려 주었다는 것을 알 수 있다.
아마도 우리는 전체 체인 시계를 함께 삭제하거나 적어도 그것을 제거하고 싶을 것이다.erase라는 방법을 만듭니다.이것은 실제로 보기보다 훨씬 쉽다.우리는 체인 시계가 머리로 시작하고 머리가 다음 노드를 인용하는 것을 알고 있다.우리가 괴물의 머리를 베면 어떡해?!만약 체인 시계가 초기 참고점이 없다면, 그것은 사라질 것이다.해봐.

LinkedList.prototype.erase = function() {
  return this.head = null
}

마찬가지로, 만약 우리가 첫 번째 노드/헤더만 삭제하고 싶다면, 어떻게 해야 합니까?
우선, 삭제할 수 있는 것이 있는지 확인하고 싶습니다.그리고 우리는 첫 번째 노드를 다음 노드와 같게 할 수 있다!

LinkedList.prototype.removeFirst = function() {
  if (!this.head) {
    return;
  }
  return this.head = this.head.next
}

우리 지금 뒹굴고 있어!좀 어려운 게 몇 개 있는데 어때요?
마지막 노드를 삭제하고 새 꼬리 노드를 만듭니다.마지막 노드를 삭제하려면 우선 가장자리 상황을 처리해야 한다.1) 우리는 하나의 노드를 확보해야 한다. 2) 우리는 하나의 노드만 있으면 null만 되돌려준다.그 후에 몇 가지 다른 방법으로 이 점을 할 수 있지만, 나는 너를 데리고 가장 의미 있는 나를 통과할 것이다.

LinkedList.prototype.deleteLast = function() {
  if (!this.head) {
    return;
  }

  if (!this.head.next) {
    return this.head = null
  }

  let previous = this.head
  while(previous) {
    let node = previous.next
    if (!node.next) {
      return previous.next = null
    }
    previous = previous.next
  }
}

검사 후, 우리는 두 개의 변수를 설정한다.머리에서 시작하는 이전 노드와 항상 이전 노드 앞에 있는 노드.우리는 하나의 노드가 있을 때 우리의 순환을 계속하고 싶다. 다음 노드에 대한 인용이null이면 우리는 우리가 마지막 노드에 도달했다는 것을 알 수 있다. 우리는 이 노드를 삭제하려고 할 것이다.
마지막으로 마지막 노드를 삭제하려면 마지막 노드에 추가할 수 있습니다.마지막 주름 보여줄게.위에서 RetrieveLast () 라는 원형 의뢰 방법을 만들었습니다.우리 스스로 좀 가볍게 하고, 그것을 사용하여 마지막으로 추가할 노드를 찾자.
그 밖에 우리는 여기에 새로운 노드를 만들어야 한다. 왜냐하면 우리는 노드를 추가하고 있기 때문에, 우리의 함수는 데이터를 수신할 것이다.그리고 retrieveLast () 함수를 변수로 설정합니다.마지막으로, 우리는 체인 시계가 비어 있지 않다는 것을 확보해야 한다.만약 그렇다면, 우리는 새 노드를 머리로 설정하고, 그렇지 않다면, 우리는 그것을 마지막으로 설정한다.다음

LinkedList.prototype.insertLast = function(data) {
  const newNode = new Node(data)
  const last = this.retrieveLast()

  if (last) {
    last.next = newNode
  } else {
    this.head = newNode
  }
}

결론

관심 가져주셔서 감사합니다!나는 이것이 너에게 도움이 되기를 바란다. 또한 네가 초보자를 위해 체인 시계에 관한 지식을 좀 배웠으면 좋겠다.

공구서류

이거 봐, 대박이다course!