php连表join技巧_假如不知道怎么用 JavaScript 实现链表的话一路来看看这篇文章

译文 | https://github.com/qq449245884/xiaozhi/issues/31

什么是链表

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

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

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

这些都是在技能口试中常常被问到的数据构造，以是让我们开始吧。

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

节点

链表只是一系列节点，以是让我们从 Node 工具开始。

一个节点有两条信息

对付我们的节点，我们只须要创建一个函数，该函数接管一个值，并返回一个具有上面两个信息的工具:指向下一个节点的指针和该节点的值。

把稳，我们可以只声明 value 而不是 value: value。
这是由于变量名称相同(ES6 语法)

我自己是一名从事了多年开拓的web前端老程序员，目前辞职在做自己的web前端私人定制课程，今年年初我花了一个月整理了一份最适宜2019年学习的web前端学习干货，各种框架都有整理，送给每一位前端小伙伴，想要获取的可以关注我的头条号并在后台私信我：前端，即可免费获取。

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

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

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

布局函数中须要三个信息:

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 方法须要检讨链表是否为空。
如何知道链表是否为空? 两种办法：

对付这个例子，我们利用 head是否为null来判断链表是否为空。

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

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

如果链表不是空的，我们必须实行以下操作：

以下是完全的 push 方法：

push(value) {const node = Node(value);// The list is emptyif (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;}

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

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

第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 nodewhile (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 nodethis.tail = secondToLastNode;this.length--;// Initialized to this.tailreturn nodeToRemove;}Get

get方法必须检讨三种情形：

如果链表中不存在要求的索引，则返回null。

// Index is outside the bounds of the listif (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 listif (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方法须要考虑到三个地方

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

// Index is outside the bounds of the listif (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://mp.weixin.qq.com/s/GV9uYmEEF7DE_1acygzAqg作者：web前端开拓