接着讲递归结构
接着讲递归结构
递归(递归定义的)数据结构是在部分中复制自身的结构。
我们刚刚见过在上面的公司结构的例子。
A公司部门是:
要么是一群人。
或者一个带有部门的对象。
web开发人员还有更著名的例子:HTML和XML文档。
在HTML文档中，一个HTML标签可能包含以下列表:
文本块。
html注释。
其他html标签(可能包含文本片段/注释或其他标签等)。
这又是一个递归定义。
为了更好地理解，我们将介绍另一种名为“链表”的递归结构，在某些情况下，它可能是数组的更好选择。
链表
想象一下，我们想存储一个有序的对象列表。
自然的选择是一个数组:
let arr = [obj1, obj2, obj3];
但是数组有一个问题。“删除元素”和“插入元素”操作代价很高。例如，arr.unshift(obj)操作必须对所有元素重新编号，以便为新的obj腾出空间，如果数组很大，则需要花费时间。与arr.shift()相同。
只有那些不需要大规模重编号的结构修改是在数组末尾操作的:arr.push/pop。数组对于大的队列来说很慢，当我们需要从一开始就处理时。
另外，如果我们真的需要快速插入/删除，我们可以选择另一种称为链表的数据结构。
链表元素被递归定义为一个对象:
值。
引用下一个链表元素的next属性，如果结束，则为null。
let list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
列表的图示:
创建的另一个代码:
let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;
在这里我们可以更清楚地看到有多个对象，每个对象都有值，下一个对象指向邻居。list变量是链表中的第一个对象，因此跟随它的next指针可以到达任何元素。
这个列表可以很容易地被分割成多个部分，然后再连接回来:
let secondList = list.next.next;
list.next.next = null;
加入:
list.next.next = secondList;
当然，我们可以在任何地方插入或删除物品。
例如，要添加一个新值，我们需要更新列表的头:
let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
// prepend the new value to the list
list = { value: "new item", next: list };
要从中间删除一个值，更改前一个值的下一个:
list.next = list.next.next;
我们列了清单。下一个跳过1到值2。值1现在被排除在链之外。如果它没有存储在其他地方，它将自动从内存中删除。
与数组不同的是，没有质量重编号，我们可以很容易地重新排列元素。
当然，列表并不总是比数组好。否则，每个人都会只使用列表。
主要的缺点是我们不能简单地按编号访问元素。在数组中，arr[n]是一个直接引用。但是在列表中，我们需要从第一项开始，然后再走N次，才能得到第N个元素。
但我们并不总是需要这样的操作。例如，当我们需要队列甚至deque时——这种有序结构必须允许非常快地从两端添加/删除元素，但不需要访问其中间部分。
列表可以增强:
我们可以添加属性prev来引用之前的元素，方便向后移动。
我们还可以添加一个名为tail的变量来引用列表的最后一个元素(并在从末尾添加/删除元素时更新它)。
数据结构可以根据我们的需要而变化。