Web开发编程网
分享Web开发相关技术

了解您的JavaScript数据结构

Paul Ryan✏️撰写

我们要谈什么?

数据结构经常在JavaScript中被忽略-或更确切地说,我们考虑的不多。忽略数据结构的问题是,对于许多顶级公司而言,通常需要您深刻了解如何管理数据。掌握数据结构也将在您解决问题时为您的日常工作提供帮助。

在本文中,我们将讨论/实现的数据结构是:

  • 队列
  • 链表
  • 哈希表
  • 树木

LogRocket免费试用横幅

我们正在讨论的第一个数据结构是堆栈。这与队列非常相似,并且您之前可能已经听说过调用堆栈,这是JavaScript用于处理事件的方法。

在外观上,堆栈看起来像这样:

堆栈的视觉表示

因此,当您有堆栈时,您在堆栈上压入的最后一个项目将是第一个被移除的项目。这称为后进先出(LIFO)。Web浏览器中的“后退”按钮就是一个很好的例子:将您查看的每个页面添加到堆栈中,当您单击“返回”时,将从堆栈中弹出当前页面(最后添加的页面)。

那足够理论了。让我们来看一些代码:

class Stack {
  constructor() {
    // create our stack, which is an empty object
    this.stack = {}
  }
  // this method will push a value onto the top of our stack
  push(value) {

  }
  // this method is responsible for popping off the last value and returning it
  pop() {

  }

  // this will peek at the last value added to the stack
  peek() {

  }
}

我已经注释了上面的代码,因此希望您与我在一起。我们将要实现的第一个方法是push方法。

因此,让我们考虑一下我们需要这种方法来做的事情:

  • 我们需要接受一个价值
  • 然后,我们需要将该值添加到堆栈顶部
  • 我们还应该跟踪堆栈的长度,以便我们知道堆栈的索引

如果您可以先自己尝试一下,那就太好了,但是如果没有,那么完整的push方法实现如下:

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0; // this is our length 
  }

  push(value) {
    // so add the value to the top of our stack
    this._storage[this._length] = value;
    // since we added a value we should also increase the length by 1
    this._length++;
  }
  /// .....
}

我敢打赌,这比您想象的要容易。我认为,使用许多这样的结构,它们听起来比实际复杂得多。

现在让我们来看看pop方法。该pop方法的目标是删除最后添加到堆栈中的值,然后返回该值。如果可以的话,请先自己尝试,否则继续查看解决方案:

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0;
  }

  pop() {
    // we first get the last val so we have it to return
    const lastVal = this._storage[--this._length]
    // now remove the item which is the length - 1 
    delete this._storage[--this._length]
    // decrement the length
    this._length--;
    // now return the last value
    return lastVal
  }
}

凉!就快到了。我们需要做的最后一件事是该peek函数,它查看堆栈中的最后一项。这是最简单的功能:我们只返回最后一个值。实现是:

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0;
  }
  /*
  * Adds a new value at the end of the stack
  * @param {*} value the value to push
  */

  peek() {
    const lastVal = this._storage[--this._length]
    return lastVal
  }
}

因此,这与pop方法非常相似,但是这次,我们不删除最后一项。

是! 那是我们第一个覆盖的数据结构。现在让我们进入队列,它与堆栈非常相似。

队列

队列是我们将要讨论的下一个结构-希望栈在您的大脑中仍然很新鲜,因为队列非常相似。堆栈和队列之间的主要区别在于队列是先进先出(FIFO)。

在视觉上,我们可以这样表示:

队列的视觉表示

因此,两个大动作是enqueuedequeue。我们添加到背面并从正面移除。让我们开始实施队列以更好地理解。

我们代码的核心结构将如下所示:

class Queue {
  constructor() {
    // similar to above we have an object for our data structure
    // and we also have a variable to keep track of the length
    this.queue = {}
    this.length = 0
    // this is a new variable which tracks the head
    this.head = 0
  }

  enqueue(value) {

  }

  dequeue() {

  }

  peek() {

  }
}

因此,让我们首先实现我们的enqueue方法。其目的是向队列的后面添加一个项目。

enqueue(value) {
  // add a key of our length + head to our object with the value param
  this.queue[this.length + this.head] = value;
  this.length++
}

这是一个非常简单的方法,可以在队列末尾添加一个值,但是您可能会对感到困惑this.queue[this.length + this.head] = value;

假设我们的队列看起来像这样{14 : 'randomVal'}。在添加此内容时,我们希望我们的下一个键是15,因此它将是length(1)+ head(14),这给了我们15

下一个要实现的dequeue方法是:

dequeue() {
  // get a reference to our first val so we can return it
  const firstVal = this.queue[this.head]
  // now delete this from our queue
  delete this.queue[this.head]
  // decrement our lenght
  this.length--;
  // finally increment our head to be the next node
  this.head++;
}

最终要实现的peek方法是一种简单的方法:

peek() {
  // simply return the value at our head
  return this.queue[this.head];
}

队列就是这样-让我们继续Linked List数据结构。

链表

因此,让我们讨论强大的链表。这比上面的结构要复杂得多,但是我们可以一起弄清楚。

您可能遇到的第一个问题是为什么我们要使用链表?链表主要用于没有动态大小调整数组的语言。链接列表按顺序组织项目,每个项目指向下一个项目。

链表中的每个节点都有一个data值和一个next值。下面5是数据值,该next值指向下一个节点,即具有value的节点10

在视觉上,它看起来像这样:

链接列表的视觉表示

作为附带说明,先前的指针称为双向链接列表。

在一个对象中,以上内容LinkedList类似于以下内容

对象中的LinkedList

您会看到最后一个值1next值为null,因为这是我们的结尾LinkedList

那么现在,我们将如何实施呢?

让我们创建一个LinkedList具有价值1237

const myLinkedList = {
    head: {
        value: 1
        next: {
            value: 2           
            next: {
                value: 37
                next: null
            }
        }
    }
};

因此,我们知道如何手动创建LinkedList,但是让我们采用编写将实现的方法LinkedList

我们应该注意的第一件事是a LinkedList只是一堆嵌套对象!

构造a时LinkedList,我们需要a head和a tail,它们最初将指向我们的头部(因为第head一个和最后一个)。

class LinkedList {
  constructor(value) {
    this.head = {value, next: null}
    this.tail = this.head
  }
}

我们将要实现的第一个方法是insert方法,它将在链接列表的末尾插入一个值。

// insert will add to the end of our linked list
insert(value) {
  /* create the node */
  const node = {value, next: null}
  /* set the next property of the tail = to the new node */
  this.tail.next = node;
  /* the new node is now the tail */
  this.tail = node;
}

上面最令人困惑的行可能是this.tail.next = node。我们这样做是因为当我们添加一个新的节点上,我们也希望当前tail的新点node,这将成为新的tail。第一次插入a时nodenext头部的指针将指向新节点-就像在我们已设置的构造函数中一样this.tail = this.head

您也可以通过访问此网站来直观地看到此内容,这将帮助您了解插入的过程(按此esc按钮可以消除烦人的弹出窗口)。

我们将实现的下一个方法是删除节点。我们必须决定的第一件事是我们的参数是a value还是对a的引用node(在采访中,最好向采访者问这个)。为了我们的缘故,我们将说a value已通过。按值从列表中删除节点是一个缓慢的过程,因为我们必须遍历整个列表才能找到值。

我们这样做是这样的:

removeNode(val) {
  /* begin at the head */
  let currentNode = this.head
  /* we need to hold reference to the previous node */
  let previousNode
  /* while we have a node i.e. not passed the tail */
  while(currentNode) {
     /* if we find our value then break out */
     if(currentNode.value === val) {
        break;
     }
    /* with no value found currentNode we set this to previousNode */
    previousNode = currentNode
    /* we get the next node and assign it to currentNode  */
    currentNode = currentNode.next
  }
  /* we return undefined as we have found no node with that value  */
  if (currentNode=== null) {
    return false;
  }

  // if the node is the head then we set our head to the next value
  // of the head node
  if (currentNode === this.head) {
    this.head = this.head.next;
    return;
  }
  /* so we remove our node by setting the node before it to the node in front of it */  
  previousNode.next = currentNode.next
}

removeNode方法使我们对LinkedList工作原理有了很好的了解。

因此,只要再解释,我们是我们的第一个变量设置currentNodehead我们LinkedList,因为这是我们的第一个节点。然后,我们创建一个名为的占位符变量previousNode,该变量将在while循环中使用。我们从while条件开始循环currentNode-只要有条件,它将一直运行currentNode

while循环中的第一个检查是检查我们是否具有价值。如果不这样做,则将我们设置previousNodecurrentNode,并将我们currentNode设置为列表中的下一个节点。我们继续进行此过程,直到找到我们的价值或节点用完为止。

在后while循环,如果我们没有currentNode,我们返回false,这表明已无节点检出的用户。如果确实有一个currentNode,则检查是否currentNode是我们的头。如果是,我们设置head我们的LinkedList是第二点,这将成为head

最后,如果我们currentNode不是我们的头,我们将设置previousNode为指向node我们前面的currentNode,这会将我们currentNode从对象中删除。

另一种非常流行的方法(面试官也可能会问您)是该removeTail方法。这种方法可以做到在锡罐上说的话,只需去除锡罐的尾巴即可LinkedList。可以想象,这比上面的方法容易得多,但工作原理类似。

我建议您先自己尝试一下,然后再看下面的代码(要使它更复杂一点,我们将不在tail构造函数中使用):

removeTail() {
  let currentNode = this.head;
  let previousNode;
  while (currentNode) {
    /* the tail is the only node without a `next` value, so if no next value is present, then this must be our tail */
    if (!currentNode.next) {
      break;
    }
    // get a reference to our previous node
    previousNode = currentNode;
    // move onto the next node
    currentNode = currentNode.next;
  }
  // to remove the tail, we set the previousNode.next to null
  previousNode.next = null;
}

那是的一些主要方法LinkedList。您可能会遇到各种各样的方法,但是利用从以上中学到的知识,您应该能够管理所有这些方法。

哈希表

因此,我们要处理的倒数第二个数据结构是强大的哈希表。我故意将其放置在LinkedList解释之后,因为它们之间相距一百万英里。

哈希表是一种实现关联数组的数据结构,这意味着它将键映射到值。JavaScript对象是hash table,因为它存储键值对。

在视觉上,可以这样表示:

哈希表的视觉表示

在开始讨论如何实现哈希表之前,我们需要讨论哈希函数的重要性哈希函数的核心概念是,它接受任意大小的输入并返回固定大小的哈希码标识符。

hashThis('i want to hash this') => 7

哈希函数可能非常复杂或直接。GitHub上的每个文件都经过哈希处理,这使得每个文件的查找都非常快。散列函数背后的核心思想是,给定相同的输入将返回相同的输出。

涵盖了散列函数之后,该讨论如何实现散列表了。

三项行动,我们将讨论的insertget和,最后,remove

实现哈希表的核心代码如下:

class HashTable {
  constructor(size) {
    // define the size of our hash table, which will be used in our hashing function
    this.size = size;
    this.storage = [];
  }
  insert(key, value) { }
  get() {}
  remove() {}
  // this is how we will hash our keys
  myHashingFunction(str, n) {
    let sum = 0;
    for (let i = 0; i < str.length; i++) {
      sum += str.charCodeAt(i) * 3;
    }
    return sum % n;
  }
}

现在,让我们解决第一种方法insertinsert哈希表中的代码如下(为简单起见,此方法将处理冲突,但不会重复):

insert(key, value) {
  // will give us an index in the array
  const index = this.myHashingFunction(key, this.size);
  // handle collision - hash function returns the same
  // index for a different key - in complicated hash functions it is very unlkely
  // that a collision would occur
  if (!this.storage[index]) {
    this.storage[index] = [];
  }
  // push our new key value pair
  this.storage[index].push([key, value]);
}

因此,如果我们像这样调用insert方法:

const myHT = new HashTable(5);
myHT.insert("a", 1);
myHT.insert("b", 2);

您认为我们的哈希表会是什么样?

哈希表示例代码

您可以看到我们的键值对已插入到索引为1和的表中4

现在我们如何从哈希表中删除?

remove(key) {
    // first we get the index of our key
    // remember, the hashing function will always return the same index for the same
    // key
    const index = this.myHashingFunction(key, this.size);
    // remember we could have more than one array at an index (unlikely)
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      // let's loop over all the arrays at that index
      for (let i = 0; i < arrayAtIndex.length; i++) {
        // get the pair (a, 1)
        let pair = arrayAtIndex[i];
        // check if the key matches the key param
        if (pair[0] === key) {
          // delete the arrayatindex
          delete arrayAtIndex[i];
          // job done, so break out of the loop
          break;
        }
      }
    }
}

关于上述内容,您可能会想:“这不是线性时间吗?您会认为是正确的,但是由于这种情况在复杂的哈希函数中很少见,因此我们仍然认为哈希表是恒定的。

我们将实现的最终方法是get方法。这与remove方法相同,但是这次,我们返回pair而不是删除它。

get(key) {
    const index = this.myHashingFunction(key, this.size);
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      for (let i = 0; i < arrayAtIndex.length; i++) {
        const pair = arrayAtIndex[i];
        if (pair[0] === key) {
          // return the value
          return pair[1];
        }
      }
    }
  }

我认为没有必要去做,因为它的作用与remove方法相同。

这是对哈希表的出色介绍,并且您可以说,它并不像最初看起来那样复杂。这是一种在各处使用的数据结构,因此是一个很好理解的结构!

二叉搜索树

可悲的是(或者可能是幸运的),这是我们要处理的最后一个数据结构-臭名昭著的二进制搜索树。

当我们想到二进制搜索树时,我们应该想到的三件事是:

  • 根:这是树形结构的最高节点,没有父级
  • 父级:它是节点的子级,也是节点的父级
  • 节点此节点是节点的子节点,不一定有子节点

在二叉搜索树中,每个节点具有零个,一个或两个子代。左边的孩子称为左孩子,右边的孩子称为右孩子。在二叉搜索树中,左侧的子项必须小于右侧的子项。

在视觉上,您可以像这样描绘一个二进制搜索树:

二进制搜索树的可视表示

一棵树的核心类如下:

class Tree {
   constructor(value) {
     this.root = null
   }

   add(value) {
    // we'll implement this below
   }

}

我们还将创建一个Node类来表示我们的每个节点。

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

好的,让我们实现该add方法。我对代码的注释非常好,但是如果您发现它令人困惑,请记住,我们所做的只是从根开始并检查每个节点的leftright

add(value) {
    // if we do not have a root, then we create one
    if (this.root === null) {
      this.root = new Node(value);
      return;
    }
    let current = this.root;
    // keep looping
    while (true) {
      // go left if our current value is greater
      // than the value passed in
      if (current.value > value) {
        // if there is a left child then run the
        // loop again
        if (current.left) {
          current = current.left;
        } else {
          current.left = new Node(value);
          return;
        }
      }
      // the value is smaller, so we go right
      else {
        // go right
        // if there is a left child then run the
        // loop again
        if (current.right) {
          current = current.right;
        } else {
          current.right = new Node(value);
          return;
        }
      }
    }
}

让我们add像这样测试我们的新方法:

const t = new Tree();
t.add(2);
t.add(5);
t.add(3);

我们的树现在看起来像:

二进制搜索树示例代码

因此,为了获得更好的理解,让我们实现一种检查我们的树是否包含值的方法。

contains(value) {
  // get the root
  let current = this.root;
  // while we have a node
  while (current) {
    // check if our current node has the value
    if (value === current.value) {
      return true; // leave the function
    }
    // we decide on the next current node by comparing our value
    // against current.value - if its less go left else right
    current = value < current.value ? current.left : current.right;
  }
  return false;
}

AddContains是二分搜索树的两种核心方法。对这两种方法的了解可以使您更好地了解如何解决日常工作中的问题。

结论

哇,这是一个很长的时间。我们已经在本文中介绍了很多内容,并且接受有关此知识的采访将使您处于有利位置。我真的希望您学到了一些东西(我知道我知道),并且希望您能更轻松地进行技术面试(尤其是讨厌的白板面试)。


编者注:这篇文章有什么问题吗?您可以在此处找到正确的版本。

插件:LogRocket,用于Web应用程序的DVR

LogRocket仪表板免费试用横幅

LogRocket是一个前端日志记录工具,可让您像在您自己的浏览器中一样重播问题。LogRocket无需猜测错误发生的原因,也不要求用户提供屏幕截图和日志转储,而是让您重播会话以快速了解出了什么问题。无论框架如何,它都能与任何应用完美配合,并具有用于记录来自Redux,Vuex和@ ngrx / store的其他上下文的插件。

除了记录Redux动作和状态外,LogRocket还记录控制台日志,JavaScript错误,堆栈跟踪,带有标头+正文,浏览器元数据和自定义日志的网络请求/响应。它还使用DOM来记录页面上的HTML和CSS,甚至可以为最复杂的单页面应用程序重新创建像素完美的视频。

免费试用


“ 了解您的JavaScript数据结构”一文首先出现在LogRocket博客上

未经允许不得转载:WEB开发编程网 » 了解您的JavaScript数据结构

WEB开发编程网

谢谢支持,我们一直在努力

安全提示:您正在对WEB开发编程网进行赞赏操作,一但支付,不可返还。