数组和链表（数组和链表的应用场景）

本篇文章给大家谈谈数组和链表，以及数组和链表的应用场景对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、链表和数组的区别是什么?
• 2、数组和链表的区别,各有何优缺点
• 3、数组内包含链表吗
• 4、链表和数组的优缺点

链表和数组的区别是什么?

1、内存不同

数组静态分配内存，链表动态分配内存。

2、连续情况不同

数组在内宴裂态存中连续，链表不连续。

3、元素位置不同

数组元素在栈区，链表元素在堆区。

4、复杂度不同

数组利用下标定位，时间复杂度为晌源O(1)，链表定位元素时间复杂度O(n)；数组插入或删源搭除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

数组和链表的区别,各有何优缺点

链表与数组的区别

（1）数组的元素个数是固定的,而组成链表的结点个数可按需要增减；

（2）数组元素的存诸单元在数组定义时分配，链表结点的存储单元在程序执行时动态向系统申请；

（3）数组中的元素顺序关系由元素在数组中的位置(即下标)确定,链表中的结点顺序关系由结点所包含的指针来体现。

（4）对于不是固定长度的列表,用可能最大长度的数组来描述，会浪费许多内存空间。

（5）对于元素的插人、删除操作非常频繁的列表处理场合,用数组表示是不适宜的。若用链表实现，会使程序结构清晰，处理的方法也较为简便。

数组的优游搏点

随机访问性强

查找速度快

数组的缺点

插入和删除效率低型吵

可能浪费内存

内存空间要求高，必须有足卜磨侍够的连续内存空间。

数组大小固定，不能动态拓展

链表的优点

插入删除速度快

内存利用率高，不会浪费内存

大小没有固定，拓展很灵活。

链表的缺点

不能随机查找，必须从第一个开始遍历，查找效率低

[img]

数组内包含链表吗

数组和链表是数据结构中最基础的两种结构,其他的都备裂是由这两者转吵弯化而来；

因此，掌握这两种结构至关重要！下面，时光就带大家来学习一下数组和链表；

线性表是具有相同类型的n（=0）个数据元素的有限序列（a0,a1,a2,…,an），ai是表项，n是表长度；

那么为什么要提到线性表呢？

因为数组和链表都是线性表的结构，只不过它们的存储方式不一样；

根据存储方式不同，可将线性表分为顺序表和链式表；

线性表是数据结构中的逻辑结构。可以存储在数组上，也可以存储在链表上。

一句话，用数组来存储的线性表就是顺序表。

数组：在内存中，是一块连续的内存区域；

链表：是由不连续的内存空间组成；

数组优点：随机访问性强，查找速度快（连续内存空间导致的）；

数组缺点：插入和删除效率低 可能浪费内存 内存空间要求高，必须有足够的连续内存空间。数组大小固定，不能动态拓展

链表的优点：插入删除速度快 内存利用率高，不会浪费内存 大小没有固定，拓展很灵活。（每一个数据仿碰闭存储了下一个数据的地址，增删效率高）

链表的缺点：不能随机查找，必须从第一个开始遍历，查找效率低

说了这么多，让我们用代码来写一个数组和链表。

数组：

1，先写一个实体类DynamicArray；

主要包括属性有数组容量，结点数据和数组长度；

1packagecom.java.model;23publicclassDynamicArray {4//动态数组最大容量5publicfinalstaticintcapacity = 100;6 7//顺序表的结点数据8publicint[] data;9//顺序表的长度，用来标识数组中的元素个数10publicintsize;11 12//构造函数13publicDynamicArray(int[] data,intsize) {14this.data =data;15this.size =size;16}17}

2，再写数组方法类DynamicArrayDao；

主要包括数组的各种操作方法，插入、查找等；

1packagecom.java.dao;23importcom.java.model.DynamicArray; 4importstaticcom.java.model.DynamicArray.capacity;56publicclassDynamicArrayDao {7 8//初始化数组9publicDynamicArray Init_Array(){10//数组数据域初始化11int[] data1=newint[capacity];12 13//DynamicArray初始化14 DynamicArray myArray=newDynamicArray(data1,0);15 16//数组赋值17for(inti=0;icapacity;i++){18 myArray.data[i]=0;19}20returnmyArray;21}22 23//插入指定值24publicvoidPushBack_Array(DynamicArray array,intvalue){25if(array==null){26return;27}28//如果线性表容量小于或等于数组容量29if(array.size==capacity){30return;31}32//插入元素33 array.data[array.size]=value;34 array.size++;35}36 37//根据位置删除38publicvoidRemoveByPos_Array(DynamicArray array,intpos){39if(array ==null){40return;41}42//判断位置是否有效43if(pos 0 || pos =array.size){44return;45}46//删除元素47for(inti = pos; i array.size -1; i ++){48 array.data[i] = array.data[i + 1];49}50 array.size--;51}52 53//查找元素,返回该值第一次出现时对应的下标位置54publicintFind_Array(DynamicArray array,intvalue){55if(array==null){56return-1;57}58//找到该值第一次出现的位置，-1表示没有找到；59intpos=-1;60for(inti=0;iarray.size;i++){61if(array.data[i]==value){62 pos=i;63break;64}65}66returnpos;67}68 69//根据位置查找到某个元素70publicintAt_Array(DynamicArray array,intpos){71if(array==null){72return-1;73}74returnarray.data[pos];75}76 77//根据值删除78publicvoidRemoveByValue_Array(DynamicArray array,intvalue){79if(array==null){80return;81}82//首先找到该值对应的数组下标83intpos=Find_Array(array,value);84//调用根据位置删除的方法85RemoveByPos_Array(array,pos);86}87 88//打印89publicvoidPrint_Array(DynamicArray array){90if(array==null){91return;92}93for(inti=0;iarray.size;i++){94 System.out.print(array.data[i]+",");95}96}97 98//清空数组99publicvoidClear_Array(DynamicArray array){100if(array==null){101return;102}103for(inti=0;iarray.size;i++){104 array.data[i]=0;105}106 array.size=0;107}108 109//获得动态数组当前元素个数110publicintSize_Array(DynamicArray array){111if(array==null){112return-1;113}114returnarray.size;115}116}

3，主函数Main；

包括测试各种函数等；

1packagecom.java.main;23importcom.java.dao.DynamicArrayDao; 4importcom.java.model.DynamicArray; 5importstaticcom.java.model.DynamicArray.capacity;67publicclassDynamicArrayMain {8publicstaticvoidmain(String[] args) {9 DynamicArrayDao dynamicArrayDao=newDynamicArrayDao();10//初始化动态数组11 DynamicArray myArray=dynamicArrayDao.Init_Array();12 System.out.println("初始化动态数组:");13//获取容量14 System.out.println("数组容量:"+capacity);15 System.out.println("数组实际大小:"+dynamicArrayDao.Size_Array(myArray));16//插入元素17for(inti=0;i10;i++){18dynamicArrayDao.PushBack_Array(myArray,i);19}20System.out.println();21 22 System.out.println("插入元素之后:");23//获取容量24 System.out.println("数组容量:"+capacity);25 System.out.println("数组实际大小:"+dynamicArrayDao.Size_Array(myArray));26System.out.println();27 28//打印插入元素29 System.out.println("打印插入的元素:");30dynamicArrayDao.Print_Array(myArray);31System.out.println();32 33//根据元素位置删除元素34 dynamicArrayDao.RemoveByPos_Array(myArray,2);35//根据元素值删除元素36 dynamicArrayDao.RemoveByValue_Array(myArray,7);37System.out.println();38 39//打印删除后的数组40 System.out.println("打印删除后的元素:");41dynamicArrayDao.Print_Array(myArray);42System.out.println();43 44//查找元素为5的位置45System.out.println();46 System.out.print("元素5的位置为: ");47intpos=dynamicArrayDao.Find_Array(myArray,5);48System.out.println(pos);49 50//查找位置为7的元素值51System.out.println();52 System.out.print("位置为7的元素为: ");53intvalue=dynamicArrayDao.At_Array(myArray,7);54System.out.println(value);55 56//获取容量57System.out.println();58 System.out.println("此时的数组容量:"+capacity);59 System.out.println("此时的数组实际大小:"+dynamicArrayDao.Size_Array(myArray));60System.out.println();61}62}

运行效果：

链表：

1，先建立链表结点以及整个链表的实体类；

这里有两个实体类：

LinkNode是结点，包括结点的数据域和指针域；

LinkList是整个链表，包括头结点以及链表元素个数；

1packagecom.java.model;23publicclassLinkNode {4//链表结点的数据域5publicObject data;6//链表结点的指针域7publicLinkNode next;8 9publicLinkNode() {10super();11//TODO Auto-generated constructor stub12}13 14//构造方法15publicLinkNode(Object data, LinkNode next) {16super();17this.data =data;18this.next =next;19}20 21}

1packagecom.java.model;23publicclassLinkList {4//链表的头结点5publicLinkNode head;6//链表的元素个数7publicintsize;8 9publicLinkList() {10super();11//TODO Auto-generated constructor stub12}13 14///构造方法15publicLinkList(LinkNode head,intsize) {16super();17this.head =head;18this.size =size;19}20 21}

2，再写链表方法类LinkListDao；

1packagecom.java.dao;23importcom.java.model.LinkList; 4importcom.java.model.LinkNode;56publicclassLinkListDao {7//初始化链表8publicLinkList Init_LinkList(){9//设置头结点的指针域和数据域10 LinkNode node=newLinkNode(0,null);11 LinkList list=newLinkList(node,0);12returnlist;13}14//指定位置插入15publicvoidInsert_LinkList(LinkList list,intpos, Object data){16//判断list是否有效17if(list==null){18return;19}20//判断data是否有效21if(data==null){22return;23}24//判断位置pos是否有效25if(pos0 || poslist.size){26//在链表的尾部插入27 pos =list.size;28}29 30//第一步，创建新的结点，也就是待插入的结点31 LinkNode newNode=newLinkNode(data,null);32//第二步，找到待插入结点前面一个结点pCurrent，并使其等于list的头结点33 LinkNode pCurrent=list.head;34for(inti = 0 ; i pos ; i++){35 pCurrent=pCurrent.next;36}37//第三步，新结点入链表，进行插入操作38 newNode.next=pCurrent.next;39 pCurrent.next=newNode;40//第四步，链表的size要加141 list.size++;42 43}44//删除指定位置的值45publicvoidRemoveByPos_LinkList(LinkList list,intpos){46if(list==null){47return;48}49if(pos0||pos=list.size){50return;51}52//第一步，找到待删除结点的前面一个结点pCurrent53 LinkNode pCurrent=list.head;54for(inti = 0; i pos; i++) {55 pCurrent=pCurrent.next;56}57//第二步，进行删除操作58 pCurrent.next=pCurrent.next.next;59//第三步，链表的size要减160 list.size--;61}62//获得链表的长度63publicintSize_LinkList(LinkList list){64returnlist.size;65}66//查找指定元素的位置67publicvoidFind_LinkList(LinkList list, Object data){68//注意这里要从头结点的下一个结点开始，因为头结点不存放数据信息69 LinkNode pCurrent=list.head.next;70for(inti = 0; i list.size; i++) {71if(pCurrent.data==data){72 System.out.print(i+",");73}74 pCurrent=pCurrent.next;75}76}77//返回第一个结点元素的值78publicObject Front_LinkList(LinkList list){79returnlist.head.next.data;80}81//打印链表结点82publicvoidPrint_LinkList(LinkList list){83if(list==null){84return;85}86 LinkNode pCurrent=list.head.next;87for(inti = 0; i list.size; i++) {88 System.out.print(pCurrent.data+",");89 pCurrent=pCurrent.next;90}91}92 93}

3，主函数Main；

测试各种方法类；

1packagecom.java.main;23importcom.java.dao.LinkListDao; 4importcom.java.model.LinkList;56publicclassLinkListMain {7publicstaticvoidmain(String[] args) {8 LinkListDao linkListDao=newLinkListDao();9//创建链表10 LinkList list=linkListDao.Init_LinkList();11 12//数据插入链表13 linkListDao.Insert_LinkList(list, 0, "A");14 linkListDao.Insert_LinkList(list, 1, "B");15 linkListDao.Insert_LinkList(list, 2, "C");16 linkListDao.Insert_LinkList(list, 3, "D");17 linkListDao.Insert_LinkList(list, 4, "D");18 19//打印链表20 System.out.println("插入数据之后的链表为:");21linkListDao.Print_LinkList(list);22System.out.println();23 24//删除指定位置的值25 linkListDao.RemoveByPos_LinkList(list, 2);26 27//打印链表28 System.out.println("删除元素C之后的链表为:");29linkListDao.Print_LinkList(list);30System.out.println();31 32//获得链表长度33 System.out.println("链表长度为:");34System.out.println(linkListDao.Size_LinkList(list));35 36//查找值为3的位置37 System.out.println("值为D的位置为:");38 linkListDao.Find_LinkList(list, "D");39System.out.println();40 41//返回第一个结点元素的值42 System.out.println("第一个结点元素为:");43System.out.println(linkListDao.Front_LinkList(list));44}45}

运行结果：

文中代码格式是仿照MVC模式写的，建议大家也这样写，比较整齐我感觉。

这次就分享到这里了，后续还有一系列的数据结构的文章哦，请大家期待！

右下角点个再看吧！蟹蟹哦~

链表和数组的优缺点

链表和数组作为算法中的两个基本数据结构，在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据，但又各有各的特点。

数组的优势，在于可以方便的遍历查找需要的数据。在查询数组指定位置（如查询数组中的第4个数据）的操作中，只需要进行1次操作即可，时间复杂度为O(1)。但是，这种时间上的便利性，是因为数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，本质是指针在内存中的定向偏移。然而，当需要对数组成员进行添加和删除的操作时，数组内完成这类操并缓宽作的时间复杂度则变成了O(n)。

链表的特性，使其在某些操作上比数组更加高效。例如当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。另外，因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。除绝亮此之外，链表还是很多算法的基础，最常见的哈希表哪亮就是基于链表来实现的。基于以上原因，我们可以看到，链表在程序设计过程中是非常重要的。本文总结了我们在学习链表的过程中碰到的问题和体会。

关于数组和链表和数组和链表的应用场景的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。