- the Java collection library separates interfaces and implementations
Add
Get and Set
Offer, Peek, Poll
Pop, Push
Remove
Utilities
void clear(): Removes all of the elements from this list.
Object clone(): Returns a shallow copy of this LinkedList.
boolean contains(Object o): Returns true if this list contains the specified element.
int indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
int size(): Returns the number of elements in this list.
Object[] toArray(): Returns an array containing all of the elements in this list in proper sequence (from first to last element).
Add
delete
set, get, replace
E get(int index): Returns the element at the specified position in this list.
E set(int index, E element): Replaces the element at the specified position in this list with the specified element.
void replaceAll(UnaryOperator<E> operator): Replaces each element of this list with the result of applying the operator to that element.## Sets
Utilities
void clear(): Removes all of the elements from this list.
Object clone(): Returns a shallow copy of this ArrayList instance.
boolean contains(Object o): Returns true if this list contains the specified element.
void forEach(Consumer<? super E> action): Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
int indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
Object[] toArray(): Returns an array containing all of the elements in this list in proper sequence (from first to last element).
“only arrayList”
boolean isEmpty(): Returns true if this list contains no elements.
int size(): Returns the number of elements in this list.
void sort(Comparator<? super E> c): Sorts this list according to the order induced by the specified Comparator.
void trimToSize(): Trims the capacity of this ArrayList instance to be the list's current size.
void ensureCapacity(int minCapacity): Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
insert and delete
- ArrayList: O(n), 因为要将目标位置之后的元素向前移位(delete)或者向后移位(insert),
如果超出capacity则需要扩容会增加时间复杂度- LinkedList: O(n), 需要遍历linkedlist找到node, 然后进行操作: O(1)
set and get
- ArrayList: O(1), 通过下标直接操作
- LinkedList: O(n) 需要遍历linkedlist找到node, 然后进行操作
“space”
- ArrayList: 只需数组的空间
- LinkedList: 有overhead, 比如next,pre指针
Summary
- 很多场景下ArrayList更受欢迎
- Queue: 在尾部加入元素, 从头部删除元素
- Deque (double-ended queue): 可以从头部或者尾部加入删除元素
- 可以用LinkedList替代(LinkedList提供了Queue和Deque功能)
package priorityQueue;
import java.util.*;
import java.time.*;
/**
* This program demonstrates the use of a priority queue.
* @version 1.02 2015-06-20
* @author Cay Horstmann
*/
public class PriorityQueueTest
{
public static void main(String[] args) {
PriorityQueue<LocalDate> pq = new PriorityQueue<>();
pq.add(LocalDate.of(1906, 12, 9)); // G. Hopper
pq.add(LocalDate.of(1815, 12, 10)); // A. Lovelace
pq.add(LocalDate.of(1903, 12, 3)); // J. von Neumann
pq.add(LocalDate.of(1910, 6, 22)); // K. Zuse
System.out.println("Iterating over elements...");
for (LocalDate date : pq)
System.out.println(date);
System.out.println("Removing elements...");
while (!pq.isEmpty())
System.out.println(pq.remove());
}
}
- 无序的set
- 使用HashTable实现 bucket hashing (Array + LinkedList)
- 默认bucket大小是 2^16, load factor是0.75
public class SetTest
{
public static void main(String[] args) {
Set<String> words = new HashSet<>(); // HashSet implements Set
long totalTime = 0;
try (Scanner in = new Scanner(System.in)) {
while (in.hasNext()) {
String word = in.next();
long callTime = System.currentTimeMillis();
words.add(word);
callTime = System.currentTimeMillis() - callTime;
totalTime += callTime;
}
}
Iterator<String> iter = words.iterator();
for (int i = 1; i <= 20 && iter.hasNext(); i++)
System.out.println(iter.next());
System.out.println(". . .");
System.out.println(words.size() + " distinct words. " + totalTime + " milliseconds.");
}
}
LinkedHashSet
是HashSet的一个子类, 元素按照加入顺序排序
- 有序的Set
- 使用红黑树实现
- TreeSet的插入复杂度要比HashSet快, 但是检查重复要比HashSet快(LogN)
- 因为是有序的所以必须重新
compareTo否则会报错, String等非自定义类型已经重写了compareTo方法- 如果数据不要求排序最好使用HashSet
public class TreeSetTest {
public static void main(String[] args) {
SortedSet<Item> parts = new TreeSet<>();
parts.add(new Item("Toaster", 1234));
parts.add(new Item("Widget", 4562));
parts.add(new Item("Modem", 9912));
System.out.println(parts);
NavigableSet<Item> sortByDescription = new TreeSet<>(
Comparator.comparing(Item::getDescription));
sortByDescription.addAll(parts);
System.out.println(sortByDescription);
}
}
- element是enum类型
- Since an enumerated type has a finite number of instances, the EnumSet is internally implemented simply as a sequence of bits.
- A bit is turned on if the corresponding value is present in the set.
enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);
- Map没有继承Collection接口
- AbstractMap和AbstractCollection是平级关系
package map;
import java.util.*;
/**
* This program demonstrates the use of a map with key type String and value type Employee.
* @version 1.12 2015-06-21
* @author Cay Horstmann
*/
public class MapTest {
public static void main(String[] args) {
Map<String, Employee> staff = new HashMap<>();
staff.put("144-25-5464", new Employee("Amy Lee"));
staff.put("567-24-2546", new Employee("Harry Hacker"));
staff.put("157-62-7935", new Employee("Gary Cooper"));
staff.put("456-62-5527", new Employee("Francesca Cruz"));
// print all entries
System.out.println(staff);
// remove an entry
staff.remove("567-24-2546");
// replace an entry
staff.put("456-62-5527", new Employee("Francesca Miller"));
// look up a value
System.out.println(staff.get("157-62-7935"));
// iterate through all entries
staff.forEach((k, v) ->
System.out.println("key=" + k + ", value=" + v));
}
}
the set of keys: 将所有的key作为一个set返回
Set<K> keySet()
Set<String> keys = map.keySet();
for (String key : keys) {
do something with key
}
the collection of values (which is not a set): 将所有的value作为一个collection返回
Collection<V> values()
Map<String,String> map=new HashMap<>();
map.put("abc","123");
map.put("efg","456");
// 使用增强型for遍历循环Map集合
Collection<String> values = map.values();
for (String value : values) {
System.out.println(value);
}
the set of key/value pairs: 得到每一对key value pair
Set<Map.Entry<K, V>> entrySet()
for (Map.Entry<String, Employee> entry : staff.entrySet()) {
String k = entry.getKey();
Employee v = entry.getValue();
do something with k, v
}
HashMap
- Hash table based implementation of the Map interface
- the default load factor (.75)
- 有一个子类为LinkedHashMap, 元素按照加入顺序排序
TreeMap
- A Red-Black tree based NavigableMap implementation.
- 需要根据compareTo排序
EumerateHashMap
- A specialized Map implementation for use with enum type keys.
- All of the keys in an enum map must come from a single enum type that is specified
WeakHashMap
- Hash table based implementation of the Map interface, with weak keys.
- An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use
Collection To Array
Object[] values = staff.toArray();
- 但是values的类型是Object并且不能转换类型
String[] values = (String[]) staff.toArray(); // Error!- 可以用如下写法:
String[] values = staff.toArray(new String[staff.size()]);
Array To Collection
Arrays.asList()
String[] values = . . .;
HashSet<String> staff = new HashSet<>(Arrays.asList(values)); //所有的collection都可以通过另外一个collection初始化