Java链表、栈、队列、哈希表、集合
总结一下JAVA中常见的一些与数据结构有关的持有对象以及他们的常见的方法 (并不是全部因为全部太多了orz)
列表 List
方法 | 作用 |
---|---|
boolean add(E e) |
在列表末尾添加元素 |
void add(int index, E e) |
在指定的下标处添加元素 |
void clear() |
清除列表中的所有元素 |
boolean contains(Object o) |
判断列表中是否包含指定的元素 |
E get(int index) |
返回指定下标出的元素 |
int indexOf(Object o) |
返回指定元素的下标,如果列表中不存在返回-1 |
boolean isEmpty() |
判断列表是否为空 |
E remove(int index) |
删除指定下标处的元素 |
boolean remove(Object o) |
删除指定元素,如果不存在返回false |
E set(int index, E element) |
将指定下标处的元素用新的元素代替 |
int size() |
返回列表的大小 |
default void sort(Comparator<? super E> c) |
对列表进行按照给定的Compartor的排序 |
Object[] toArray() |
将列表转化为对应元素的一个数组 |
列表与数组之间的相互转化
在实际使用中,数组和列表的相互转化也是经常需要用到的,奈何本人记性太差,老是记不住,印象中已经是查了N次了,果然好记性不如烂笔头,还是记一下吧,原文:Java List和Array之间的转换
Array 转为List
实现方法 :java中数组转list使用Arrays.asList(T... a)方法。
1
2
3
4
5
6
7
8
9public class Array2List {
public static void main(String[] args){
List<String> listA=Arrays.asList("dog","cat","cow");
String[] strs={"dog","cat","cow"};
List<String> listB= Arrays.asList(strs);
System.out.println(listA);
System.out.println(listB);
}
}注意事项
1)
Arrays.asList()
方法返回的对象是Arrays的内部类,对list的操作仍然反映在原数组上,因此这个list是定长的,不支持add、remove操作;2)由于
asList
方法接受的泛型参数,因此不能用于基本类型,只能使用如下方法:1
2
3
4
5
6
7
8
9
10public class Array2List {
public static void main(String[] args){
int[] a={1,2,3,4,5};
List<Integer> list=new ArrayList<>();
for(int i:a){
list.add(i);
}
System.out.println(list);
}
}
List转为Array
实现:使用
list.toArray()
1
2
3
4
5
6
7
8
9
10
11
12public class Array2List {
public static void main(String[] args){
List<String> list=new ArrayList<>();
list.add("dog");
list.add("cat");
list.add("cow");
String[] animals=list.toArray(new String[0]);
for(String animal:animals){
System.out.println(animal);
}
}
}注意事项
由于
list.toArray()
返回的是Object对象数组,如果我们想要转化为基本类型数组,比如说List<Integer>
转化为int[]
,那么可以使用steam()
:1
list.stream().mapToInt(Integer::intValue).toArray();
双端队列 Deque [1]
First Element (Head) | Last Element (Tail) | |||
---|---|---|---|---|
Throws exception | Special value | Throws exception | Special value | |
Insert | addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
Remove | removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
Examine | getFirst() |
peekFirst() |
getLast() |
peekLast() |
Queue Method |
Equivalent Deque Method |
---|---|
add(e) |
addLast(e) |
offer(e) |
offerLast(e) |
remove() |
removeFirst() |
poll() |
pollFirst() |
element() |
getFirst() |
peek() |
peekFirst() |
Stack Method | Equivalent Deque Method |
---|---|
push(e) |
addFirst(e) |
pop() |
removeFirst() |
peek() |
peekFirst() |
ArrayList
ArrayList是List接口的可变数组实现,所有的方法和List基本一致。时间复杂度方面,增的时间复杂度均摊下来是常数的,但是几乎其他的操作都是线性时间复杂度,优点是常数因子相比于LinkedList来说比较小。
特有的方法 | 作用 |
---|---|
void ensureCapcity(int minCapacity) |
将动态数组进行扩容,确保列表能够容纳给定的最小容量 |
void trimToSize() |
将动态数组的容量调整为数组中的元素个数 |
LinkedList
LinkedList是List接口和Deque接口的双向链表实现,所拥有的方法为List接口和Deque接口的集合。链表实现使得增、删时间复杂度为O(1),但是没有了ArrayList中的索引机制,导致对于特定位置的元素查询时间复杂度为O(n)。
图 Map (键值对)
方法 | 作用 |
---|---|
void clear() |
清除图中所有的元素 |
boolean containsKey(Object key) |
判断是否包含我们给定键的键值对 |
boolean containsValue(Object value) |
判断是否包含我们给定值的键值对 |
Set<Map.Entry<K, V>> entrySet() |
返回Map的集合(Set)视图 |
V get (Object key) |
返回给定键的对应值,若不存在,返回null |
default V getOrDefault(Object key, V defaultValue) |
返回给定键的对应值,若不存在,返回设定的默认值 |
boolean isEmpty() |
判断Map是否为空 |
Set<K> keySet() |
返回Map中键的集合(Set)视图 |
V put(K key, V value) |
将给定的键值对插入到Map中,若已经存在对应的key,则替换value,返回旧的value,若不存在,返回null |
default V putIfAbsent(K key, V value) |
如果不存在给定的键的键值对,则插入,否则,返回当前键对应的值 |
V remove(Object key) |
删除给定键的键值对 |
default boolean remove(Object key, Object value) |
删除给定的键值对,返回是否删除成功 |
default V replace(K key, V value) |
如果存在给定键的键值对,替换键的当前值为给定的新值 |
default boolean replace(K key, V oldValue, V newValue) |
如果存在给定键值对,替换给定键值对中的值为新值,返回是否替换成功 |
int size() |
返回Map中的键值对数目 |
HashMap和Hashtable
Map接口的哈希表实现,HashMap基本与Hashtable相同,除了HashMap是异步的并且允许null key。时间复杂度方面,对于基本的增查操作 (get and put),HashMap可以达到常数的时间复杂度。关于HashMap和Hashtable的区分,详情可以参考这一篇博文 2
构造器 Constructor:initialCapcacity和loadFactor影响HashMap的性能。当当前的entry数量超过loadFactor和当前容量的乘积,哈希表就会被rehash,扩容至原来的两倍 [3]。默认情况下initialCapacity为16,loadFactor为0.75,这样的情况下性能是 比较好的。
构造器 Constructor |
---|
HashMap(): 默认的initialCapacity为16,loadFactor为0.75 |
HashMap(int initialCapacity):设定初始化容量 |
HashMap(int initialCapacity, float loadFactor):设定初始化容量和负载系数 |
TreeMap
NavigableMap接口的红黑树实现,具有排序的能力,默认情况对键值的进行默认的排序,也可以指定Comparator进行排序。TreeMap与普通 的Map不同的方法在于一些和键值顺序有关的函数,下面简要列举一下
方法 | 作用 |
---|---|
Map.Entry<K,V> ceilingEntry(K key) |
最小的键大于等于给定值的键值对 |
K ceilingKey(K key) |
最小的大于等于给定值的键 |
NavigableSet<K> descendingKeySet() |
降序排列的键集合 |
NavigableMap<K,V> descendingMap() |
按键降序排列的Map |
Map.Entry<K,V> firstEntry() |
键最小的键值对 |
K firstKey() |
最小的键 |
Map.Entry<K,v> floorEntry(K key) |
最大的键小于等于给定值的键值对 |
K floorKey(K key) |
最大的小于等于给定值的键 |
SortedMap<K,V> headMap(K toKey) |
返回小于给定键的所有键值对的一个map |
NavigableMap<K,V> headMap(K toKey, boolean inclusive) |
返回小于(或等于)给定键的所有键值对的一个map,如果没有则返回null |
Map.Entry<K,V> higherEntry(K key) |
最小的键严格大于给定键的键值对 |
K higherKey(K key) |
最小的严格大于给定键的键值对 |
Map.Entry<K,V> lastEntry() |
键最大的键值对 |
K lastKey() |
最大的键 |
Map.Entry<K,V> lowerEntry(K key) |
最大的键严格小于给定键的键值对 |
K lowerKey(K key) |
最大的严格小于给定键的键值对 |
Map.Entry<K,V> pollFirstEntry() |
删除并返回键最小的键值对 |
Map.Entry<K,V> pollLastEntry() |
删除并返回键最大的键值对 |
SortedMap<K,V> headMap(K toKey) |
返回大于等于给定键的所有键值对的一个map |
NavigableMap<K,V> headMap(K toKey, boolean inclusive) |
返回大于(或等于)给定键的所有键值对的一个map,如果没有则返回null |
集合 Set 接口
集合的方法就比较简单了,基本上都是之前的一些简单重复,简单列举一下
方法 | 方法 | 方法 |
---|---|---|
boolean add(E e) |
void clear() |
boolean contains(Object o) |
boolean equals(Object o) |
boolean isEmpty() |
boolean remove(Object o) |
int size() |
Object[] toArray() |
常用的集合类有HashSet(基于HashMap实现)以及它的子类LinkedHashSet。
参考资料
[1] Deque (Java Platform SE 8 ) (oracle.com)
[2] JAVA中HashMap和Hashtable区别 - 知我者,足以 - 博客园 (cnblogs.com)
[3] HashMap中的Initial Capacity和Load Factory - 我要去巴萨 - 博客园 (cnblogs.com)