前几天和敖丙交流,他说我们写作的人都是在不停地燃烧自己,所以需要不停地补充燃料。对于他的观点,我不能再苟同了——所以我开始狂补计算机方面的基础知识,这其中就包括我相对薄弱的数据结构。
百度百科对数据结构的定义是:相互之间存在一种或多种特定关系的数据元素的集合。定义很抽象,需要大声地朗读几遍,才有点感觉。怎么让这种感觉来得更强烈,更亲切一些呢?我来列举一下常见的 8 种数据结构,数组、链表、栈、队列、树、堆、图、哈希表。
这 8 种数据结构有什么区别呢?
①、数组
优点:
按照索引查询元素的速度很快;
按照索引遍历数组也很方便。
缺点:
数组的大小在创建后就确定了,无法扩容;
数组只能存储一种类型的数据;
添加、删除元素的操作很耗时间,因为要移动其他元素。
②、链表
《算法(第 4 版)》一书中是这样定义链表的:
链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。
Java 的 LinkedList 类可以很形象地通过代码的形式来表示一个链表的结构:
public class LinkedList<E> { transient Node<E> first; transient Node<E> last; private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } }
这是一种双向链表,当前元素 item 既有 prev 又有 next,不过 first 的 prev 为 null,last 的 next 为 null。如果是单向链表的话,就只有 next,没有 prev。
单向链表的缺点是只能从头到尾依次遍历,而双向链表可进可退,既能找到下一个,也能找到上一个——每个节点上都需要多分配一个存储空间。
链表中的数据按照“链式”的结构存储,因此可以达到内存上非连续的效果,数组必须是一块连续的内存。
由于不必按照顺序的方式存储,链表在插入、删除的时候可以达到 O(1) 的时间复杂度(只需要重新指向引用即可,不需要像数组那样移动其他元素)。除此之外,链表还克服了数组必须预先知道数据大小的缺点,从而可以实现灵活的内存动态管理。
优点:
不需要初始化容量;
可以添加任意元素;
插入和删除的时候只需要更新引用。
缺点:
含有大量的引用,占用的内存空间大;
查找元素需要遍历整个链表,耗时。
③、栈
栈就好像水桶一样,底部是密封的,顶部是开口,水可以进可以出。用过水桶的小伙伴应该明白这样一个道理:先进去的水在桶的底部,后进去的水在桶的顶部;后进去的水先被倒出来,先进去的水后被倒出来。
同理,栈按照“后进先出”、“先进后出”的原则来存储数据,先插入的数据被压入栈底,后插入的数据在栈顶,读出数据的时候,从栈顶开始依次读出。
④、队列
队列就好像一段水管一样,两端都是开口的,水从一端进去,然后从另外一端出来。先进去的水先出来,后进去的水后出来。
和水管有些不同的是,队列会对两端进行定义,一端叫队头,另外一端就叫队尾。队头只允许删除操作(出队),队尾只允许插入操作(入队)。
注意,栈是先进后出,队列是先进先出——两者虽然都是线性表,但原则是不同的,结构不一样嘛。
⑤、树
树是一种典型的非线性结构,它是由 n(n>0)个有限节点组成的一个具有层次关系的集合。
之所以叫“树”,是因为这种数据结构看起来就像是一个倒挂的树,只不过根在上,叶在下。树形数据结构有以下这些特点:
每个节点都只有有限个子节点或无子节点;
没有父节点的节点称为根节点;
每一个非根节点有且只有一个父节点;
除了根节点外,每个子节点可以分为多个不相交的子树。
下图展示了树的一些术语:
根节点是第 0 层,它的子节点是第 1 层,子节点的子节点为第 2 层,以此类推。
深度:对于任意节点 n,n 的深度为从根到 n 的唯一路径长,根的深度为 0。
高度:对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长,所有树叶的高度为 0。
树的种类有很多种,常见的有:
无序树:树中任意节点的子节点之间没有顺序关系。那怎么来理解无序树呢,到底长什么样子?
假如有三个节点,一个是父节点,两个是同级的子节点,那么就有三种情况: