常见的数据结构

1.栈

栈，tack，又称堆栈，他是运算受限的线性表。其限制是只允许在一端进行插入和删除操作。

存取特点：先进后出。

压栈：将指定元素存储到栈顶。

弹栈：取出栈顶的元素。

2.队列

队列，queue,简称队，同栈一样，也是一种运算受限的线性表。其限制是允许在表的一段插入，在表的另一端删除。

存取特点：先进先出。

3.数组

数组，Array，是有序的元素序列，数组是在内存中开辟一段连续的空间。并在此空间中存放元素。

存取特点：

元素查找快。（通过索引，可以快速地访问指定的元素）

增删数据慢。（增删元素，需要重新创建数组，并把源数组的值复制到对应的数组。）

4.链表

链表，linked list，由一系列节点（链表中的每一个元素成为一个节点）组成。一个节点包括数据域和指针域两个部分，数据域存储数据，指针域存储下一跳节点地址。

单向链表与双向链表的区别：单向链表只存储了吓一跳节点的地址，而双向链表存储了上一跳和下一跳的节点地址。因此单向链表是无序的，而双向链表是有序的。

存取特点：

多个节点之间，通过地址进行连接。

查询元素慢（每次查询都需要遍历整个链表）

增删元素快（只需要修改元素的地址即可）

5.红黑树

二叉树：每个节点不超过二的有序树。左右节点分别叫做左子树和右子树。树的键值是有序的。

红黑树存取特点：

速度特别快，查找叶元素的最少和最大的路径不多于二倍。

HashSet集合存储数据的结构（哈希表）

在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。 但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过8时，将链表转换为红黑树，这样大大减少了查找时间。