接着讲递归结构

接着讲递归结构

递归(递归定义的)数据结构是在部分中复制自身的结构。

我们刚刚见过在上面的公司结构的例子。

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的变量来引用列表的最后一个元素(并在从末尾添加/删除元素时更新它)。

数据结构可以根据我们的需要而变化。