最近归零后重新学习的数据结构,根据同事推荐的某老师的数据结构视频学习后有总醍醐灌顶的感觉.总结学习后一些理解和想法.
(注: 老师是用java实现的一些,目的是了解原理,而不是实现java里面的一些数据结构)
数组
对于最常用的数据结构之一的 动态数组 来说.基于其还是实现了 栈 还有 队列 以及 循环队列.
动态数组原理其实很简单,让我唯一觉得有意思的是它的重新分配容量的机制.需要扩容的时候,很明显这个时候的扩容条件就是,当前元素个数 == 容量.这个时候就扩容为原来的两倍.而在缩小容量的时候,选择的时机的却是 当前元素个数 / 4 == 容量的时候.一开始我还在困惑,为什么要选择是当前元素个数是容量的 1/4 的时候呢,而不是 1/2 的时候.不过呢,这个问题老师也很快给了解答,因为如果在选择 1/2 那么,假如一开始申请了10个容量,后来,我删除最尾端元素之后,只剩下5个的时候,删除操作本来应该是O(1)的时间复杂度,这个时候就触发了重新分配容量的机制,而重新分配容量的机制无非就是重新申请一个新的数组,然后把老数组的元素给复制过去,这个时候时间复杂度是O(n).而此时容量为5,我又添加了一个元素到最末尾本来时间复杂度也是O(1)的,这个时候容量又不够了,与需要触发了重新分配容量的机制进行扩容,时间复杂度又是O(n)了.所以,如果设置成 1/4 的时候缩容,就可以避免这个极端情况的出现.哈哈,有的时候懒也是一总性能优化的方式.
(注:因为添加和删除数组末尾的元素不是每次都会触发缩容和扩容,根据均摊计算所以得出O(1)的时间复杂度)
再来说说我认为很有意思的循环队列的实现.循环队列和数组队列的区别在于通过维护头尾指针来降低出队的时间复杂度.因为数组队列中,出队操作完后,后面的元素需要都往前挪一位,这个时候时间复杂度就是O(n).而因为循环队列中有头指针存在,所以出队的时候只需要操作一个元素,然后维护下这个头指针指向下一个元素就行.这个时候时间复杂仅仅为O(1).总体来说,循环队列给我的感觉就是多维护了两个头尾指针,通过移动指针的方式来避免移动全部的元素.可以说是一种牺牲空间换时间的做法.但是这仅仅多维护了两个头尾指针变量就把时间复杂度O(n)降至了O(1)感觉还是很划算的.
(单)链表
对于也是常用的数据结构之一的 链表 基于其也依然实现了 栈 和 队列
这里实现的链表,使用了一个虚拟头节点,来方便操作真实的头节点.说实话,如果让我换我自己写的时候,我还真是每次都把头节点这个情况单独列出来考虑.而通过新增了一个虚拟头节点后,可以服用操作非头节点的代码逻辑操作头节点.举个很简单例子,如果我在新增的时候,如果我第一次添加.那么我就不能直接把这个放到尾节点的next上.因为第一次添加,整个链表都是null,所以这个时候需要new一个头节点,然后把这个值放在头节点上.而有了虚拟头节点后,就可以直接每次都放在这个链表的尾节点上了.感叹下这个操作的确妙.
简单说下用动态数组实现的栈与队列和用链表实现的栈与队列的区别吧.因为链表在只操作头节点的时候,时间复杂度是O(1),而动态数组因为扩容机制的存在,所以时间复杂度肯定是大于O(1)的.而栈和队列这种大部分时间都是在操作头节点的情况下.显然,用链表实现的栈和队列时间复杂度是优于用动态数组的时间复杂度的.
(单)链表 VS 动态数组
看完链表的实现后,我重新审视下老听别人说的一句话: “数组查找(随机访问)快,插入和删除慢,链表插入和删除快,查找慢.”数组查找快这个可以理解,因为数组在内存中是连续的空间,所以可以通过索引来快速的知道该偏移多少地址,这样能快速的访问那个内存的值.而链表则不是,它在内存中是不连续的,只能通过访问前一个才能找到下一个节点的位置.而链表插入和删除快,如果单看时间复杂度的话,数组最好和情况,直接插入到尾端且不需要扩容为O(1), 最坏的情况,需要扩容则O(n).链表也一样,最好的情况,操作头节点O(1),最坏的情况,操作尾节点O(n).平均下来都是O(n/2) => O(n).
同事跟我说,链表的插入和删除操作是O(1),因为只需要更换下节点的指向.而动态数组需要把插入的位置的后面的元素都往后移位,况且加上扩容的情况.肯定是链表快.如果单独看插入操作来说,同事说的我也认可.但是,你做插入和删除操作之前,难道不需要查找到目标元素吗?所以说,链表插入和删除真的比动态数组快吗?
那这么一看,似乎链表对于动态数组来说毫无优势,我认为不是的.因为动态数组有个扩容操作.所以如果你读取进内存中的数据量很大,扩容的时候需要占据更多的内存.这个时候,不需要扩容操作的链表是不是就更优了呢?
所以总的来说.单单看时间复杂度来说,链表并不比动态数组快.但是如果数据量过大,需要考虑内存的情况下,那么链表无疑的是优于动态数组的选择.
二分搜索树
updating…