多个数组链接成一个数组_数组与链接列表–数组与链接列表之间的区别

野性酷女 2022-12-08 04:44 149阅读 0赞

![ffc147ac4beecd60055eace9fb6af7a4.png][]

多个数组链接成一个数组

Ever wondered, How data is stored inside the computer’s memory? You can’t just throw data into the memory without making proper structure for the data.

曾经想过，如何将数据存储在计算机内存中？ 您不能不为数据建立适当的结构就将数据扔到内存中。

To provide a organised structure for the data to get stored inside the computer’s memory so that we can use and manage the stored data in the most efficient way possible, we use [Data Structures][].

为了提供一种组织化的数据存储在计算机内存中的结构，以便我们可以以最有效的方式使用和管理存储的数据，我们使用[数据结构][Data Structures] 。

All programming languages provide fundamental data structures like int, char, float etc. to store the primitive type values. But with the use of user defined data types we can create data structure as required. It is like creating our home with bricks, we can make any type of structure we want.

所有编程语言都提供基本数据结构(例如int，char，float等)来存储原始类型值。 但是，通过使用用户定义的数据类型，我们可以根据需要创建数据结构。 就像用砖砌房屋一样，我们可以制造任何想要的结构。

Here in this article we will see two most commonly used user defined data types: Arrays and Linked List, Difference between Array and Linked List and their implementation.

在本文的此处，我们将看到两种最常用的用户定义数据类型：数组和链表，数组与链表之间的差异及其实现。

### 数组 **(**Array**)** ###

The simplest type of data structure is Array which is used to store set of similar data in continuous blocks of memory under a common heading or variable name. With its simplicity comes some barriers like it need continuous block of memory and if free memory is not available in contiguous block it becomes inefficient to use arrays.

数据结构的最简单类型是Array，它用于以公共标题或变量名将相似数据集存储在连续的内存块中。 它的简单性带来了一些障碍，例如它需要连续的内存块，并且如果连续内存块中没有可用的内存，则使用数组的效率会降低。

![Array Representation][]

Array Representation ([Source][])

数组表示法( [来源][Source] )

Arrays indexing starts with 0, and every element of the array can be accessed using its index. Operation on array is very fast as any element can accessed directly using array indexing. Name of array is the base address of the array and all other elements can be accessed using the base address because the memory allocated to array is consecutive.

数组索引从0开始，并且可以使用其索引访问数组的每个元素。 数组上的操作非常快，因为任何元素都可以使用数组索引直接访问。 数组的名称是数组的基地址，由于分配给数组的内存是连续的，因此可以使用基地址访问所有其他元素。

### 链表 **(**Linked List**)** ###

On the other hand, a simple yet very useful data structure which doesn’t need contiguous blocks of memory is Linked List. They are used in situations when there is need to allocate memory dynamically that is during runtime of a program. It can be visualized like a train where we have an Engine (Head) and all the carriages(nodes) are linked to the train engine either directly or indirectly through other carriages.

另一方面，链表是一个简单但非常有用的数据结构，它不需要连续的内存块。 它们用于需要在程序运行期间动态分配内存的情况。 它可以像火车一样可视化，我们有一个引擎(Head)，所有车厢(节点)都直接或间接通过其他车厢链接到火车引擎。

![Linked list Representation][]

Linked list Representation ([Source][Source 1])

链接列表表示( [来源][Source 1] )

Linked list is user-defined data type where all the nodes of the list are linked using pointers. To access any node of the list, we must traverse the list linearly unlike array where we can directly access the elements.

链接列表是用户定义的数据类型，其中列表的所有节点都使用指针链接。 要访问列表的任何节点，我们必须线性遍历列表，这与可以直接访问元素的数组不同。

## 数组与链接列表–数组与链接列表之间的区别 **(**Array vs Linked List – Difference between Array and Linked List**)** ##

<table> 
 <thead> 
  <tr> 
   <td><strong>Parameters</strong></td> 
   <td><strong>Array</strong></td> 
   <td><strong>Linked List</strong></td> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Definition</td> 
   <td>It is a collection of elements having same data type with a common name.</td> 
   <td>It is an ordered collection of elements which are connected by links or pointers.</td> 
  </tr> 
  <tr> 
   <td>Size</td> 
   <td>Fixed, once declared cannot be changed.</td> 
   <td>Variable, can be changed during run-time.</td> 
  </tr> 
  <tr> 
   <td>Memory Allocation</td> 
   <td>Require Contiguous blocks of memory.</td> 
   <td>Random memory can be allocated.</td> 
  </tr> 
  <tr> 
   <td>Access</td> 
   <td>Direct or randomly accessed, i.e., Specify the array index or subscript.</td> 
   <td>Sequentially accessed, i.e., Traverse starting from the first node in the list by the pointer.</td> 
  </tr> 
  <tr> 
   <td>Insertion and Deletion</td> 
   <td>Relatively slow, as to insert or delete any element, other elements need to be shifted to occupy the empty space or make space.</td> 
   <td>Faster, Easier and Efficient as just linking or unlinking of node is required.</td> 
  </tr> 
  <tr> 
   <td>Searching</td> 
   <td>Binary search and Linear search</td> 
   <td>Linear search</td> 
  </tr> 
  <tr> 
   <td>Extra Space</td> 
   <td>Extra space is not required.</td> 
   <td>To link nodes of list, pointers are used which require extra Space.</td> 
  </tr> 
  <tr> 
   <td>Memory Utilization</td> 
   <td>Inefficient</td> 
   <td>Efficient</td> 
  </tr> 
  <tr> 
   <td>Types</td> 
   <td>It can be&nbsp;single dimensional, two dimensional or&nbsp;multi-dimensional.</td> 
   <td>It can be singly,&nbsp;doubly&nbsp;or&nbsp;circular&nbsp;linked list.</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <td> <strong>参量</strong> </td> 
   <td> <strong>数组</strong> </td> 
   <td> <strong>链表</strong> </td> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td> 定义 </td> 
   <td> 它是具有相同数据类型和通用名称的元素的集合。 </td> 
   <td> 它是通过链接或指针连接的元素的有序集合。 </td> 
  </tr> 
  <tr> 
   <td> 尺寸 </td> 
   <td> 固定，一旦声明就不能更改。 </td> 
   <td> 变量，可以在运行时更改。 </td> 
  </tr> 
  <tr> 
   <td> 内存分配 </td> 
   <td> 需要连续的内存块。 </td> 
   <td> 可以分配随机内存。 </td> 
  </tr> 
  <tr> 
   <td> 访问 </td> 
   <td> 直接或随机访问，即指定数组索引或下标。 </td> 
   <td> 顺序访问，即指针从列表中的第一个节点开始遍历。 </td> 
  </tr> 
  <tr> 
   <td> 插入和删除 </td> 
   <td> 相对较慢，因为要插入或删除任何元素，其他元素需要移动以占据空白空间或腾出空间。 </td> 
   <td> 更快，更轻松，更高效，因为只需要链接或取消链接节点即可。 </td> 
  </tr> 
  <tr> 
   <td> 正在搜寻 </td> 
   <td> 二进制搜索和线性搜索 </td> 
   <td> 线性搜索 </td> 
  </tr> 
  <tr> 
   <td> 额外空间 </td> 
   <td> 不需要额外的空间。 </td> 
   <td> 为了链接列表节点，使用了需要额外空间的指针。 </td> 
  </tr> 
  <tr> 
   <td> 内存利用率 </td> 
   <td> 低效 </td> 
   <td> 高效的 </td> 
  </tr> 
  <tr> 
   <td> 种类 </td> 
   <td> 它可以是一维，二维或多维的。 </td> 
   <td> 它可以是单，双或循环链表。 </td> 
  </tr> 
 </tbody> 
</table>

### C ++中的数组实现 **(**Array Implementation in C++**)** ###

#include<iostream>
     
    using namespace std;
     
    int main()
    {
    	int arr[5];  // declaration an integer array of size 5
    	
    	arr[0]=5;  // assigning values to the array elements
    	arr[1]=4;  //  notice that array indexing starts from 0 and ends at size-1
    	arr[2]=3;
    	arr[3]=2;
    	arr[4]=1;
    	
    	for(int i=0;i<5;i++)
    	cout<<arr[i]<<" ";    // printing array elements
    	
    	return 0;
    }

**Output**

**输出量**

*5 4 3 2 1*

### C ++中的链表实现 **(**Linked List Implementation in C++**)** ###

#include<iostream>
     
    using namespace std;
     
    /* Creating user defined structure for storing data in linked list */
    struct Node 
    { 
       int data; 
       struct Node *next;  // pointer to link nodes of the list
    }; 
     
    struct Node* head = NULL;   // Initially their is no element in list, so head point nowhere 
     
    /* function to insert and link nodes to the list */
    void insert(int new_data) 
    { 
       struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));  // allocating memory dynamically
       new_node->data = new_data; 
       new_node->next = head; 
       head = new_node; 
    } 
     
    /* function to display data of the list */
    void display() 
    { 
       struct Node* ptr;
       ptr = head;
       while (ptr != NULL) 
       { 
          cout<< ptr->data <<" "; 
          ptr = ptr->next; 
       } 
    } 
     
    int main() 
    { 
       insert(5);  // inserting data in the list
       insert(1);
       insert(4);
       insert(6);
       insert(7);
       
       cout<<"The linked list is: ";
       display(); 
       return 0; 
    }

**Output**

**输出量**

*The linked list is: 7 6 4 1 5*

*链接列表为：7 6 4 1 5*

### 影片教学 **(**Video Tutorial**)** ###

> 翻译自: [https://www.thecrazyprogrammer.com/2019/08/array-vs-linked.html][https_www.thecrazyprogrammer.com_2019_08_array-vs-linked.html]

多个数组链接成一个数组

[ffc147ac4beecd60055eace9fb6af7a4.png]: /images/20221123/7a63872913444f829f0ec4752ff3ead3.png
[Data Structures]: https://www.thecrazyprogrammer.com/2018/10/types-of-data-structures.html
[Array Representation]: /images/20221123/7eb73c35c0b74f25ae3e8c5790653dcf.png
[Source]: https://beginnersbook.com/wp-content/uploads/2018/10/array.jpg
[Linked list Representation]: /images/20221123/1f2e75aea6d949058be5b79f416cbca9.png
[Source 1]: https://s3-us-west-2.amazonaws.com/ib-assessment-tests/problem_images/singly-ll.png
[https_www.thecrazyprogrammer.com_2019_08_array-vs-linked.html]: https://www.thecrazyprogrammer.com/2019/08/array-vs-linked.html