共计 3257 个字符,预计需要花费 9 分钟才能阅读完成。
前言
本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的常识。
你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。
数组、链表、队列、栈,是数据结构中最根底的四大构造,数组和链表更是根底中的根底,后续所有简单的数据结构都是在它们的根底上演变而来的。
本节,咱们就来重温这四大构造。
数组
对于数组,大家都比拟相熟了。
它是一种线性数据结构,应用一组间断的内存空间存储一组具备雷同类型的数据。
这个概念中有三个关键词:线性、间断、雷同类型。
线性,示意没有分叉,任意元素的前后元素最多只有一个,同样是线性构造的还有链表、队列等。
间断,它在内存空间中的存储是间断的,不间断的,前后两个元素紧挨着,不存在间隙。
雷同类型,数组中存储的元素的类型肯定是雷同的,当然,在 Java 中,你能够应用 Object 代表所有类型,实质上,它们仍然是雷同类型。
正是有了下面三个个性,才使得数组具备了 随机拜访 的个性,那么,什么是随机拜访呢?
简略点说,你能够通过下标疾速定位到数组中的元素,且工夫复杂度是 O(1),它是怎么做到的呢?
咱们晓得,计算机中只有 0 和 1,所有的所有都能够看作是 0 和 1 的各种组合,内存也是一样。
当咱们创立一个数组,比方 int[] array = new int[]{2, 5, 8, 7};
时,它其实返回的是这个数组在内存中的地位(地址),咱们晓得,一个 int 类型占用 4 个字节,也就是 32 位的 0 或 1,当咱们拜访数组下标为 0 的元素时,间接返回数组地址处取 32 位转成 int 即可,同样地,当咱们拜访数组下标为 1 的元素时,返回数组地址加上 (32*1) 的地址处取 32 位转成 int,依此类推。
这也是大部分语言中数组下标从 0 开始的起因,试想如果下标从 1 开始,那么,计算内存地址的时候就变成了address + 32 * (i - 1)
,这显然会造成肯定的性能损耗。
链表
链表,它也是一种线程数据结构,与数组不同的是,它在内存空间中不肯定是顺序存储的,为了保障链表中元素的连续性,个别应用一个指针来找到下一个元素。
上图是典型的单链表构造,在单链表中,只有一个指向下一个元素的指针。
如果要用 Java 类来示意单链表中的元素节点的话,大略看起来像这样子:
class Node {
int value;
Node next;
}
所以,链表不具备随机拜访的个性,在链表中依据索引来查找元素只能从头开始(单链表),它的工夫复杂度是 O(n)。
下面咱们说的是单链表,如果在单链表的根底上再减少一个前驱指针(指向前一个元素的指针),就变成了双向链表。
Java 中的 LinkedList 就是典型的双向链表构造,双向链表既能够当作队列应用,又能够当作栈来应用,十分不便。
如果在双向链表的根底上再减少 HashMap 的性能,就变成了 LinkedHashMap 了,咳咳,扯远了。
心愿学习 LinkedList 和 LinkedHashMap 源码解析的同学,能够关注我的公号主“彤哥读源码”。
这里提到了队列,那么,什么是队列呢?
队列
所谓队列,其实跟事实中的排队是一样的,其中的元素从一端进入,从另一端进来,英文叫做:First In,First Out,简写 FIFO。
从这张图,也能够看进去,实现队列最简略的形式就是应用链表,把上图中的箭头倒过去即可。
入队时,将元素退出到链表尾端,出队时,将第一个元素删除并将头节点指向下一个节点即可。
让咱们来看看应用链表实现队列的简略代码实现:
public class LinkedQueue {
Node head;
Node tail;
void offer(Integer value) {if (value == null) {throw new NullPointerException();
}
Node node = new Node(value);
if (head == null) {head = tail = node;} else {
tail.next = node;
tail = node;
}
}
Integer poll() {
Node first = head;
if (first != null) {
head = first.next;
first.next = null;
return first.value;
} else {return null;}
}
static class Node {
int value;
Node next;
public Node(int value) {this.value = value;}
}
}
是不是很简略呢?
那么,数组能不能实现队列呢?
答案是必定的,应用数组实现队列有很多种形式,其中一种是应用两个指针:入指针、出指针,它们别离指向下一个入队列和下一个出队列的地位。
入队时,在入指针处放入元素,同时入指针后移。
出队时,取出出指针处的元素返回,同时出指针后移。
当指针达到数组开端时,返回数组开始的地位。
这样就造成了一个能够循环应用的数组,俗称环形数组。
此时,咱们思考一个问题,队列空和队列满时,两个指针都是指向同一个地位,仿佛不太好解决。
其实,很简略,引入一个 size 变量标识队列中有多少个元素即可。
所以,这玩意儿要怎么实现呢?Show me the code!
public class ArrayQueue {int[] array;
int offerIndex;
int pollIndex;
int size;
public ArrayQueue(int capacity) {this.array = new int[capacity];
this.offerIndex = this.pollIndex = 0;
this.size = 0;
}
boolean offer(Integer value) {if (value == null) {throw new NullPointerException();
}
if (size == array.length) {return false;}
array[offerIndex] = value;
offerIndex = (offerIndex + 1) % array.length;
size++;
return true;
}
Integer poll() {if (size == 0) {return null;}
int value = array[pollIndex];
pollIndex = (pollIndex + 1) % array.length;
size--;
return value;
}
}
OK,以上就是应用数组实现的队列,能够看到,与链表实现的队列相比,它须要指定容量,这叫做 有界队列
,如果须要应用数组实现无界队列,则须要退出扩容的机制,有趣味的同学能够本人实现看看。
上面,咱们再来看另一种根底的数据结构——栈。
栈
栈,它是与队列体现齐全相同的数据结构,它的元素是先进的后进去,就像咱们往一个杯子外面放货色一样,先放进去的放在最上面,只有把下面的货色拿进去后能力拿出上面压着的货色,这种行为用英文叫做:First In,Last Out,简称 FILO。
栈,具备很多用途,计算机中很多解决都是通过栈这种数据结构来进行的,比方算术运算,筹备两个栈,一个栈存储数字,一个栈存储符号,从头开始顺次把字符压入到这两个栈中,当遇到符号优先级比栈顶元素低时,则取出栈顶符号,并从数字栈中取出两个数字进行运算,运算的后果再压回数字栈中,持续以此运行,当所有字符都放入栈之后,顺次从数字栈中取出两个元素,并从符号栈中取出一个元素,进行计算,后果压回数字栈,持续以此运行,直到符号栈为空,或者数字栈只剩下一个元素为止,弹出这个数字即为最初的后果。
以 3 + 2 * 4 -1
为例:
好了,对于栈,咱们就简略介绍到这里,前面,咱们还会大量遇到这个数据结构。
后记
本节,咱们一起重温了数组、链表、队列、栈这四种最根底的数据结构。
说起数组,咱们看到,内存自身就是一张大数组,它外面的元素就是 0 和 1,那么,咱们能不能间接操作这些 0 和 1 呢?
答案是必定的。
下一节,咱们将介绍位运算,以及位图这种数据结构,彼时,咱们将具体介绍如何应用 位图来实现 12306 的抢票逻辑
,关注我,及时获取最新推文。
关注公号主“彤哥读源码”,解锁更多源码、根底、架构常识。