leetcode常用数据结构(JAVA)

数据结构JAVA版本

List 接口

list接口是一个有序集合，他可以包含重复的元素。

ArrayList

基于动态数组的实现，他的元素在内存中是连续存放的。

特点
1. 动态数据实现：ArrayList内部使用数组存储元素，当添加元素超过当前容量时，可以自动增常。
2. 随机访问效率高：可以快速访问到数据的特定元素。
3. 插入和删除效率较低：在列表的中间或者开始插入元素需要移动元素
4. 非线程安全
5. 支持范型

定义方式

ArrayList<Integer> numbers = new ArrayList<>();

//指定初始容量
// 定义一个初始容量为10的ArrayList
ArrayList<Integer> numbers = new ArrayList<>(10);

// 定义一个用于存储自定义对象的ArrayList
ArrayList<MyObject> myObjects = new ArrayList<>();
import java.util.Arrays;

// 从已存在的数组或集合创建ArrayList
ArrayList<String> names = new ArrayList<>(Arrays.asList("Alice", "Bob", "Charlie"));

常用方法
1. 添加元素
  1. add(E e)：将特定元素添加到尾部 返回值 boolean
  2. add(int index, E e): 将指定的元素插入列表的指定位置 返回值 void
2. 访问元素
  1. get(int index ): 返回列表中指定元素的位置 返回值 E (列表中元素的类型)
3. 修改元素
  1. set(int index , E element) : 用于指定元素列表中指定位置的元素 返回值 E
4. 移除元素
  1. remove(int index): 移除列表中指定位置的元素 返回值 E (返回被移除的元素)
  2. remove(Object o): 移除列表中首次出现的指定元素(如果存在) 返回值 boolean
5. 列表大小和清空
  1. size（）: 返回列表中的元素个数 返回值 int
  2. clear（）：移除列表中的所有元素 返回值 void
6. 其他操作
  1. indexOf(Object o): 返回列表中首次出现指定元素的索引，如果列表不包含该元素，则返回-1。 返回值 int
  2. contains（Object o)：判断列表中是否包含指定的元素。 返回值 boolean

LinkedList

基于双向链表的实现，允许在列表的任何位置快速插入元素和删除元素，但随机访问元素则比较慢

特点
1. 双向链表实现: 基于双向链表数据结构实现，这意味着他的每个元素指向前一个和下一个元素的引用。
2. 插入和删除效率高：由于其链表结构，向LinkedList中添加或删除元素，通常比ArrayList快，因为不需要移动其他元素
3. 随机访问效率低: 与ArrayList相比，随机访问（通过索引获取元素）在LinkedList中效率较低，因为需要从头或者结尾开始遍历元素
4. 实现了List和Deque接口：ListedList不仅实现List接口，还实现了Deque接口，提供了额外的队列操作，如在头部或尾部添加/删除元素
5. 内存占用相对较高：每个元素都有额外的内存开销，因为存储需要指向前一个后一个的引用

定义方式

import java.util.LinkedList;

// 定义一个空的LinkedList，用于存储Integer类型的元素
LinkedList<Integer> numbers = new LinkedList<>();

// 定义一个空的LinkedList，用于存储String类型的元素
LinkedList<String> names = new LinkedList<>();

常用方法
1. 添加元素
  1. add(E e)：在列表末尾添加指定的元素 返回值 boolean
  2. add(int index , E e): 在列表的指定位置插入指定的元素 返回值 void
  3. addFirst(E e)：在列表的开头插入指定的元素 返回值 void
  4. addLast(E e): 在列表末尾插入指定的元素 返回值 void
2. 访问元素
  1. get(int index) : 返回列表中指定位置的元素 返回值 E
  2. getFirst() : 返回列表的第一个元素 返回值 E
  3. getLast() : 返回列表的最后一个元素 返回值 E
3. 修改元素
  1. set(int index , E e): 用指定的元素替换列表中指定位置的元素 返回值 E(返回的是旧的元素)
4. 移除元素
  1. remove() : 移除并返回列表的第一个元素 返回值 E
  2. remove(int index): 移除列表中指定位置的元素 返回值 E
  3. remove(Object o): 移除列表中首次出现的指定元素 返回值 boolean
  4. removeFirst() : 移除并返回列表的第一个元素 返回值 E
  5. removeLast(): 移除并返回列表的最后一个元素 返回值 E
5. 其他操作
  1. size() : 返回列表中的元素数 返回值 int
  2. clear(): 移除列表中的所有元素 返回值 void
  3. contains(Object o ): 判断列表中是否包含指定的元素 返回值 boolean
  4. indexOf(Object o): 返回列表中首次出现的指定元素的索引 返回值 int
  5. lastIndexOf(Object o): 返回列表中最后一次出现指定元素的索引 返回值 int
栈Stack
stack是java中的一个类，他扩展了Vector类并实现了一个后进先出的堆栈
1. 特点
  1. 后进先出
  2. 基于Vector类实现：因此拥有vector的所有特性，如能动态扩展
  3. 线程安全：所有方法都是同步的，即线程安全
  4. 支持所有的数据类型：虽然Stack仍能被使用，但java官方更推荐灵活的Deque 如ArrayDeque或LinkedList
2. 定义
  1
  Stack<Integer> stack = new Stack<>();
3. 常用方法
  1. push（E item）：将元素压入堆栈顶部 返回值 E
  2. pop( ) ：移除并返回堆栈顶部移除的元素 返回值 E
  3. peek( ) : 查看堆栈顶部的对象而不移除它 返回值 E
  4. empty( )：测试堆栈是否为空 返回值 boolean
  5. search（Object o)：返回对象在堆栈中的位置，以1为基数 返回值 int

Vector

他和ArrayLsit类似，是线程安全的

CopyOnWriteArrayList

线程安全的ArrayList变体。在任何修改操作（如添加、设置和删除等）时，它都会复制底层数组。

Deque 接口

是 Java 中的一个接口，属于 Java 集合框架。它允许在队列的两端进行元素的插入和移除操作，这使得它既可以被当作队列使用，也可以作为栈使用。

LinkedList

ArrayDeque

ArrayDeque 是 Deque 接口的一个具体实现，使用了可变大小的数组。

特点
1. 高效的双端操作：允许高校的在队列的两端插入和删除元素，可以实现栈，也可以实现队列
2. 无容量限制：虽然是基于数组实现的，但他可以在运行时动态的扩展和缩减其容量
3. 更快的迭代性能：与基于链表的LinkedList相比，ArrayDeque在迭代访问时更快
4. 非线程安全： ArrayDeque不是线程安全，如果在多线程环境下使用，需要外部使用
5. 不允许插入null元素：使用ArrayDeque时不能添加null元素，因为null被用来作为特殊的返回值，以指示队列为空。

定义

1
2
3

Deque<Integer> deque = new ArrayDeque<>(); 
// 或者，直接使用 ArrayDeque 类型
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();

常用方法
1. 添加元素
  1. addFirst(E e) : 在队列前端添加一个元素
  2. addLast(E e): 在队列的后段添加一个元素
  3. offerFirst(E e): 在队列的前端添加一个元素，如果队列已满，则返回 false
  4. offerLast(E e): 在队列的后段添加一个元素，如果队列已满，则返回 false
2. 移除元素
  1. removeFirst() : 移除并返回队列前端的元素
  2. removeLast() : 移除并返回队列后段的元素
  3. pollFirst() ：移除并返回队列前端的元素，如果队列为空，则返回null
  4. pollLast() ：移除并返回队列后段的元素，如果队列为空，则返回null
3. 查看元素
  1. getFirst() : 返回队列前端的元素但不移除
  2. getLast() : 返回队列后段的元素
  3. peekFirst() : 返回队列前端的元素但不移除它，如果队列为空，则返回null
  4. peekLast() : 返回队列后端的元素但不移除它，如果队列为空，则返回null
4. 栈操作
  1. push(E e) : 将元素推入堆栈表示的队列前端
  2. pop() ：移除并返回堆栈表示的队列前端的元素
5. 其他方法
  1. size() : 返回队列中元素数量
  2. isEmpty() : 检查队列是否为空
  3. clear() : 清空队列

Set集合

Map集合

定义

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

方法

创建和修改
1. put(K key, V value):将指定的值与此映射中的指定键关联
删除
1. remove(Objcet key): 如果存在，则从此映射中移除键的映射
2. clear()：清除所有映射
查询
1. get(Object key); 返回指定键所映射的值，如果此映射不包含键的映射关系，则返回null.
2. containsKey(Object key):如果此映射包含指定键的映射关系，则返回true
3. containsValue(Object value): 如果此映射将一个或多个键映射到指定值，则返回true
4. size(): 返回此映射中的键值映射关系的数。
5. isEmpty():如果此映射不包含键值映射关系，则返回true。

迭代

keySet(): 返回set视图，示例如下

Map<String, Integer> map = new HashMap<>();
map.put("apple", 10);
map.put("banana", 20);

Set<String> keySet = map.keySet();
for (String key : keySet) {
    System.out.println(key);
}
// apple  banana

values(): 返回collection视图

for (Integer value : map.values()) {
    System.out.println(value);
}

entrySet(): 返回包含

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " => " + value);
}

`Iterator`迭代器

定义 Iterator是一个用于遍历集合（Collection）的接口，几乎所有的集合类都提供了一个方法来获得一个实现Iterator接口的对象，该对象能够遍历集合中的元素。

基本使用方法

调用集合的iterator()方法获取Iterator对象
使用hasNext()方法检查集合中是否还有元素
使用next()方法获取集合中的下一个元素
如果有需要，使用remove()方法从集合中移除next()方法返回的最后一个元素

数据结构JAVA版本

List 接口

ArrayList

LinkedList

栈Stack

Vector

CopyOnWriteArrayList

Deque 接口

LinkedList

ArrayDeque

Set集合

Map集合

定义

方法

Iterator迭代器

`Iterator`迭代器