链表相对于数组的优缺点

2025年3月17日 | 阅读11分钟

链表和数组都是最常用的数据结构。两者都有各自的优点和缺点，完全取决于具体情况，通过比较它们的时间和空间复杂度来决定哪种数据结构最适合使用。

数据结构

安排和存储数据以便于访问的方式称为数据结构。它作为一种容器，以高效且易于管理的方式存储值。

数据结构分类

Advantages and Disadvantages of Linked List Over Array

1. 原始（Primitive）： 这些是用于派生其他数据结构的基本数据结构。例如，int、float、String 等。

2. 非原始（Non-Primitive）： 这些数据结构是从原始数据结构派生出来的。非原始数据结构分为两种类型

线性（Linear）： 线性数据结构具有线性和简单的结构。线性又分为两个子类型
- 静态（Static）： 数组
- 动态（Dynamic）： 链表、栈、队列。
非线性（Non-Linear）：非线性数据结构具有复杂的结构。例如，树和图。

以下操作有助于区分并找出这两种数据结构的优缺点。

遍历（Traversing）： 访问数据结构中每个元素/值的过程称为遍历。
查找（Searching）： 查找元素/值在数据结构中的位置称为查找。
插入（Inserting）： 插入是将新值添加到数据结构中的过程。
删除（Deleting）： 从结构中删除值并释放空间的過程称为删除。
合并（Merging）： 将两组值连接在一起的过程称为合并。
排序（Sorting）： 根据特定序列排列值的过程称为排序。例如：按数字、按字母顺序等。

Array

数组是一种数据结构，用于在内存中连续存储不同的值。数组的元素数量有限，受其大小限制，该大小可以在定义数组时设置。

下方展示了数组的样本结构

索引从 0 开始。

数组类型

1. 一维数组

这是最简单的数组形式。

例如：

Int arr[5] = {15,34,78,23,56};

2. 二维数组

通常，二维数组是作为元素的一维数组集合。我们可以定义一个具有 m x n 维的二维整型数组，并在代码中使用它。通过在两个方括号中给出行和列的两个值来创建 2D 数组。

例如：

int arr[2][2]= {{2,6}, {6,2}};

您可以将其视为一个 2x2 矩阵。

3. 多维数组

包含多个维度的数组称为多维数组。通过在三个方括号中给出三个坐标的三个值来创建 3D 数组。

例如：

int arr[2][6][4];

插入： 在指定位置的数组中插入一个元素。如果空间可用，在数组的最后一个位置进行插入是有益的。在数组中间或第一个位置插入会花费时间和空间。因此，不应将数组用于此类插入。

数组插入代码

#include <iostream>
#include <stdlib.h>
using namespace std;
//insert element at the ith index of an array.
int insert(int arr[], int i, int val, int s){
           if(i>s){
                       return -1;
//index out of size.
                                   }
                                   
           else{
                       for(int j =(s-1); j>=i ; j--){
                       arr[j+1]=arr[j];
           }
           arr[i]=val;
           return arr[i];
           }
           
}

int main(){
           
           cout << "enter the size of the array" << endl;
           int n;
           cin >> n;
           int arr[n];
           int s= sizeof(arr);
           int i, val, b;
           cout << "enter the index" << endl;
           cin >> i;
           cout << "enter the value" << endl;
           cin >> val;
           for(int i=0; i<n; i++){
                       cout << "enter the " << i << " the element ";
                                               cin >> arr[i];                          
                       } 
           
            b=insrt( arr, i, val,s);
            cout << b;
           
           return 0;
}

删除： 从数组中删除一个元素。为了删除，我们必须移动其他元素，这很耗时。

Int p;
Int n; //size of array
Int arr[5]={8,5,0,2,23}
Cout<< "enter the position of the element to be deleted:"
Cin >> p;
for(int i= p-1; i<n; i++){
           arr[i]= arr[i+1];
}

n--; 

查找： 查找给定数组中的一个元素。建议在排序数组中进行查找，而不是在未排序的数组中。因为查找的最坏情况是元素位于最后一个位置，我们必须遍历整个数组才能到达最后一个位置。

二分查找： 在这种搜索算法中，我们总是通过变量 middle、low 和 high 将结构分成两半，从而到达中间元素。在每次划分中，high、middle 和 low 的值都会改变。应用/使用二分搜索算法的必要条件是：数据结构必须已排序。否则，我们必须对其进行排序。

int binary search(int arr[], int s, int e){  
           int l,h,m;
           l=0;
           h=s-1;
           m=(l+h)/2;
           
           while(l<=h){
           if(arr[m]==e){
                       return m;
           }
           
           else if(arr[m]<e){
                       l=m+1;
           }
           
           else{
                       h=m-1;
           }
   
}
return -1;      
                       
}

int main(){
           int arr[]={23,36,48,69,70,245,299,658};
           int e=69;
           int s= sizeof(arr)/sizeof(int);
           int x=binarysearch(arr,s,e);
           cout << "element found at index" << x;
           
           return 0;
}

排序： 将值按逻辑顺序排列。

#include<iostream>
using namespace std;
void slctnSort(int a[], int s) {
   int m, i, j, temp;
   for (i = 0; i < s - 1; i++) {
      m = i;
      for (j = i + 1; j < s; j++)
      if (a[j] < a[m])
      m = j;
      temp = a[i];
      a[i] = a[m];
      a[m] = temp;
   }
}
int main() {
   int a[] = { 55,78,32,67,87,43,3,4,90,99 };
   int s = sizeof(a)/ sizeof(a[0]);
   int i;
  
cout<<"original array is:"<<endl;
   for (i = 0; i < s; i++)
   cout<< a[i] <<" ";
  
cout<<endl;
   slctnSort(a, s);
   cout<< "Sorted array is: "<<endl;
   for (i = 0; i < s; i++)
   cout<< a[i] <<" ";
   return 0;
}

链表

链表也是线性数据结构之一。简单的链表结构包含数据部分和下一个部分。节点随机存储在主内存空间中，不一定是连续的。这是链表的主要优点，因为它有助于更好的内存管理。数据部分存储实际值/数据。下一个部分存储下一个节点的地址。

下方展示了链表的样本结构

链表类型

1. 单向链表（Singly-Linked List）： 这是一种非常简单的链表，具有线性的结构，包含数据部分和下一个部分。

例如

2. 双向链表（Doubly Linked List）： 双向链表比单向链表多一个部分，即除了数据和下一个部分之外，还有一个前一个部分。

例如

代码

class Node{
           public:
                       int data;
                       Node* next;
                       Node* prev;
                       
                       Node(int d){
                                   data=d;
                                   next=NULL;
                                   prev=NULL;
                       }
           
};

void insertAthead(Node* &head, int d){
           Node* temp = new Node(d);
           temp->next=head;
           head->prev=temp;
           head=temp;
           
}

void insertAttail(Node* &tail, int d){
           Node* temp= new Node(d);
           tail->next=temp;
           temp->prev=tail;
           tail=temp;
}

void insertAtposition(Node* &head, int position, int p){
                       Node* n1=new Node(p);
                       Node* temp = head;
                       int count=1;
           if(position==1){
                                   insertAthead(head, p);
           }
           
           else{

                       while(count<position -1){
                       temp=temp->next;
                       count++;
           }
           n1->next=temp->next;
           temp->next->prev=n1;
           temp->next=n1;
           n1->prev=temp;
                       
           }
}

void deletell(Node* &head, int position){
           Node* temp= head;
           if(position==1){
                       head=head->next;

           }
           else{
                       temp->next=temp->next->next;
           }
}

printll(Node* &head){
           Node* temp = head;
           while(temp!=NULL){
                       cout << temp->data << " ";
                       temp=temp->next;
           }
           cout << endl;
           
}

int main(){
           Node* n= new Node(73);
           int d, t, p, position;
           Node* head=n;
           Node* tail=n;
           cout << "enter the element to be added at head:";
           cin >>d;
           
           cout << "enter the element to be added at tail:";
           cin >>t;
           
           cout << "enter the element to be added anywhere:";
           cin >>p;
           
           cout << "enter the position:";
           cin >>position;
           
           insertAthead(head, d);
           insertAttail(tail, t);
           insertAtposition(head, position, p);
           cout <<"before deletion" << endl;
           printll(head);
           deletell(head,position);
           cout <<"after deletion" << endl;
           printll(head);
           
           
           return 0;
}

3. 循环链表（Circular Linked List）： 循环链表是一种没有预定义开始和结束的链表。您可以从任何节点开始。可以说，循环链表是一种单向链表，其中最后一个节点的下一个节点指向第一个节点（头节点）。

例如

代码

class Node{
           public:
                       int data;
                       Node* next;
                       
                       Node(){}
                       
                       Node(int val){
                                   data=val;
                                   next=NULL;
                       }
};

void insertAthead(Node* &head, int val){
           Node* temp=new Node(val);
           temp->next=head;
           head=temp;
}

void sortll(Node* head){
           Node* temp=head;
           
           if(temp>=temp->next){
                       
           }          
}

void printll(Node* &head){
           Node* temp =head;
           while(temp!=NULL){
                       cout << temp->data << " ";
                       temp=temp->next;
           }
           cout << endl;
}

int main(){
           Node* n1= new Node(10);
           Node* head= n1;
           int d1, d2, d3, d4, d5;
           cout << "enter values:" << endl;
           cin >> d1;
           cin >> d2;
           cin >> d3;
           cin >> d4;
           cin >> d5;
           
           insertAthead(head, d1);
           insertAthead(head, d2);
           insertAthead(head, d3);
           insertAthead(head, d4);
           insertAthead(head, d5);
           
           printll(head);

                       
           return 0;
}

4. 循环双向链表（Circular Doubly Linked List）： 它是循环链表和双向链表的组合。

让我们通过一个例子来理解

链表排序

比较第一个节点的数据与其他节点中的数据。如果第一个节点的数据大于其他节点的数据，则交换第一个节点和另一个节点的数据。迭代 1 结束后，第一个节点已排序。继续对第二个节点到最后一个节点执行相同的过程。

代码

void sort(node* head){
 struct node* I, *j; 
int temp;
for(i=start; i->next!=null; i=i->next){
    for(j=start; j->next!=null; j=j->next){
           If(i-> data > j->data){
temp=i->data;
i->data = j-> data;
j->data=temp;}
}
}

通过插入排序进行排序

代码

void insert sorted(node* head, int val){
node* temp = new node(val);
if(head==null || head->data >val){
temp-> next=head;
head=temp;}
node* p=head;
while(p->next!=null && p->next->data<val)
p=p->next= head->next;
head->next=temp;}

链表插入

  class Node{
           public:
                       int data;
                       Node* next;
                       
                       Node(){}
                       
                       Node(int val){
                                   data=val;
                                   next=NULL;
                       }
};

void insertAthead(Node* &head, int val){
           Node* temp=new Node(val);
           temp->next=head;
           head=temp;
}

void printll(Node* &head){
           Node* temp =head;
           while(temp!=NULL){
                       cout << temp->data << " ";
                       temp=temp->next;
           }
           cout << endl;
}

int main(){
           Node* n= new Node(10);
           int d1,d2,d3,position;
           cout << "enter the elements to be entered." << endl;
           cin >> d1;
           cin >> d2;
           cin >> d3;
           Node* head =n;
           Node* tail=n;
           insertAthead(head, d1);
           insertAthead(head, d2);
           insertAthead(head, d3);
           cout << "values inserted";
           printll(head);
           cout << "enter position to be deleted." << endl;
           cin >> position;
            deletell(head, position);
                       printll(head);
                       
           return 0;
}

链表删除

void delete(Node* &head,int position){

           Node * temp =head;
           int count=1;
           
           if(position==1){
                       head=head->next;
                       delete temp;
           }

           
           while(count<position -1){
                       temp=temp->next;
                       count++;
           }
           temp->next=temp->next->next;
           
}

链表数据查找

#include <stdio.h>
using namespace std;

class Node
{
           public:
           int data;
           Node* next;
};

void push(Node** head_p, int val)
{
           Node* new_node = new Node();

           new_node->data = val;

           new_node->next = (*head_p);

           (*head_p) = new_node;
}

bool search(Node* head, int x)
{
           Node* current = head;
           while (current != NULL)
           {
                       if (current->data == x)
                                   return true;
                       current = current->next;
           }
           return false;
}

int main()
{
           Node* head = NULL;
           int x = 30;
           bool answer;
           push(&head, 10);
           push(&head, 20);
           push(&head, 30);
           push(&head, 40);
           push(&head, 50);

           answer=search(head, 30);
           if(answer is true){
cout<< ?element found?<<endl;}
else{
cout << ?element not found?<<endl;}
           return 0;
}

链表应用

用于实现各种其他数据结构，如栈、队列和图。基于链表的真实生活示例是火车车厢系统，其中车厢可以插入链中的任何位置。

链表的优缺点

链表优点

链表提供了动态插入和删除节点的便利。用户可以通过在链表的最后、开头或中间插入节点，或者通过删除节点来增加或减少链表的大小，以满足他们的需求。
链表遵循高效的节点（数据）内存分配。在链表格式的数据存储中，节点不像数组那样连续存储；相反，节点存储在随机内存位置。这减少了内存浪费。我们无需预定义链表的大小。
链表为实现队列、图和栈等各种数据结构提供了简便的方法。
链表的删除和插入操作非常优化。与数组不同，我们无需移动或更改现有节点的位置，并且可以在链表的任何位置中间插入和删除节点。元素的移动是一个非常耗时的过程。
当处理大量数据且数据是非静态的（即随时间变化）时，链表的最大优势得以体现。由于链表节点的存储不是以规则/连续的方式进行的，我们可以将任何节点存储在任何位置。

链表缺点

在链表中，单个节点的两个部分是存储数据的部分和存储另一个节点地址的下一个部分。因此，即使要存储一个节点，我们也需要比在数组中存储一个元素更多的空间。
要访问特定节点，我们需要遍历它之前的节点；因此，链表的遍历是一个耗时的过程。例如，在给定的链表中，如果我们想访问 10，那么没有直接通往 12 的路径，我们需要访问 12 之前的所有节点，即 2、4、6、8，然后才能到达 12。

由于缺乏索引方法，我们无法直接访问链表中的特定节点。
单向链表无法反向遍历，但双向链表可以反向遍历，因为有前向指针可以向后遍历。
不建议使用链表作为数据结构来存储和共享少量数据。
理解链表的整体实现并不容易，因为它包含类、构造函数、对象甚至结构的概念。新手在不理解这些概念的情况下无法直接使用链表。

数组的优缺点

数组优点

数组数据结构实现简单。
与链表相比，访问数组中的元素非常容易。通过索引可以直接访问元素。
数组实现了其他数据结构，如队列、栈等。

数组缺点

存储在数组中的数据是静态的，这意味着我们无法在运行时更改数组的大小，就像在链表中一样。
我们必须超出数组中存储的元素数量。例如，如果数组的长度为五，则数组中不能存储超过五个元素。
我们必须指定要在数组中存储的元素的类型，因为数组的类型是指定的。例如，如果我们想在数组中存储整数类型的元素，那么应该将数组定义为整数类型，对于字符串、字符等其他数据类型也是如此。
元素存储在连续的内存位置，因此中间没有空隙来添加新元素。如果数组中有空隙并且我们想在数组之间插入一个元素，那么我们必须将其他元素推移以在该特定位置创建空间，这非常耗时。
如果分配的内存少于预留的内存，则会发生内存浪费。例如，如果我们声明了一个长度为 100 的数组，但只存储了 40 个元素。

在以下情况下，可以优先选择链表而非数组

当您不知道要处理的元素总数时，这是因为在数组中，我们必须预先定义数组的大小和长度，整个代码都应遵循此规则，除非在根部（即声明处）进行了更改。
当元素在运行时可能会增加或减少时。
当在末尾或开头位置插入和删除的概率更高时，就像在实现栈和队列时一样，通常会优先选择链表而非数组。正如我们之前讨论过的，我们必须移动元素才能在数组中添加新元素。

下一个主题Personal-cloud-storage-pcs

链表相对于数组的优缺点

数据结构

Array

数组类型

链表

链表类型

链表应用

链表的优缺点

链表优点

链表缺点

数组的优缺点

数组优点

数组缺点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

博客

链表相对于数组的优缺点

数据结构

Array

数组类型

链表

链表类型

链表应用

链表的优缺点

链表优点

链表缺点

数组的优缺点

数组优点

数组缺点

相关帖子

Arduino 与 Elegoo

最佳手机处理器

Adobe InDesign 版本

最小的奇数

密码强度条

最佳入门级科技工作

百货商店的优缺点

定义 Beam Search

FSM 机器

数据科学的优缺点

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器