JAVA——数据结构

JAVA数据结构有：

1、数组

2、列表（Ｌｉｓｔ）

３、集合（Ｓｅｔ）

４、栈 (Stack) 

5、队列（Ｑｕｅｕｅ）

6、树（Ｔｒｅｅ）

７、堆（Ｈｅａｐ）

8、MAP

一数组：

数组是编程语言中最常见的一种数据结构，可以用它来存储一个元素个数固定且元素类型相同的有序集，每个数组元素存放一个数据，通常可通过数组元素的索引来访问数组元素，包括为数组元素赋值和取出数组元素的值。

二列表

List概念： List集合是一个元素有序（每个元素都有对应的顺序索引，第一个元素索引为0）、且可重复的集合。

ArrayList

Vector

链表 LinkedList

双向链表（对于单向链表而言，只有一个查找方向，并且不能自我删除。

所以引入双向链表，与单向链表的主要不同点只是在于pre指针的引入和删除操作

next：指向下一个结点。

pre：指向前一个结点。）

三、集合 （set）

set：集合注重独一无二的性质,该体系集合可以知道某物是否已近存在于集合中,不会存储重复的元素用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。

如果想要让两个不同的Person对象视为相等的，就必须覆盖Object继下来的hashCode方法和equals方法，因为Object hashCode方法返回的是该对象的内存地址，所以必须重写hashCode方法，才能保证两个不同的对象具有相同的hashCode，同时也需要两个不同对象比较equals方法会返回true

两个对象hash值相同，值不一行相等，因为可能equals（）方法不等。

四、栈（先入后出） 

特点：先入后出，变化的一端在栈顶，栈底固定，像一个桶

五、队列 （先进先出）

 Queue：

Queue是java中实现队列的接口，它总共只有6个方法，我们一般只用其中3个就可以了。Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList。 

六、树

树定义和基本术语

定义

树(Tree)是n(n≥0)个结点的有限集T，并且当n＞0时满足下列条件：

（1）有且仅有一个特定的称为根(Root)的结点；

（2）当n＞1时，其余结点可以划分为m(m＞0)个互不相交的有限集T1、T2 、…、Tm，每个集Ti(1≤i≤m)均为树，且称为树T的子树(SubTree)。

七、堆

概念：堆就是一颗顺序存储的完全二叉树，底层是一个数组。

1、堆逻辑上是一颗完全二叉树

2、堆物理上是保存在数组中

3、堆满足任意结点的值都大于其子树中结点的值，也就是所有根节点 > 其左右孩子结点，叫做大堆，或者大根堆、最大堆，反之则是小堆，或者小根堆、最小堆

4、堆的基本作用是快速找到集合中的最值

八、MAP

常用Map：Hashtable、HashMap、LinkedHashMap、TreeMap