Java中常见的自带数据结构类

目录

一、ArrayList（动态数组）

特性

常用方法

二、LinkedList（双向链表）

特性

常用方法

三、ArrayDeque（双端队列） 

特性

常用方法

四、HashMap（哈希表）

特性

常用方法

五、TreeMap（红黑树）

特性

常用方法

六、HashSet（哈希表）

特性

常用方法

HashSet和HashMap的区别

数据结构和存储内容：

方法：

遍历方式：

七、TreeSet（红黑树）

特性

常用方法

TreeSet和TreeMap的区别 

存储内容不同：

遍历方式不同：

操作对象不同：

方法不同：

八、Stack（栈）

特性

常用方法

九、Queue（队列）

特性

常用方法

十、PriorityQueue（优先级队列）

特性

常用方法

十一、Deque（双端队列）

特性

常用方法

---

关山难越谁悲失路之人？萍水相逢尽是他乡之客

                                                                —— 24.10.19

一、ArrayList（动态数组）

ArrayList是 Java 中一个常用的动态数组实现类

特性

① 动态扩容：当向 ArrayList 添加元素导致容量不足时，它会自动增加内部数组的大小，以容纳更多的元素。

② 随机访问快：通过索引获取元素的时间复杂度为 O(1)。

③ 插入和删除元素：在中间位置插入或删除元素的时间复杂度为 O(n)，因为需要移动后续元素。

---

常用方法

• add(E element) ：向列表末尾添加一个元素。
• add(int index, E element) ：在指定索引位置插入一个元素。
• get(int index) ：获取指定索引位置的元素。
• remove(int index) ：移除指定索引位置的元素。
• remove(Object o) ：移除指定的元素。
• size() ：返回列表中的元素个数。
• clear() ：清空列表。 

add(E element)    // 向列表末尾添加一个元素
add(int index, E element)    // 在指定索引位置插入一个元素
get(int index)    // 获取指定索引位置的元素
remove(int index)    // 移除指定索引位置的元素
remove(Object o)    // 移除指定的元素
size()    // 返回列表中的元素个数
clear()    // 清空列表

---

二、LinkedList（双向链表）

LinkedList 是 Java 中的一种常见数据结构

特性

1.底层数据结构是双向链表，每个节点包含数据以及指向前一个和后一个节点的引用。

2.插入和删除操作在特定位置时，效率通常比 ArrayList 高，尤其是在列表头部或中间位置，时间复杂度为 O (1)。

3.随机访问元素的效率较低，时间复杂度为 O (n) 。

---

常用方法

• add(E element) ：在列表末尾添加元素
• add(int index, E element) ：在指定索引位置插入元素
• get(int index) ：获取指定索引位置的元素
• remove(int index) ：移除指定索引位置的元素
• removeFirst() ：移除列表的第一个元素
• removeLast() ：移除列表的最后一个元素

add(E element)    // 在列表末尾添加元素
add(int index, E element)    // 在指定索引位置插入元素
get(int index)    // 获取指定索引位置的元素。
remove(int index)    // 移除指定索引位置的元素
removeFirst()    // 移除列表的第一个元素
removeLast()    // 移除列表的最后一个元素

---

三、ArrayDeque（双端队列） 

ArrayDeque 是一个基于数组实现的双端队列，是一个可以同时在队列的头部和尾部进行高效的插入和删除操作的数据结构

特性

1.没有容量限制，会随着元素的添加自动扩容。

2.可以作为栈（只在一端操作）或双端队列（两端均可操作）使用。

3.不允许存储 null 元素

---

常用方法

• addFirst(E e) ：在队列头部添加元素
• addLast(E e) ：在队列尾部添加元素
• removeFirst() ：移除并返回队列头部的元素
• removeLast() ：移除并返回队列尾部的元素
• getFirst() ：获取但不删除队列头部的元素
• getLast() ：获取但不删除队列尾部的元素

addFirst(E e)    // 在队列头部添加元素
addLast(E e)    // 在队列尾部添加元素
removeFirst()    // 移除并返回队列头部的元素
removeLast()    // 移除并返回队列尾部的元素
getFirst()    // 获取但不删除队列头部的元素
getLast()    // 获取但不删除队列尾部的元素

---

四、HashMap（哈希表）

HashMap 是 Java 中常用的键值对存储数据结构

特性

1.基于哈希表实现，查找、插入和删除的平均时间复杂度为 O (1) 。

2.不保证键值对的顺序。

3.允许键为 null ，但值也可为 null 。

---

常用方法

• put(K key, V value) ：向 HashMap 中添加键值对。
• get(K key) ：通过键获取对应的值。
• remove(K key) ：根据键移除键值对。
• containsKey(K key) ：检查是否包含指定的键。
• size() ：获取 HashMap 中的键值对数量。

put(K key, V value)    // 向 HashMap 中添加键值对get(K key)    // 通过键获取对应的值remove(K key)    // 根据键移除键值对containsKey(K key)    // 检查是否包含指定的键size()     // 获取 HashMap 中的键值对数量

---

五、TreeMap（红黑树）

TreeMap 是 Java 中的一种有序的键值对映射数据结构

特性

1.基于红黑树实现，元素按照键的自然顺序或者指定的比较器顺序进行排序。

2.提供了有序的键访问，例如获取第一个键、最后一个键、大于或小于给定键的键等操作。

---

常用方法

• put(K key, V value) ：添加键值对。
• get(K key) ：通过键获取值。
• firstKey() ：获取第一个键。
• lastKey() ：获取最后一个键。
• lowerKey(K key) ：获取小于给定键的最大键。

put(K key, V value)    // 添加键值对
get(K key)    // 通过键获取值
firstKey()    // 获取第一个键
lastKey()    // 获取最后一个键
lowerKey(K key)    // 获取小于给定键的最大键

---

六、HashSet（哈希表）

HashSet 是 Java 中用于存储不重复元素的集合

特性

1.基于哈希表实现，查找元素的时间复杂度接近 O (1) 。

2.不保证元素的顺序。

---

常用方法

• add(E element) ：向集合中添加元素。
• remove(E element) ：从集合中移除元素。
• contains(E element) ：检查集合是否包含指定元素。
• size() ：获取集合中元素的数量。

add(E element)    // 向集合中添加元素remove(E element)    // 从集合中移除元素contains(E element)    // 检查集合是否包含指定元素size()    // 获取集合中元素的数量

---

⭐HashSet和HashMap的区别

1. 数据结构和存储内容：

   • HashSet 基于哈希表实现，存储的是一组不重复的元素
   • HashMap 基于哈希表实现，存储的是键值对

2. 方法：

   • HashSet 主要方法有 add 、 remove 、 contains 等，用于操作元素
   • HashMap 主要方法有 put 、 get 、 remove 、 containsKey 等，用于操作键值对

3. 遍历方式：

   • 遍历 HashSet 通常使用增强型 for 循环直接获取元素。
   • 遍历 HashMap 可以通过获取键集、值集或者键值对集来进行遍历。

---

七、TreeSet（红黑树）

TreeSet 是 Java 中一个有序且不允许重复元素的集合

特性

1.基于红黑树实现，元素按照自然顺序或者自定义的比较器顺序排列。

2.有序性使得可以方便地获取集合中的第一个、最后一个元素，以及获取特定范围内的元素。

---

常用方法

• add(E element) ：向集合添加元素。
• remove(E element) ：移除元素。
• first() ：获取集合中的第一个元素。
• last() ：获取集合中的最后一个元素。

add(E element)    // 向集合添加元素remove(E element)    // 移除元素first()    // 获取集合中的第一个元素last()    // 获取集合中的最后一个元素

---

⭐TreeSet和TreeMap的区别 

1. 存储内容不同：

   • TreeSet 存储的是一组不重复的元素
   • TreeMap 存储的是键值对

2. 遍历方式不同：

   • TreeSet 只能遍历元素
   • TreeMap 可以遍历键、值或者键值对

3. 操作对象不同：

   • TreeSet 的操作对象是单个元素
   • TreeMap 的操作对象是键值对

4. 方法不同：

   • TreeSet 有 first() 、 last() 等获取集合中极值元素的方法。
   • TreeMap 有 firstKey() 、 lastKey() 等获取极值键的方法，以及 get(key) 根据键获取值的方法。

---

八、Stack（栈）

Stack 是一种遵循后进先出（Last-In-First-Out，LIFO）原则的数据结构

特性

1.后进先出（LIFO - Last In First Out）原则：最后进入栈的元素最先被取出。就像往一个桶里叠盘子，最后放进去的盘子会最先被拿出来。

2.操作受限：主要操作是压入（push）元素和弹出（pop）元素，以及查看栈顶元素（peek）和判断栈是否为空（empty）。

3.高效的插入和删除：在栈顶进行插入和删除操作的时间复杂度通常为 O (1) ，这些操作不需要移动大量元素。

---

常用方法

• push(E item) ：将元素压入栈顶
• pop() ：弹出并返回栈顶元素
• peek() ：查看栈顶元素，但不弹出
• empty() ：判断栈是否为空

push(E item)    // 将元素压入栈顶
pop()    // 弹出并返回栈顶元素
peek()    // 查看栈顶元素，但不弹出
empty()    // 判断栈是否为空

---

九、Queue（队列）

Queue 是一种遵循先进先出（First-In-First-Out，FIFO）原则的数据结构，即先进入队列的元素先出队列。

特性

1.元素的添加和移除按照特定的顺序进行，先进先出。

2.可以为空，并且可以查询队列是否为空以及队列中元素的数量。

---

常用方法

• offer(E e) ：尝试将元素添加到队列末尾，如果成功返回true，如果队列已满则返回 false
• poll() ：获取并移除队列头部的元素，如果队列为空则返回 null 
• peek() ：获取但不移除队列头部的元素，如果队列为空则返回 null 
• size() ：返回队列中元素的数量
• isEmpty() ：判断队列是否为空

offer(E e)    // 尝试将元素添加到队列末尾，如果成功返回 true ，如果队列已满则返回 false 
poll()    // 获取并移除队列头部的元素，如果队列为空则返回 null 
peek()    // 获取但不移除队列头部的元素，如果队列为空则返回 null 
size()    // 返回队列中元素的数量
isEmpty()    // 判断队列是否为空

---

十、PriorityQueue（优先级队列）

PriorityQueue 是一个无界的优先级队列，其中的元素按照其自然顺序（或者通过提供的比较器）进行排序

特性

1.元素按照优先级进行排序，优先级高的元素先出队。

2.不允许插入 null 元素。

3.是非线程安全的。

---

常用方法

• offer(E e) ：将元素插入到队列中合适的位置以保持队列的优先级顺序
• poll() ：获取并移除队列头部的元素，返回并删除具有最高优先级的元素
• peek() ：获取但不移除队列头部优先级最高的元素
• size() ：返回队列中元素的个数
• isEmpty() ：判断队列是否为空

offer(E e)    // 将元素插入到队列中合适的位置以保持队列的优先级顺序
poll()    // 获取并移除队列头部的元素，返回并删除具有最高优先级的元素
peek()    // 获取但不移除队列头部优先级最高的元素
size()    // 返回队列中元素的个数
isEmpty()    // 判断队列是否为空

---

十一、Deque（双端队列）

Deque 是一个可以在两端进行插入和删除操作的数据结构

特性

1.支持在队列的头部和尾部添加或删除元素

2.可以作为栈（只在一端操作）或队列（两端分别进行入队和出队）使用

---

常用方法

• addFirst(E e) ：在队列头部添加元素
• addLast(E e) ：在队列尾部添加元素
• removeFirst() ：移除并返回队列头部的元素
• removeLast() ：移除并返回队列尾部的元素
• getFirst() ：获取但不删除队列头部的元素
• getLast() ：获取但不删除队列尾部的元素

addFirst(E e)    // 在队列头部添加元素
addLast(E e)    // 在队列尾部添加元素
removeFirst()    // 移除并返回队列头部的元素
removeLast()    // 移除并返回队列尾部的元素
getFirst()    // 获取但不删除队列头部的元素
getLast()    // 获取但不删除队列尾部的元素