链接列表在数组上的优点是什么？反之亦然 [英] What is the advantage of linked list over an array and vice versa?

问题描述

请说明链接列表在数组中的优势是什么。而且与链表相比，使用数组有什么优势。

Regards，
Shoaib

解决方案

都存储一系列元素，但使用不同的技术。

数组记忆中的连续顺序，即它看起来如下：

  --------------- -------------------------------------------------- --------------------- 
 |项目1 |项目2 |项目3 | ... ... |项目x | //这里来的其他东西
 ---------------------------------------- ---------------------------------------------- 
  

这意味着元素在内存中连续一个。

<另一方面，p> A（（双重）链接）列表以下列方式存储项目：它为每个元素创建一个自己的列表项这个列表项将实际元素和将指针/引用/提示/等保存到下一个列表项。如果它是双向链接的，它还包含以前的列表项的指针/引用/提示/等：

  ----------- 
 ------------ ---------- |项目4 | 
 |项目1 | |项目2 | | next --- + ----... 
 | next --- + -------> |下一个| ------------ 
 ------------ --- + ------ ^ 
 | | 
 | | 
 v | 
 ---------- | 
 |项目3 | | 
 |下一个 -  + --- + 
 ---------- 
  

这意味着，这些元素可以遍布内存，而不是存储在特定的内存位置。

现在我们知道这一点，我们可以比较一些常见的操作元素序列：

• 访问特定索引的元素使用数组，我们简单地计算这个索引的偏移量，并将索引的元素。

  
  
  

  这是非常便宜的。另一方面，使用列表，我们不知道索引中存在元素的先验（因为所有元素都可以在内存中的任何位置），所以我们必须逐个列出项目，直到我们在索引中找到元素。这是一个昂贵的操作。




• 在序列末尾添加一个新元素使用数组这可能会导致以下问题：数组通常是固定的大小，所以如果我们有这个情况我们的数组已经完全填充（见 //这里来的其他东西），我们可能不会把新元素放在那里，因为可能还有别的东西。所以，也许我们必须复制整个数组。但是，如果数组没有被填充，我们可以简单地将元素放在那里。

  
  
  

  使用列表，我们必须生成一个新的列表项，将元素放入其中，并将当前最后一个元素的下一个指针设置到此新列表项。通常，我们存储对当前最后一个元素的引用，以便我们不必搜索整个列表来查找它。因此，插入一个新元素不是列表的真正问题。




• 在中间添加一个新元素 数组：这里，我们可能会遇到以下情况：我们有一个元素为1到1000的数组：

  
  
  

  1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 |免费|免费

  
  
  

  现在，我们要在之间插入 4.5 4 和 5 ：这意味着我们必须从 5 code>到 1000 一个位置，以便为 4.5

    1 | 2 | 3 | 4 |免费| 5 | 6 | ... | 999 | 1000 |免费
   
   || 
   vv 
   
   1 | 2 | 3 | 4 | 4.5 | 5 | 6 | ... | 999 | 1000 |免费
    

  移动所有这些元素，是一个非常昂贵的操作。所以更好不要经常这样做。

  
  
  

  现在我们考虑一下列表可以执行这个任务：假设我们目前有以下列表：

    1  - > 2  - > 3  - > 4→> 5  - > ...  - > 999  - > 1000 
    

  再次，我们要插入 4.5 在 4 和 5 之间。这可以很容易地完成：我们生成一个新的列表项并更新指针/引用：

    1  - > 2  - > 3  - > 4 5→> ...  - > 999  - > 1000 
   | ^ 
   +  - > 4.5  -  + 
    

  我们只是创建了一个新的列表元素，并生成了一些绕过来插入它 - 非常便宜（只要我们有一个指针/引用新的元素将插入到列表项中）。




所以，我们来总结一下：链接的列表在随机位置插入（只要你有足够的列表项的指针）就是非常好的。如果您的操作涉及到动态添加大量元素，并遍历所有元素，列表可能是一个不错的选择。

一个数组在索引访问方面非常好。如果您的应用程序需要经常访问特定位置的元素，则应该使用数组。

值得注意的事项：

• 解决数组的固定大小问题：如前所述，（raw）数组通常是固定大小的。然而，现在这个问题现在不再是真的了，因为几乎所有的编程语言都提供了生成（可能缩小）数组的机制，就是根据需要动态生成数组。可以实现这种不断增长和缩小，使得我们有用于插入和移除元素（在数组结尾）的O（1）的运行时间，以便程序员不必调用明确地增加和收缩。




• 为插入提供这样好的属性，它们可以用作搜索树的基础数据结构等您构建一个搜索树，其最低级别由链接列表组成。

Please explain what is the advantage of linked list over an array. And also is there any advantage of using array compared to linked list.

Regards, Shoaib

解决方案

Both store a sequence of elements, but using different techniques.

An array stores elements in successive order in memory, i.e. it looks like follows:

--------------------------------------------------------------------------------------
|  item 1  |  item 2  |  item 3  |  ...  ...  |  item x  | //here comes other stuff
--------------------------------------------------------------------------------------

This means, elements are one after another consecutive in memory.

A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":

                                  ------------
------------        ----------    |  item 4  |
|  item 1  |        | item 2 |    |  next ---+----...
|  next ---+------->| next   |    ------------
------------        ---+------      ^
                       |            |
                       |            |
                       v            |
                       ----------   |
                       | item 3 |   |
                       | next --+---+
                       ----------

This means, the elements can be spread all over the memory and are not stored at specific memory locations.

Now that we know this, we can compare some usual operations on sequences of elements:

• Accessing an element at a specific index: Using an array, we simply compute the offset for this index and have the element at the index.

  This is very cheap. With a list on the other hand, we do not know a priori where the element at index is stored (since all elements can be anywhere in memory), so we have to walk the list item by item until we find the element at the index. This is an expensive operation.

• Adding a new element at the end of the sequence: Using an array this can lead to the following problem: Arrays are usually of fixed size, so if we have the situation that our array is already completely filled (see //here comes other stuff), we probably cant put the new element there because there might already be something else. So, maybe we have to copy the whole array. However, if the array is not filled, we can simply put the element there.

  Using a list, we have to generate a new "list item", put the element into it and set the next pointer of the currently last element to this new list item. Usually, we store a reference to the currently last element so that we don't have to search through the whole list to find it. Thus, inserting a new element is no real problem with lists.

• Adding a new element somewhere in the middle: Let's first consider arrays: here, we might get into the following situation: We have an array with elements 1 to 1000:

  1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free

  Now, we want to insert 4.5 between 4 and 5: This means, we have to move all elements from 5 to 1000 one position right in order to make space for the 4.5:

   1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free
  
                    ||
                    vv
  
   1 | 2 | 3 | 4 | 4.5  | 5 | 6 | ... | 999 | 1000 | free
  

  Moving all these elements, is a very expensive operation. So better don't do this too often.

  Now we consider, how a list can perform this task: Let's say we have currently the following list:

   1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000
  

  Again, we want to insert 4.5 between 4 and 5. This can be done very easily: We generate a new list item and update the pointers/references:

   1 -> 2 -> 3 -> 4        5 -> ... -> 999 -> 1000
                  |        ^
                  +-> 4.5 -+
  

  We have simply created a new list element and generated sort of "bypass" to insert it - very cheap (as long as we have a pointer/reference to the list item the new element will be inserted after).

So, let's sum up: Linked lists are really nice when it comes to inserting at random positions (as long as you have a pointer to the adequate list item). If your operation involves adding lots of elements dynamically and traversing all elements anyway, a list might be a good choice.

An array is very good when it comes to index accesses. If your application needs to access elements at specific positions very often, you should rather use an array.

Notable things:

• Solving the fixed-size problem for arrays: As mentioned before, (raw) arrays are usually of fixed size. However, this problem is nowadays no real point anymore, since almost all programming languages provide mechanisms to generate arrays that grow (and possibly shrink) dynamically - just as needed. This growing and shrinking can be implemented such that we have amortized runtime of O(1) for inserting and removing elements (at the end of the array) and such that the programmer doesn't have to call grow and shrink explicitly.

• Since lists provide such nice properties for insertions, they can be used as underlying data structures for search trees, etc. I.e. you construct a search tree, whose lowest level consists of the linked list.

这篇关于链接列表在数组上的优点是什么？反之亦然的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！