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

  1. 实现方法 :java中数组转list使用Arrays.asList(T... a)方法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public 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);
    }
    }
  2. 注意事项

    1)Arrays.asList()方法返回的对象是Arrays的内部类,对list的操作仍然反映在原数组上,因此这个list是定长的,不支持add、remove操作;

    2)由于asList方法接受的泛型参数,因此不能用于基本类型,只能使用如下方法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public 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

  1. 实现:使用list.toArray()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public 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);
    }
    }
    }

  2. 注意事项

    由于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)