数组与链表
目录
前言
数组和链表是两种数据结构,数组非常简单易用但是它有两个非常大的缺点,一个是数组一旦创建无法扩展,另一个则是数组的查找和删除的速度很慢.
链表改善了一些数组的缺点,但是同样的链表自身也存在一些自己的缺点.
本篇博客将为大家介绍一下这数组和链表特点及各自的优缺点.
阅读前的准备工作
大O表示法,一种粗略的评价计算机算法效率的方法.后面的内容会用到表示效率的方法.
1. 数组
我们按数组中的数组是否排序对数组进行划分,将数组分为无序数组和有序数组.无序数组中的数组是无序的,而有序数组中的数据则是升序或者降序排序的.
1.1 无序数组
因为无序数组中的数据是无序的,往数组中添加数据时不用进行比较和移动数据,所以往无序数组里面添加数据很快.无论是添加第一个数据还是第一万个数据所需的时间是相同的,效率为O(1).
至于查找和删除速度就没有那么快了,以数组中有一万个数据项为例,最少需要比较1次,最多则需要比较一万次,平均下来需要比较5000次,即N/2次比较,N代表数据量,大O表示法中常数可以忽略,所以效率为O(N).
结论:
- 插入很快,因为总是将数据插入到数组的空余位置.
- 查找和删除很慢,假设数组的长度为N,那么平均的查找/删除的比较次数为N/2,并且还需要移动数据.
1.2 有序数组
无序数组中存放的数据是无序的,有序数组里面存放的数据则是有序的(有可能是升序有可能是降序).
因为有序数组中的数据是按升序/降序排列的,所以插入的时候需要进行排序并且移动数据项,所有有序数组的插入速度比无序数组慢. 效率为O(N).
删除速度和无序数组一样慢 效率为O(N).
有序数组的查找速度要比无序数组快,这是因为使用了一个叫做二分查找的算法.
二分查找: 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列.
有一个关于二分查找的形象类比 -> 猜数游戏
假设要在0-100之间猜一个数,那么你第一个要猜的数字就是100的一半50的时候,你的朋友会告诉你这个数字比要猜的数字是大还是小,如果比数字大,你接下来要猜的数字就是50的一半25,你的朋友说比这个数字要大,那么你下面要猜的数字就是25-50中间的那个数37,以此类推...
使用二分查找可极大的提高查找的效率,假设一个有序数组有十亿个数据,那么查找到所需的数字,最多只需比较30次.
有序数组使用二分查找的效率为O(logN).有序数组也可以通过二分查找来新增和删除数据以提高效率,但是依然需要在新增/删除后移动数据项,所以效率依然会有影响.
总结:
- 有序数组的查找速度比无序数组高,效率为O(logN)
- 有序数组的删除和新增速度很慢,效率为O(N)
1.3 数组总结
数组虽然简单易用,但是数组有两个致命的缺点:
- 数组存储的数量有限,创建的过大浪费资源,创建的过小溢出
- 数组的效率比其他数据结构低
- 无序数组插入效率为O(1)时间,但是查找花费O(N)时间
- 有序数组查找花费O(logN)时间,插入花费O(N)时间
- 删除需要移动平均半数的数据项,所以删除都是O(N)的时间
2. 链表
数组一经创建大小就固定住了,无法修改,链表在这方面做出了改善,只要内存够用就可以无限制的扩大.
链表是继数组之后应用最广泛的数据结构.
2.1 链表的特点
链表为什么叫链表呢? 因为它保存数据的方式就像一条锁链
链表保存数据的方式很像上面的这一条锁链,每一块锁链就是一个链节点,链节点保存着自己的数据同时通过自己的next()方法指向下一个链节点. 链表通过链节点不断地调用next()方法就可以遍历链表中的所有数据.
在链表中,每个数据项都被包含在"链节点"(link)中,一个链结点是某个类的对象,这个类可以叫做Link.因为一个链表中有许多类似的链结点,所以有必要用一个不同于链表的类来表达链结点.
每个Link对象中都包含一个对下一个链结点引用的字段(通常叫做next).
链表本身的对象中有一个字段指向对第一个链结点的引用.
数据与链表查找数据的区别: 在数组中查找数据就像在一个大仓库里面一样,一号房间没有,我们去二号房间,二号房间没有我们去三号房间,以此类推.. 按照地址找完所有房间就可以了.
而在链表中查找数据就像单线汇报的地下工作者,你是孤狼你想要汇报点情报给你的顶级上司毒蜂,但是你必须先报告给你的接头人猪刚鬣,猪刚鬣在报告给它的单线接头人土行孙,最后由土行孙报告给毒蜂.只能一个找一个,这样最终完成任务.
2.2 Java代码
链节点类:
/** * @author liuboren * @Title: 链节点 * @Description: * @date 2019/11/20 19:30 */ public class Link