arrays - 链表与数组（已实现？）

Question

数组是与链表不同的数据结构，对吧？或者我可以使用数组实现链表？我对这个话题有点困惑，如果你能帮助我，我将不胜感激。谢谢！

标签： arraysdata-structureslinked-list

Answer 1

数组是与链表不同的数据结构，对吧？

是的，数组和链表是不同的数据结构。

链表：
链表是数据元素的线性集合，其顺序不是由它们在内存中的物理位置给出的。相反，每个元素都指向下一个元素。它是一种数据结构，由一组节点组成，这些节点一起表示一个序列。

假设您有这样定义的节点结构（在示例中使用 C 语言结构）：

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

链表的每个节点都有一个整数和一个指向其下一个节点的指针，该指针用于访问链表的下一个成员（最后一个节点的下一个指针设置为NULL）。内存中的视图将是这样的：

---------    ---------    ---------    ---------
| 1 |  -|--->| 2 |  -|--->| 3 |  -|--->| 4 |  -|--->NULL
---------    ---------    ---------    ---------

它提供了在列表中任何位置插入/删除元素的灵活性，您只需要设置/重置节点的下一个指针。缺点是需要顺序遍历才能访问其节点。

数组：
数组数据结构，或简称数组，是由一组元素（值或变量）组成的数据结构，每个元素由至少一个数组索引或键标识。

假设您有 5 个整数的数组（在示例中使用 C 语言构造）：

int arr[5] = {0}; // array of 5 integer initialized with 0

内存中的视图将是这样的：

  index   0   1   2   3   4
    arr ---------------------
        | 0 | 0 | 0 | 0 | 0 |
        ---------------------

它的优点是，您可以通过 index 直接访问数组的任何元素。例如，如果你想访问^第三个元素，你可以简单地做a[2]. 缺点是除了数组末尾之外的任何位置的数组中元素的插入/删除都不是直截了当的。为此，您可能必须对数组的几个元素进行洗牌。

或者我可以使用数组实现链表？

是的你可以。但是这样做不会有任何好处。相反，它会在您的代码中引入不必要的复杂性。检查这个。