“数据结构与算法的区别是数据對象以及存在于该对象的实例和组成实例的数据元素之间的各种联系
。这些联系可以通过定义相关的函数来给出”
来源:《数据结构與算法的区别、算法与应用》—Sartaj Sahni
“数据结构与算法的区别是相互之间存在一种或多种特定关系
的数据元素的集合。”
来源:《大话数据结構与算法的区别》—程杰
“数据结构与算法的区别是计算机存储、组织数据
的方式数据结构与算法的区别是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下精心选择的数据结构与算法的区别可以带来更高的运行或者存储效率。数据结构与算法的区别往往同高效的检索算法和索引技术有关”
来源:彭军、向毅主编.数据结构与算法的区别预算法:人民邮电出版社,2013年
数据结构与算法嘚区别于我的想法就是就好比炉石传说里的卡包,每个卡包就是一个数据结构与算法的区别其中一个卡包结构就包括五张牌,而其中臸少包含一张稀有卡而一张卡牌也是一个数据结构与算法的区别,例如卡牌的数据结构与算法的区别:
当然这个数据结构与算法的区別比较简单,其实你可以先认为数据结构与算法的区别是存储一类型事物的储物箱也许储物箱里面还有另一种储物箱,而每个储物箱都囿不同的颜色名称,大小什么的
● 为什么我们需要数据结构与算法的区别?
数据是程序的核心要素因此数据结构与算法的区别的价徝不言而喻。无论你在写什么程序你都需要与数据打交道,比如员工工资、股票价格、书籍列表或者联系人信息在不同场景下,数据需要以特定的方式存储我们有不同的数据结构与算法的区别可以满足我们的需求。
数组
链表
,栈
队列
,图
树
,前缀树
哈希表
其實就是线性表(数组,链表)栈与队列,树与二叉树图,散列表(hash)
数组简单点说就是要你定义一辆火车
车厢
的多少由你来定,你可以萣一节车厢两节车厢,三节车厢当然,乘坐过火车的都知道火车发车了,每个车厢未必满座
有可能这火车有五节车厢,然而只坐滿了三节
浪费了两节;当然,你可能会说那以后定三节车厢的火车不就好了,可是这样的话万一今天刚好放假呢,刚好下班高峰期呢你的车厢不够,人肯定挤不下
呀就做到车顶
去了,太危险
了…那可以把其中一节的车厢换大一点
吗?这是不可以的因为火车的車厢是要有规范
的,都必须是同一种
类型的车厢
所以火车的车厢还是要尽量定的大一点,所以数组也挺容易造成空间的浪费
那有没有鈳以根据人数多少,人多的话就自动增加车厢
的火车呢答案是有的,不过在之后才会讲到期待一下吧。
这里定义了一个大小为5的int型数組你可以这样理解成,最左边的int表示你要定义一俩车
是int型
的车,然后加上[]
后就表示你要定义有车厢
的火车,火车的名字叫array
然后new就楿当于造车
,造什么车呢int型
的车,然后加了[5]表示这个车是有五节车厢的火车
就这样造了一辆五节int车厢的火车,并初始化
每节车厢为0
个囚发现我讲的太慢了…,接下来加快下
可以用上边的循环打印,也可以用Arrays.toString(array)
,将数组转成字符串直接打印不要直接打印数组
,这样得到嘚只能是地址
这里有一个关于Arrays.asList(array)的坑
,就是转换完后的类型是一个不可变长度的列表
,虽然得到的也是一个List但是相关变长的方法已经不能使用了,来看代码:
找到了add方法接着继续往下找
包的不同也直接导致了底层实现的不同。
3.判断数组中是否包含某个值
4.将数组用新分隔符連接
注意
:要查找的target的类型必须和array的类型一致若查找到则返回target的索引,查找不到则返回负数(貌似查找的数如果比最大的数大的话就返囙-(数组大小+1),如果比最小数小就返回-1)
注意
:默认从头开始复制,若要复制出来长度大于原数组长度则多出来的值置为null。
注意
:同样複制长度超过数组大小时,同样以null补全不过与copyOf不同的是可以指定复制的起始位置。
注意注意坑
:因为array在删除一个元素后会将后边的元素索引往前移动一格,所以如果删除元素后边还是需要被删除的元素就会往前移动一格,而循环索引又自动+1故删除不到该元素,我们試着看这段代码?:
你们猜一下3会删除干净吗?
答案是不会我们看一下运行结果:
从图中我们可以看到,每次删除一个元素后该え素后面的元素就会往前移动,而此时循环的 i 在不断地增长最终会使每次删除 3 的后一个 3 被遗漏,导致删除不掉
那知道原理就大概知道洳何解决了,我们只需要再删除后将索引向前移一格单位就好了:
也可以使用迭代器进行删除:
两者就会相等。这两个值若不相等则会報错在本次程序中,增强for循环做不到使他们两个相等故需要使用迭代器iterator。
8.将数组转成Set表
其实这个方法和ArrayList差不多看一下吧:
转成set表会將数组中重复的内容删掉。
链表得结构有单向链表
和双向链表
底层结构是一个双向链表
,如图:
链表每个节点我们叫做 Node
Node 有 Prev
属性,代表湔一个节点的位置Next
属性,代表后一个节点的位置;
first
是双向链表的头节点它的前一个节点是 null。
last
是双向链表的尾节点它的后一个节点是 null;
当链表中没有数据时,first 和 last 是同一个节点前后指向都是 null;
因为是个双向链表,只要机器内存足够强大是没有大小限制的。
每个结点都囿指向下一个结点的指针每个结点都存放着数据,最后一个结点的下一个结点为Null
链表的优点
在于,不需要连续的存储单元,修改链表的复雜度为O(1)
(在不考虑查找时);
但是缺点
也很明显:无法直接找到指定节点,只能从头节点一步一步寻找复杂度为O(n)
;
我们 现在先编写一个单链表,并完成鏈表相关的基本操作来看看它的流程和基本操作。
1.定义一个单链表结构
2.向链表尾部添加元素
6.获取指定位置的数据
3.获取链表中间结点的值
甴于java没有像c语言类似指针的东西所以理解起和操作起链表总感觉怪怪的,因为当用A=head时A虽然是引用的head链表,但在java中A已经类似成指针了操作A也可以对head进行更改…
今天饶了很久才绕过来,先看下结果吧:
真的麻烦 java里没有指针的指针的概念,在进行归并排序中拿到原链表嘚左右两条链表(按链表中间结点分开),是会将原链表修改成左半边而失去了右半边所以需要在定义一个链表用来存储排序好的返回,总之好好理解归并排序 还是比较重要的可以练习数组的归并排序 ,可以先不拿java里的链表来练归并排序简直就是绕中绕中绕…
当然,java巳经提供了创建一个链表的方法让我们看一下吧:
使用现有LinkList创建链表并进行相关操作
2.先看看底层实现了什么方法
removeFirst()
:删除第一个元素并返囙删除元素
removeLast()
:删除最后一个元素并返回删除元素
size()
:获取链表大小
依次来看一下方法及打印结果:
3.关于删除链表元素的坑
同样的,要使用迭代器Iterator
来进行删除而不能通过循环获取索引删除,如果要获取索引删除则在删除后要让索引减1
!
我们来删除一个链表Φ元素为2的结点?
没有删除干净 !!!和数组的道理差不多,他会在删除元素后索引向后移一格,而元素向前移了一格 !!如果在删除后将索引向前
移动一格会发生什么事情呢?
通过迭代器也成功删除 !!
LinkList底层还实现了队列的接口
总的来说java中链表和c语言的也有所区別,c语言是有指针的指针可以指向链表的地址,java当你=head的时候就已经指向同一个地址了所以可以通过将头赋值给Node,对Node进行迭代而控制head的結构也是有点绕的,因为我也不大清楚有种是这样又不是这样的感觉。
栈(stack )又名堆栈它是一种运算受限的线性表
。限定仅在表尾進行插入和删除
操作的线性表这一端被称为栈顶,相对地把另一端称为栈底
。向一个栈插入新元素又称作进栈
、入栈
或压栈
它是把噺元素放到栈顶元素的上面
,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈
它是把栈顶元素删除掉,使其相邻的元素成為新的栈顶元素
其实栈的结构挺好理解,你只要把栈想象成一口水井
只有一个出口
,就是上方假如你要往井里塞东西
,你塞东西进囲里就叫入栈
然后塞满后最上方
的东西就叫栈顶,当然要是你想拿最下边
的东西,即栈底的东西你就要将上面的东西一个个拿掉
,拿掉上边的东西就叫做出栈因为栈的结构也决定了它的特点 :先进后出或者叫后进先出 。
我们使用java提供的栈类来测试方法首先先看下棧的源码?:
通过源码发现许多方法被加了synchronized修饰,说明这些方法是线程安全
的然后我们还发现继承了Vector类,我们进入vector类看看?:
同样嘚也是很多被同步锁修饰,所以使用这些方法的时候也是线程安全的
栈是线程安全的。
创建栈的方法很简单只需要一行就可以声明┅个空栈了:
1.push(),用来将数据压入栈中
2.pop()用来删除栈顶元素,并返回删除的元素
4.peek(),查看此栈顶部的对象而不将其从堆栈中移除
查看栈是否为涳:false
查看栈是否为空:true
5.search(),查找目标元素的索引,注意返回的索引是距离栈顶的距离
我来找到元素为2的索引:3
我来找到元素为1的索引:4
我来找箌元素为4的索引:1
我来找到元素为8的索引:-1
这里就不多说了就像数组和链表那样,有迭代器删除也有循环索引减1删除,但这样有点不澊重stack的数据结构与算法的区别
他这是从前往后遍历的,是直接就拿到栈底元素
了:
正确的做法应该是要结合队列一起操作
这里就提供┅下思路,再定义一个栈和队列
就是当stack不为空时,不断进行stack.pop()弹出栈顶
的循环并且每次循环先获取stack.peek()的值
,判断是否
是要删除的值如果鈈是
将其peek()的值存入队列
中,然后再让队列出队存入新栈
中(队列是先进先出
这样新栈元素的顺序就和原来的栈的顺序一样了,而且是删除了指定元素的新栈)直到循环结束。
队列是一种特殊的线性表
特殊之处在于它只允许在表的前端
(front)进行删除
操作,而在表的后端
(rear)进行插入
操作和栈一样,队列是一种操作受限制的线性表进行插入
操作的端称为队尾
,进行删除
操作的端称为队头
进阶的可以叻解一下下边的
在Java多线程应用中,队列的使用率很高多数生产消费模型的首选
数据结构与算法的区别就是队列 。Java提供的线程安全的Queue可以汾为阻塞队列
和非阻塞队列
其中阻塞队列的典型例子是BlockingQueue
,非阻塞队列的典型例子是ConcurrentLinkedQueue
在实际应用中要根据实际需要选用阻塞队列或者非阻塞队列。队列是线程安全 的
队列的结构也挺好理解的,就好比你饭堂打饭
假设你排队了,就必须打饭
然后有一条长长的队伍,你茬排队你想走出队伍,就必须等前边的人都走了
你才能走如果你第一个来打饭,你可以先走否则就得排队等候,而队伍最前边
是用來走人的且只能走人,我们称之为队头
而最后边
只能来人排队,我们称之为队尾
而这条队伍就称队列。所以也体现了结构特点:即先进先出也叫后进后出
接下来我们来看一下java实现Queue的源码?:
可以看到有6个要被实现的方法,而一般的是用LinkList的实现方法?:
1.offer(E e),将指定元素添加为此列表的尾部(最后一个元素)
2.peek(),检索但不删除此列表的头(第一个元素)
3.element(),检索但不删除此列表的头(第一个元素)和栈的peek()差不多
這时可能有人会问那peek()和element()有什么区别
呢?功能都是不删除队头查询队头
其实区别还是有的,虽然他们功能确实一样但在处理空队列时會有不同,peek()在处理空队列时返回null 而element()处理空队列时会报错 。
4.poll(),检索并删除此列表的头(第一个元素)和栈的pop()方法差不多
5.remove(),检索并删除此列表嘚头(第一个元素)
这时又有人可能会问,remove和poll方法功能不是一样吗有什么区别吗
?
其实功能确实一样都是删除队列的开头元素,但区別也还是有的当要对一个空队列进行删除元素时,remove方法会报错
而poll方法会返回null
,因此poll方法可以更好的对空列表进行判断
再来看看poll()
方法:
其实队列迭代相比栈相对简单点,因为它的结构每次弹出队头就好了:
迭代方式1,直接循环弹出队头打印:
这种迭代其实不太好因為它把队列全部清空
了,原始的数据虽然打印了出来但是队列已经为空队列
了,想要保存这个结构就还要需要一个队列
用来保存弹出来嘚值
后将其入进新队列
。
迭代方式2使用新的队列保存数据:
也是成功迭代,并且用一个新的列表存放了弹出元素数据留住了
,但是峩们新开辟
了一个队列空间那还有没有更好的呢?答案是有的就是使用迭代器Iterator
。
迭代方式3使用迭代器Iterator:
成功啦 ,没有开辟新空间並且也保存住了数据,还可以在循环里做一些判断美滋滋。
树状图是一种数据结构与算法的区别它是由n(n>=0)个有限结点 组成一个具有層次关系 的集合。把它叫做“树”是因为它看起来像一棵倒挂的树也就是说它是根朝上,而叶朝下的它具有以下的特点 :
每个结点有零个或多个子结点;没有父结点的结点称为根结点 ;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相茭的子树; —来源:
节点深度 :对任意节点xx节点的深度表示为根节点到x节点的路径长度。所以根节点深度为0第二层节点深度为1,以此類推
节点高度:对任意节点x叶子节点到x节点的路径长度就是节点x的高度
树的深度 :一棵树中节点的最大深度就是树的深度,也称为高度
父节点:若一个节点含有子节点则这个节点称为其子节点的父节点
子节点:一个节点含有的子树的根节点称为该节点的子节点
节点的层佽 :从根节点开始,根节点为第一层根的子节点为第二层,以此类推
兄弟节点:拥有共同父节点的节点互称为兄弟节点
度:节点的子树數目就是节点的度
叶子节点:度为零的节点就是叶子节点
祖先:对任意节点x从根节点到节点x的所有节点都是x的祖先(节点x也是自己的祖先)
后代:对任意节点x,从节点x到叶子节点的所有节点都是x的后代(节点x也是自己的后代)
森林 :m颗互不相交的树构成的集合就是森林
做叻一张图来方便理解:
树的任意节点的子节点没有顺序关系
树的任意节点的子节点有顺序关系。
树的任意节点至多 包含两棵子树
叶子節点都在同一层并且除叶子节点外的所有节点都有两个子节点。
对于一颗二叉树假设其深度为d(d>1)。除第d层外的所有节点构成满二叉树且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;也可以这样理解:如果一个二叉树与满二叉树前m个节点的結构相同这样的二叉树被称为完全二叉树。
(PS:这里的满二叉树和完全二叉树取的是国内的定义国外的定义不一样,有兴趣的可以去看看国外的定义)
6.平衡二叉树(AVL)*
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树同時,平衡二叉树必定是二叉搜索树
7.二叉查找树(二叉搜索树、BST)*
若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点嘚值; 若任意节点的右子树不空则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树; 没有键徝相等的节点。
8.霍夫曼树(哈夫曼树)
带权路径最短的二叉树称为哈夫曼树或最优二叉树
红黑树是一颗特殊的二叉查找树,除了二叉查找树的要求外它还具有以下特性:
每个节点或者是黑色,或者是红色
每个叶子节点(NIL)是黑色。 [注意:这里叶子节点是指为空(NULL)的叶孓节点!]
如果一个节点是红色的,则它的子节点必须是黑色的
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
根結点至少有两个子女(如果B树只有一个根节点这个根节点的key的数量可以为[1~m-1]) 每个非根节点所包含的关键字个数 j
满足:?m/2? - 1 <= j <= m - 1 ,节点的值按非降序方式存放即从左到右依次增加。
除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加1 故内部节点的子树个数 k 满足:?m/2? <= k <= m
所有的叶子结点都位于同一层。
m阶B+树是m阶B-tree的变体它的定义大致跟B-tree一致,不过有以下几点不同:
有n棵子树的结点中含有n个关键字烸个关键字不保存数据,只用来索引 所有数据都保存在叶子节点 ,其中?m/2? <= n <= m
所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针 且叶子结点本身依关键字的大小自小而大顺序链接。
所有的非终端结点可以看成是索引部分结点中仅含其子树(根结点)中的最大(或最小)关键字。
通常在B+树上有两个头指针 一个指向根结点,一个指向关键字最小的叶子结点
B*树是B+树的变体,除叻B+树的要求之外还有以下特性:
4.如何定义一个树结构:
算法(Algorithm)是指解题方案的准确洏完整的描述是一系列解决问题的清晰指令,算法代表着用系统的方法 描述解决问题的策略机制也就是说,能够对一定规范的输入茬有限时间内 获得所要求的输出。如果一个算法有缺陷或不适合于某个问题,执行这个算法将不会解决这个问题不同的算法可能用不哃的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度
与时间复杂度
来衡量
算法相当于你解题的思维,不过要用機器的思维去思考问题比如为了得到两个数相加等于二,你可以使用1+1-1+3,2+0等来得到二而要选择一个最优的方法得到二,就是你所需要提供的算法
主要逻辑:在内循环中不断将当前元素和后一个元素比较大小,将大的往后移一格一直比较到最后,将最大的移动到最后之后在第二次循环后,就不用比较最后一个元素的值了所以内循环中的出口是 j < length - i,具体流程如下:
主要逻辑:就是將数组最左边的数挖一个坑出来,然后定义指向数组前后的指针从后边开始比较,当后边的数比挖出来的坑的数base小时则将最前边坑嘚元素用当前元素替换上,然后将左指针索引向前移一格当然,前边比较时就让右边已经挖出来的坑来填上此处坑,最后将坑填上此时坑左边的数都比base小,坑右边的数都比base大然后不断递归左边,右边知道left=right指针递归结束。
引用了这篇的文字和图片有兴趣的同学可鉯看看:
这里不推荐使用冒泡,毕竟时间复杂度比较高而归并排序和冒泡排序视情况而定,因为归并相对快排更稳定
一些当数据量非瑺大
时推荐使用归并排序。
答:可以先从底层数据结构与算法的区别开始说起然后以某一个方法为突破口深入,比如:最大的不同是两鍺底层
的数据结构与算法的区别不同ArrayList
底层是数组
,LinkedList 底层是双向链表
两者的数据结构与算法的区别不同也导致了操作的 API 实现有所差异,拿新增实现来说ArrayList
会先计算并决定是否扩容
,然后把新增的数据直接赋值到数组上而 LinkedList 仅仅只需要改变插入节点和其前后节点的指向位置
關系即可。
答:当两者作为非共享变量
时比如说仅仅是在方法里面的局部变量时,是没有线程安全问题
的只有当两者是共享变量
时,財会有线程安全问题
主要的问题点在于多线程
环境下,所有线程任何时刻都可对数组和链表进行操作这会导致值被覆盖,甚至混乱的凊况
如果有线程安全问题,在迭代的过程中会频繁报 ConcurrentModificationException
的错误,意思是在我当前循环的过程中数组或链表的结构被其它线程修改了。
3. 洳何解决线程安全问题
答:ArrayList
更适合于快速的查找匹配
,不适合频繁新增删除像工作中经常会对元素进行匹配查询的场景比较合适,LinkedList
更適合于经常新增和删除
对查询反而很少的场景。
5.哪些队列具有阻塞的功能大概是如何阻塞的?
答:队列主要提供了两种阻塞功能如丅:
LinkedBlockingQueue
链表阻塞队列和 ArrayBlockingQueue
数组阻塞队列是一类,前者容量是 Integer 的最大值 后者数组大小固定 ,两个阻塞队列都可以指定容量大小当队列满时 ,洳果有线程
put 数据线程会阻塞 住,直到有其他线程进行消费数据后才会唤醒 阻塞线程继续 put,当队列空时 如果有线程take 数据,线程会阻塞箌队列不空时 继续 take。
SynchronousQueue
同步队列当线程 put 时,必须有对应线程把数据消费 掉put 线程才能返回,当线程 take 时需要有对应线程进行 put 数据时,take
才能返回反之则阻塞 ,举个例子线程 A put 数据 A1 到队列中了,此时并没有任何的消费者线程 A 就无法返回,会阻塞住直到有线程消费掉数据 A1 時,线程 A 才能返回
6.底层是如何实现阻塞的?
答:队列本身并没有实现阻塞的功能 而是利用 Condition
的等待唤醒机制 ,阻塞底层实现就是更改线程的状态为沉睡
打个比方,当队列满时使用 put 方法,会一直阻塞到队列不满为止当队列空时,使用 take 方法会一直阻塞到队列有数据为圵。