数组 Array
-
数组在内存中的存储方式
image.png
可以看出数组查找的时间复杂度是O(1)，因为直接通过下标就可以查找
-
数组的插入和删除操作
image.png
从上图可以看出，数组插入元素到数组中间的时间复杂度是O(n)，因为插入之后插入位置后面的数据都要换位置，删除也是如此。当然，如果插入或删除的元素是数组最后，则时间复杂度为O(1)
image.png
链表 Linked List
- 插入、删除的速度比数组快
image.png
- 每个元素都有一个指针，链向下一个节点。
-
Insert操作
image.png
新插入的元素的Next指针直接指向后一个元素，新插入的元素的前面的元素的Next指向新插入的元素即可。
- Delete操作
image.png
删除一个元素，直接把该元素前面的元素的Next指向后面的元素即可。再把要删除的节点从内存中释放掉即可。
那么链表的插入和删除都是O(1)的时间复杂度。
但是呢，链表中想要查找某一个元素，比如查找第五个元素，则要从头遍历五次，那么链表查找的时间复杂度则是O(n)的。
所以，不用的数据结构优缺点都是不同的。使用的时候根据实际情况来应用。
双链表
image.png
image.png
网友评论