常见的数据结构

  • 2020 年 09 月 22 日
  • 44次
  • 849 字
  • 暂无评论

定义:

相互之间存在一种或多种特定关系的数据元素的集合。定义很抽象,需要大声地朗读几遍,才有点感觉。怎么让这种感觉来得更强烈,更亲切一些呢?我来列举一下常见的 8 种数据结构,数组、链表、栈、队列、树、堆、图、哈希表。

区别:

①、数组

优点:

按照索引查询元素的速度很快;
按照索引遍历数组也很方便。
缺点:

数组的大小在创建后就确定了,无法扩容;
数组只能存储一种类型的数据;
添加、删除元素的操作很耗时间,因为要移动其他元素。

②、链表

《算法(第 4 版)》一书中是这样定义链表的:

链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。

Java 的 LinkedList 类可以很形象地通过代码的形式来表示一个链表的结构:

public clas sLinkedList<E> [

transient Node<E> first ;transient Node<E> last ;

private static

class

Node<E> l

E item ;

Node<E> next ;Node<E> prev ;

Node (Node<E> prev, E element , Node<E> ne X

this. item = element ;

this . next = next ;

this. prev = prev ;

这是一种双向链表,当前元素 item 既有 prev 又有 next,不过 first 的 prev 为 null,last 的 next 为 null。如果是单向链表的话,就只有 next,没有 prev。

单向链表的缺点是只能从头到尾依次遍历,而双向链表可进可退,既能找到下一个,也能找到上一个——每个节点上都需要多分配一个存储空间。

链表中的数据按照“链式”的结构存储,因此可以达到内存上非连续的效果,数组必须是一块连续的内存。

由于不必按照顺序的方式存储,链表在插入、删除的时候可以达到 O(1) 的时间复杂度(只需要重新指向引用即可,不需要像数组那样移动其他元素)。除此之外,链表还克服了数组必须预先知道数据大小的缺点,从而可以实现灵活的内存动态管理。

优点:

不需要初始化容量;
可以添加任意元素;
插入和删除的时候只需要更新引用。
缺点:

含有大量的引用,占用的内存空间大;
查找元素需要遍历整个链表,耗时。

③、栈

栈就好像水桶一样,底部是密封的,顶部是开口,水可以进可以出。用过水桶的小伙伴应该明白这样一个道理:先进去的水在桶的底部,后进去的水在桶的顶部;后进去的水先被倒出来,先进去的水后被倒出来。

同理,栈按照“后进先出”、“先进后出”的原则来存储数据,先插入的数据被压入栈底,后插入的数据在栈顶,读出数据的时候,从栈顶开始依次读出。

④、队列

队列就好像一段水管一样,两端都是开口的,水从一端进去,然后从另外一端出来。先进去的水先出来,后进去的水后出来。

和水管有些不同的是,队列会对两端进行定义,一端叫队头,另外一端就叫队尾。队头只允许删除操作(出队),队尾只允许插入操作(入队)。

注意,栈是先进后出,队列是先进先出——两者虽然都是线性表,但原则是不同的,结构不一样嘛。


版权属于:hierarch

本文链接:https://hiea.top/archives/155.html



—— 暂无评论 ——

OωO