资讯专栏INFORMATION COLUMN

用 JavaScript 实现链表

appetizerio / 3364人阅读

摘要:相反,双向链表具有指向其前后元素的节点。另外,可以对链表进行排序。这个实用程序方法用于打印链表中的节点,仅用于调试目的。第行将更新为,这是从链表中弹出最后一个元素的行为。如果链表为空,则返回。

什么是链表

单链表是表示一系列节点的数据结构,其中每个节点指向链表中的下一个节点。 相反,双向链表具有指向其前后元素的节点。

与数组不同,链表不提供对链表表中特定索引访问。 因此,如果需要链表表中的第三个元素,则必须遍历第一个和第二个节点才能到得到它。

链表的一个好处是能够在固定的时间内从链表的开头和结尾添加和删除项。

这些都是在技术面试中经常被问到的数据结构,所以让我们开始吧。

另外,可以对链表进行排序。 这意味着当每个节点添加到链表中时,它将被放置在相对于其他节点的适当位置。

节点

链表只是一系列节点,所以让我们从 Node 对象开始。

一个节点有两条信息

指向链表中下一项的指针或引用(对于单链表)

节点的值

对于我们的节点,我们只需要创建一个函数,该函数接受一个值,并返回一个具有上面两个信息的对象:指向下一个节点的指针和该节点的值

注意,我们可以只声明 value 而不是 value: value。这是因为变量名称相同(ES6 语法)
节点链表

现在,让我们深入研究 NodeList 类,以下就是节点链表样子。

节点链表将包含五个方法:

push(value): 将值添加到链表的末尾

pop() :弹出链表中的最后一个值

get(index):返回给定索引中的项

delete(index):从给定索引中删除项

isEmpty(): 返回一个布尔值,指示链表是否为空

printList():不是链表的原生方法,它将打印出我们的链表,主要用于调试

构造函数

构造函数中需要三个信息:

head:对链表开头节点的引用

tail:对链表末尾节点的引用

length:链表中有多少节点

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

isEmpty() 方法是一个帮助函数,如果链表为空,则返回true

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

这个实用程序方法用于打印链表中的节点,仅用于调试目的。

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

在添加新节点之前,push 方法需要检查链表是否为空。如何知道链表是否为空? 两种方式:

isEmpty()方法返回true(链表的长度为零)

head 指针为空

对于这个例子,我们使用 head是否为null来判断链表是否为空。

如果链表中没有项,我们可以简单地将head 指针和tail指针都设置为新节点并更新链表的长度。

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

如果链表不是空的,我们必须执行以下操作:

tail.next 指向新节点

tail 指向新节点

更新链表长度

以下是完整的 push 方法:

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

在删除链表中的最后一项之前,我们的pop方法需要检查以下两项内容:

检查链表是否为空

检查链表中是否只有一项

可以使用isEmpty方法检查链表是否包含节点。

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

我们如何知道链表中只有一个节点? 如果 headtail 指向同一个节点。但是在这种情况下我们需要做什么呢? 删除唯一的节点意味着我们实际上要重新设置链表。

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

如果链表中有多个元素,我们可以执行以下操作

当链表中有节点时,
 如果链表中的下一个节点是 tail 
   更新 tail 指向当前节点
   当前节点设置为 null,
   更新链表的长度
   返回前一个 tail 元素

它看起来像这样:

    1  let currentNode = this.head;
    2  let secondToLastNode;
    3
    4  //从前面开始并迭代直到找到倒数第二个节点
    5 
    6  while (currentNode) {
    7    if (currentNode.next === this.tail) {
    8      // 将第二个节点的指针移动到最后一个节点
    9      secondToLastNode = currentNode;
   10      break;
   11    }
   12    currentNode = currentNode.next;
   13  }
   14  // 弹出该节点
   15  secondToLastNode.next = null;
   16  // 将 tail 移动到倒数第二个节点
   17  this.tail = secondToLastNode;
   18  this.length--;
   19 
   20  // 初始化 this.tail
   21   return nodeToRemove;

如果你无法想象这一点,那么让我们来看看它。

第6-10行:如果链表中的下一个节点是最后一个项,那么这个当前项目就是新tail,因此我们需要保存它的引用。

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

第15行:将secondToLastNode更新为null,这是从链表中“弹出”最后一个元素的行为。

secondToLastNode.next = null;

第17行:更新tail以指向secondToLastNode

this.tail = secondToLastNode;

第18行:更新链表的长度,因为我们刚删除了一个节点。

第21行:返回刚刚弹出的节点。

以下是完整的pop方法:

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

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;
}

如果我们请求第一个元素,返回 head

// 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;
}
Delete

delete方法需要考虑到三个地方

删除的索引超出了链表的范围

链表是否为空

我们想要删除 head

如果链表中不存在我们要删除的索引,则返回 null

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

如果我们想删除head,将head设置为链表中的下一个值,减小长度,并返回我们刚刚删除的值。

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

如果以上都 不是,则删除节点的逻辑如下:

循环遍历正在查找的索引

   增加索引值

   将前一个和当前指针向上移动一个

将当前值保存为要删除的节点

更新上一个节点的指针以指向下一个节点

如果下一个值为 `null`

   将`tail`设置为新的最后一个节点

更新链表长度

返回已删除的节点

如果你需要可视化图片,请参考Pop部分中的图表。

以下是完整的 delete 方法:

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;
}


你的点赞是我持续分享好东西的动力,欢迎点赞!

欢迎加入前端大家庭,里面会经常分享一些技术资源。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/109658.html

相关文章

  • JavaScript 实现链表操作 - 06 Insert Sort

    摘要:需求实现一个函数对链表进行升序排列插入排序。关于插入排序插入排序的介绍可以看,大体逻辑为建立一个新的空链表。遍历完成,返回新链表。代码如下总结因为有上个的函数的帮助,这个插入排序实现起来非常简单。 TL;DR 2016 年末最后一篇,对链表进行插入排序。系列目录见 前言和目录 。 需求 实现一个 insertSort() 函数对链表进行升序排列(插入排序)。实现过程中可以使用 上一个 ...

    doodlewind 评论0 收藏0
  • JavaScript 实现链表操作 - 13 Shuffle Merge

    摘要:需求实现函数把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。通过行的调换指针,我们可以保证下一次循环就是对另一个链表进行操作了。这样一直遍历到两个链表末尾,返回结束。参考资料的代码实现的测试 TL;DR 把两个链表洗牌合并成一个,系列目录见 前言和目录 。 需求 实现函数 shuffleMerge() 把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。这叫洗牌合并。举...

    shiguibiao 评论0 收藏0
  • JavaScript 实现链表操作 - 15 Merge Sort

    摘要:需求实现函数进行归并排序。解法归并排序的运行方式是,递归的把一个大链表切分成两个小链表。切分到最后就全是单节点链表了,而单节点链表可以被认为是已经排好序的。这时候再两两合并,最终会得到一个完整的已排序链表。用把排好序的两个链表合并起来。 TL;DR 对链表进行归并排序,系列目录见 前言和目录 。 需求 实现函数 mergeSort() 进行归并排序。注意这种排序法需要使用递归。在 fr...

    X_AirDu 评论0 收藏0
  • JavaScript 实现链表操作 - 11 Alternating Split

    摘要:需求实现一个函数,把一个链表切分成两个。子链表的节点应该是在父链表中交替出现的。所以整个算法的解法就能很容易地用表示。唯一需要考虑的就是在每个循环体中判断节点该插入哪个链表。也有人使用持续增长的配合取余来做,比如。 TL;DR 把一个链表交替切分成两个,系列目录见 前言和目录 。 需求 实现一个 alternatingSplit() 函数,把一个链表切分成两个。子链表的节点应该是在父链...

    jsyzchen 评论0 收藏0
  • JavaScript 实现链表操作 - 16 Sorted Intersect

    摘要:需求实现函数取两个已排序的链表的交集,交集指两个链表都有的节点,节点不一定连续。每个链表应该只遍历一次。结果链表中不能包含重复的节点。当我们对比和的值时,有这几种情况,这时节点肯定交集,加入结果链表中。 TL;DR 一次遍历取两个排序链表的交集,系列目录见 前言和目录 。 需求 实现函数 sortedIntersect() 取两个已排序的链表的交集,交集指两个链表都有的节点,节点不一定...

    zhigoo 评论0 收藏0
  • JavaScript 实现链表操作 - 01 Push & Build List

    摘要:写两个帮助函数来创建链表。用于把一个节点插入到链表的头部。这个方法应该始终返回一个新的链表。接收一个数组为参数,创建对应的链表。参考资料的代码实现的测试 TL;DR 写两个帮助函数来创建链表。系列目录见 前言和目录 。 需求 写两个方法 push 和 buildList 来初始化链表。尝试在 buildList 中使用 push 。下面的例子中我用 a -> b -> c 来表示链表,...

    Scorpion 评论0 收藏0

发表评论

0条评论

appetizerio

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<