JS(Linked-list)의 데이터 구조에 대한 심층적인 이해

관련 추천: "javascript 비디오 튜토리얼"

JS는 내장된 연결 목록을 제공하지 않기 때문에 JS 초보자의 경우 연결 목록을 이해하는 것이 어려울 수 있습니다. JS와 같은 고급 언어에서는 이 데이터 구조를 처음부터 구현해야 하는데, 이 데이터 구조가 어떻게 작동하는지 익숙하지 않으면 구현 부분이 더 어려워지죠?

이 기사에서는 데이터베이스에 연결 목록을 저장하는 방법, 연결 목록 추가 및 삭제, 검색 및 연결 목록 역전과 같은 작업을 구현하는 방법에 대해 설명합니다. 연결리스트를 구현하기 전에 배열이나 객체에 비해 연결리스트의 장점이 무엇인지 알아야 합니다.

우리는 배열의 요소가 인덱스 번호와 순서에 따라 데이터베이스에 저장된다는 것을 알고 있습니다.

배열로 작업하는 동안 시작 부분이나 특정 인덱스에 요소를 추가/제거하는 등의 작업은 성능이 떨어질 수 있습니다. 문제. 다른 모든 요소의 인덱스를 이동해야 하기 때문에 작업량이 적습니다. 그 이유는 배열의 번호가 매겨진 인덱스 특성 때문입니다.

객체를 사용하면 위의 문제를 해결할 수 있습니다. 객체에서 요소 저장 위치는 무작위이므로 시작 부분이나 특정 인덱스에서 요소를 추가/제거하는 등의 작업을 수행할 때 요소의 인덱스를 이동할 필요가 없습니다.

객체에서 요소를 추가하고 제거하는 것은 빠르지만 위 이미지에서 볼 수 있듯이 객체의 요소가 임의의 위치에 저장되기 때문에 객체를 반복할 때 최선의 선택은 아닙니다. 따라서 반복 작업에는 시간이 오래 걸릴 수 있습니다. linked list가 나오는 이유가 바로 이것이다.

그럼 연결리스트란 무엇인가요?

이름 자체에서 어떤 면에서는 연결리스트라는 것을 알 수 있습니다. 그렇다면 어떻게 연결되어 있으며 목록에는 무엇이 포함되어 있습니까?

연결된 목록은 데이터와 포인터라는 두 가지 속성을 가진 노드로 구성됩니다.

노드 내의 포인터는 목록의 다음 노드를 가리킵니다. 연결된 목록의 첫 번째 노드를 head라고 합니다. 더 나은 이해를 위해 연결 목록을 설명하는 다이어그램을 살펴보겠습니다. head。 为了更好地理解，让我们看一下描述链表图示：

从上图可以看出，每个节点都有两个属性，data和pointer。 指针指向列表中的下一个节点，最后一个节点的指针指向null，上图是一个单链表 ?。

链表和对象时有很大的不同。 在链表中，每个节点都通过指针(pointer)连接到下一个节点。 因此，我们在链表的每个节点之间都有连接，而在对象中，键值对是随机存储的，彼此之间没有连接。

接着，我们实现一个存储整数的链表。 由于 JS 不提供内置的链表支持，因此我们将使用对象和类来实现链表 ?

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

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

  prepend (value) {

  }

  insert (value, index) {

  }

  lookup (index) {

  }

  remove (index) {

  }

  reverse () {
    
  }
}

在上面的代码中，我们创建了两个类，一个用于来链表本身，一个是节点本身。 如我们所讨论的，每个节点将具有两个属性，一个值和一个指针(对应 next 字段)。

LinkedList类包含三个属性，head(初始值为null)，用于存储链表的最后一个节点的tail(也指向null)和用于保存链表长度的length属性。接着，我们来实现里面的方法 ?。

append (按顺序添加值)

这个函数将一个节点添加到链表的末尾。为了实现这个函数，我们需要理解它需要执行的一些操作：

从上图中，我们可以通过以下方式实现append函数：

  append (value) {
    const newNode = new Node(value)
    if (!this.head) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length++
  }

简单的对 append 方法解释一下 ?：

const linkedList1 = new LinkedList()
linkedList1.append(2)

检查head是否指向null，此时的head指向null，因此我们创建一个新对象，并将新对象分配给head和tail:

let node = new Node(2)
this.head = newNode
this.tail = newNode

现在，head 和 tail 都指向同一个对象，这一点很重要，要记住。

接着，我们再向链表添加两个值：

linkedList1.append(3)
linkedList1.append(4)

现在，head 不指向null，所以我们进入append函数的else

🎜🎜🎜🎜위 그림에서 볼 수 있듯이 각 노드에는 data와 pointer라는 두 가지 속성이 있습니다. . 포인터는 목록의 다음 노드를 가리키고, 마지막 노드의 포인터는 null을 가리킵니다. 위 그림은 🎜단일 연결 목록🎜?입니다. 🎜🎜연결된 목록과 객체에는 큰 차이가 있습니다. 연결리스트에서는 각 노드가 포인터를 통해 다음 노드와 연결됩니다. 따라서 연결 목록의 각 노드 사이에는 연결이 있는 반면, 객체에서는 키-값 쌍이 서로 연결되지 않고 무작위로 저장됩니다. 🎜🎜다음으로 정수를 저장하기 위해 연결 목록을 구현합니다. JS는 내장 연결 목록 지원을 제공하지 않기 때문에 연결 목록을 구현하기 위해 객체와 클래스를 사용할 것입니까?🎜

this.tail.next = node

🎜위 코드에서 우리는 두 개의 클래스를 만들었습니다. 하나는 🎜연결 목록🎜 자체용이고 다른 하나는 🎜 노드🎜 자체. 논의한 대로 각 노드에는 값과 포인터(next 필드에 해당)라는 두 가지 속성이 있습니다. 🎜🎜🎜LinkedList🎜 클래스에는 마지막 속성의 tail을 저장하는 데 사용되는 head(초기 값은 null)라는 세 가지 속성이 포함되어 있습니다. 연결된 목록의 노드(null도 가리킴) 및 연결된 목록의 길이를 저장하는 데 사용되는 length 속성. 다음으로, 내부에 메소드를 구현해 보겠습니다. 🎜

append(값을 순서대로 추가)

🎜이 함수는 연결된 목록의 끝에 노드를 추가합니다. 이 기능을 구현하려면 수행해야 하는 일부 작업을 이해해야 합니다. 🎜🎜🎜🎜🎜🎜위 그림에서 다음과 같은 방법으로 append 기능을 구현할 수 있습니다. 🎜

this.head.next = node;

🎜Simple pair < code>append 방법을 설명해주세요. 🎜

this.tail = node

🎜 head가 null을 가리키는지 확인하세요. 이때 head는 null을 가리키는지 확인하세요. null. 따라서 새 개체를 만들고 head 및 tail에 할당합니다.🎜

head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
tail : {value: 4, next: null}
length:3

🎜이제 head</ code> 및 <code>tail은 모두 동일한 개체를 가리키므로 이를 기억하는 것이 중요합니다. 🎜🎜다음으로 연결된 목록에 두 개의 값을 더 추가합니다. 🎜

  prepend (value) {
  const node = new Node(value)

  node.next = this.head
  this.head = node
  this.length++
}

🎜이제 head는 null을 가리키지 않으므로 append를 입력합니다. 함수 else 분기: 🎜

this.tail.next = node

由于head 和tail 都指向同一个对象，tail的变化都会导致head对象的变化，这是JS 中对象的工作方式。在JavaScript中，对象是通过引用传递的，因此 head 和tail都指向存储对象的相同地址空间。上面这行代码相当于

this.head.next = node;

下一行：

this.tail = node

现在，在执行完上面的代码行之后，this.head.next和this.tail指向同一对象，因此，每当我们添加新节点时，head对象都会自动更新。

执行三次append之后，linkedList1 的结构应该是这样的：

head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
tail : {value: 4, next: null}
length:3

从上面的代码中我们可以看到，链表的append函数的复杂度是O(1)，因为我们既不需要移动索引，也不需要遍历链表。

我们来看下一个函数 ?

prepend (将值添加到链表的开头)

为了实现此函数，我们使用Node类创建一个新节点，并将该新节点的下一个对象指向链表的head 。 接下来，我们将新节点分配给链表的head：

与append函数一样，这个函数的复杂度也是O(1)。

  prepend (value) {
  const node = new Node(value)

  node.next = this.head
  this.head = node
  this.length++
}

就像append函数一样，此函数的复杂度也为O(1)。

insert (在特定索引处添加值)

在实现此函数之前，我们先看看它的一个转化过程。因此，出于理解目的，我们先创建一个值很少的链表，然后可视化insert函数。 insert 函数接受两个参数，值和索引:

let linkedList2 = new LinkedList()
linkedList2.append(23)
linkedList2.append(89)
linkedList2.append(12)
linkedList2.append(3)

linkedList2.insert(45,2)

第1步：

遍历链表，直到到达index-1位置:

第2步：

将索引为1的节点的指针（在本例中为89）分配给新节点（在本例中为45）：

第3步：

将新节点(45)的 next 指向给下一个节点(12)

这就是执行插入操作的方式。 通过以上可视化，我们观察到需要在index-1位置和index位置找到节点，以便可以在它们之间插入新节点。 在代码中实现：

insert (value, index) {
  if (index >= this.length) {
  this.append(value)
}

  const node = new Node(value)

  const { prevNode, nextNode } = thisg.getPrevNextNodes(index)
  prevNode.next = node
  node.next = nextNode

  this.length++
}

简单分析一下上面的函数：

如果index的值大于或等于length属性，则将操作移交给append函数。 对于 else 分支，我们使用 Node 类创建一个新节点，接下来观察一个新函数getPrevNextNodes() ，通过该函数我们可以接收prevNode和nextNode的值。 getPrevNextNodes函数的实现如下：

 getPrevNextNodes(index){
    let count = 0;
    let prevNode = this.head;
    let nextNode = prevNode.next;

    while(count < index - 1){
      prevNode = prevNode.next;
      nextNode = prevNode.next;
      count++;
    }

    return {
      prevNode,
      nextNode
    }
  }

通过遍历链表返回在index-1位置和index位置的节点，并将prevNode的next属性指向新节点，并将新节点的next属性指向nextNode。

链表的插入操作的复杂度为 O(n)，因为我们必须遍历链表并在index-1和 index 位置搜索节点。 尽管复杂度为O(n)，但我们发现此插入操作比对数组的插入操作快得多，在数组中，我们必须将所有元素的索引移到特定索引之后，但是在链接中，我们仅操纵 index-1 和index 位置的节点的下一个属性。

remove (删除特定索引处的元素)

实现了插入操作之后，删除操作就比较容易理解，因为它几乎与插入操作相同，当我们从getPrevNextNodes函数获取prevNode和nextNode值时，我们必须在remove中执行以下操作：

remove(index){
  let {previousNode,currentNode} = this.getNodes(index)
  previousNode.next = currentNode.next
  this.length--
}

删除操作的复杂度也为 O(n)，类似于插入操作，链表中的删除操作比数组中的删除操作要快。

reverse (反转链表)

虽然看起来很简单，但反转链表常常是实现起来最令人困惑的操作，因此，在面试中会经常询问这个操作。在实现这个函数之前，让我们先把反转链表的策略可视化一下。

为了反转链表，我们需要跟踪三个节点，previousNode，currentNode和nextNode。

考虑下面的链表:

let linkedList2 = new LinkedList()
linkedList2.append(67)
linkedList2.append(32)
linkedList2.append(44)

第一步：

开始，previousNode的值为null，而currentNode的值为head：

第二步：

接下来，我们将nextNode分配给currentNode.next：

第三步：

接下来，我们将currentNode.next属性指向previousNode：

第三步：

现在，我们将previousNode移至currentNode，将currentNode移至nextNode：

这个过程从步骤2重复操作，一直到currentNode 等于 null。

reverse (){
  let previousNode = null
  let currentNode = this.head

  while(currentNode !== null) {
    let nextNode = currentNode.next
    currentNode.next = previousNode
    previousNode = currentNode
    currentNode = nextNode
  }

  this.head = previousNode
}

就像我们看到的一样，直到currentNode === null，我们一直在遍历和移动这些值。 最后，我们将previousNode值分配给head。

反向运算的复杂度为O(n)。

查找 (查找特定索引的值)

这个操作很简单，我们只是遍历链表并返回特定索引处的节点。这个操作的复杂度也是O(n)。

lookup(index){
    let counter = 0;
    let currentNode = this.head;
    while(counter < index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }

好了，我们已经完成了用javascript实现单个链表的基本操作。单链表和双链表的区别在于，双链表的节点具有指向前一个节点和下一个节点的指针。

总结

链表为我们提供了快速的append（末尾添加元素）和prepend（开头添加元素）操作。 尽管链表中的插入操作的复杂度为O(n)，但比数组的插入操作要快得多。 使用数组时我们面临的另一个问题是大小复杂性，当使用动态数组时，在添加元素时，我们必须将整个数组复制到另一个地址空间，然后添加元素，而在链表中，我们不需要 面对这样的问题。

在使用对象时，我们面临的问题是元素在内存中的随机位置，而在链表中，节点是通过指针相互连接的，指针提供了一定的顺序。

原文地址：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/

作者：Vivek Bisht 

译文地址：https://segmentfault.com/a/1190000024565634

更多编程相关知识，请访问：编程教学！！

위 내용은 JS(Linked-list)의 데이터 구조에 대한 심층적인 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!