数据结构 List Set Collections Map - 07

ding0

2020-02-12

关注关注

数据结构：

数据存储的常用结构有：栈、队列、数组、链表和红黑树。

栈：

栈：stack, 又称堆栈。

先进后出。
栈的入口、出口的都是栈的顶端位置。

压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

队列：

队列：queue,简称队。

先进先出。
队列的入口、出口各占一侧。

数组：

数组:Array,是有序的元素序列。

查找元素快：通过索引，可以快速访问指定位置的元素
增删元素慢
- 指定索引位置增加元素：需要创建一个新数组。
- 指定索引位置删除元素：需要创建一个新数组。

链表：

链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成。

多个结点之间，通过地址进行连接。
查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素
增删元素快：
- 增加元素：只需要修改连接下个元素的地址即可。
- 删除元素：只需要修改连接下个元素的地址即可。

红黑树：

二叉树：binary tree ,是每个结点不超过2的有序树（tree）

红黑树的约束:

节点可以是红色的或者黑色的

根节点是黑色的

叶子节点(特指空节点)是黑色的
每个红色节点的子节点都是黑色的
任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点:

速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍

List：

List接口特点：

它是一个元素存取有序的集合。
它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素。
集合中可以有重复的元素，

常用方法：

public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
public E get(int index):返回集合中指定位置的元素。
public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

ArrayList集合：

java.util.ArrayList集合数据存储的结构是数组结构。元素增删慢，查找快，

LinkedList集合：

java.util.LinkedList集合数据存储的结构是链表结构。方便元素添加、删除的集合。

常用方法：

public void addFirst(E e):将指定元素插入此列表的开头。
public void addLast(E e):将指定元素添加到此列表的结尾。
public E getFirst():返回此列表的第一个元素。
public E getLast():返回此列表的最后一个元素。
public E removeFirst():移除并返回此列表的第一个元素。
public E removeLast():移除并返回此列表的最后一个元素。
public E pop():从此列表所表示的堆栈处弹出一个元素。
public void push(E e):将元素推入此列表所表示的堆栈。
public boolean isEmpty()：如果列表不包含元素，则返回true。

Set：

Set集合有多个子类，其中的java.util.HashSet、java.util.LinkedHashSet这两个集合，常用.

HashSet集合介绍:

java.util.HashSet是Set接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。

HashSet集合存储数据的结构（哈希表）哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的.

保证HashSet集合元素的唯一，其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。

LinkedHashSet

java.util.LinkedHashSet，它是链表和哈希表组合的一个数据存储结构。

可变参数：

Collections：

java.utils.Collections 是集合工具类，用来对集合进行操作。部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素。
public static void shuffle(List<?> list) 打乱顺序:打乱集合顺序。
public static <T> void sort(List<T> list):将集合中元素按照默认规则排序。
public static <T> void sort(List<T> list，Comparator<? super T> ):将集合中元素按照指定规则排序。