相较于 ArrayList，LinkedList 在平时使用少一些。
LinkedList 内部是一个双向链表，并且实现了 List 接口和 Deque 接口，因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下：
前文分析了 Queue 和 Deque 接口，正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承结构如下：
结点类 Node
查看 LinkedList 的源码可发现它内部有个嵌套类 Node，代码如下：
private static class Node {
E item; // 存储的数据
Node next; // 后继结点
Node prev; // 前驱结点
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} LinkedList 是双向链表的实现，而该 Node 类则是链表的结点。
此外，LinkedList 还有几个成员变量如下：
// list 的长度
transient int size = 0;
// 链表头结点
transient Node first;
// 链表尾结点
transient Node last; 构造器
LinkedList 有两个构造器，如下：
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}PS: 由于链表的容量可以一直增加，因此没有指定容量的构造器。
其中第一个为无参构造器；第二个为使用指定的集合构造，并调用 addAll()，继续跟进该方法，代码如下：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// 将集合元素转为数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 获取当前链表的前驱和后继结点
Node pred, succ;
if (index == size) { // 尾结点的前驱和后继结点
succ = null;
pred = last;
} else { // 若非尾结点，获取指定位置的结点
succ = node(index);
pred = succ.prev;
}
// 循环将数组中的元素插入到链表
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 若插入到末尾，则数组中的最后一个元素就是尾结点
if (succ == null) {
last = pred;
} else {
// 若插入到指定位置，将数组中最后一个元素与下一个位置关联起来
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
} 其中 node(index) 方法为获取指定位置的结点，代码如下：
Node node(int index) {
// assert isElementIndex(index);
// 若下标在前一半，则从前往后遍历；否则从后往前遍历
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
} 该方法通过遍历链表获取指定的元素。
值得注意的是，该方法并非直接从头到尾遍历整个链表，而是先判断下标的位置，若在前一半则从前往后遍历；否则就从后往前遍历。这样能减少遍历结点的个数。
PS: 之前对链表进行过分析，由于其内存空间非连续，因此不支持随机访问（下标访问）。所以，查询某个结点是通过遍历整个链表来实现的。
与此同时，get(index) 方法内部也是这样实现的：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}常用方法
之前分析 Queue 和 Deque 的时候提到：Queue 中的方法在 Deque 中都有对应的。下面简单分析 LinkedList 中一些常用的方法。
新增结点方法：add(), addLast(), offerLast()
public boolean offerLast(E e) {
addLast(e);
return true;
}
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}可以看到他们都是调用了同一个方法 linkLast(e) 实现的，如下：
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
// 若链表为空，则新结点为头结点
if (l == null)
first = newNode;
// 若链表不为空，将新结点插入到链表尾部
else
l.next = newNode;
size++;
modCount++;
} 该操作就是将指定的结点添加到链表末尾。
删除结点方法：poll(), pollFirst(), removeFirst()
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
} 可以看到这三个方法都是调用 unlinkFirst() 方法实现的，其代码如下：
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
} 该方法的操作就是从链表头部移除一个结点。
向单链表插入和删除结点的操作示意图如下（双链表比这里多了前驱结点）：
栈的入栈（push）和出栈（pop）操作：
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
} 可以看到这两个方法直接调用了双端队列的实现方法。即，该栈是一个「链式栈」。
线程安全性
线程安全的概念不再赘述。分析以下场景：
若有线程 T1 对 LinkedList 进行遍历，同时线程 T2 对其进行结构性修改。
对 LinkedList 的遍历是通过 listIterator(index) 方法实现的，如下：
public ListIterator listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator {
private Node lastReturned;
private Node next;
private int nextIndex;
// 初始化时二者是相等的
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
// ...
// 是否有其他线程对当前对象进行结构修改
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
} 该类的 next(), add(e) 等方法在执行时会检测 modCount 与创建时是否一致（checkForComodification() 方法），从而判断是否有其他线程对该对象进行了结构修改，若有则抛出 ConcurrentModificationException 异常。
因此，LinkedList 是线程不安全的。
小结
1. LinkedList 内部是「双向链表」，同时实现了 List 接口和 Deque 接口，因此也具备 List、双端队列和栈的性质；
2. 线程不安全。
Map 是一个接口，它表示一种“键-值（key-value）”映射的对象（Entry），其中键是不重复的（值可以重复），且最多映射到一个值（可以理解为“映射”或者“字典”）。
Map 常用的实现类有 HashMap、TreeMap、ConcurrentHashMap、LinkedHashMap 等，它们的继承结构如下：
Map 的方法列表如下：
一些常用方法：
// 将键-值对存入 Map，若 key 对应的 value 已存在，则将其替换
// 返回原先 key 对应的 value（若不存在，返回 null）
V put(K key, V value);
// 将指定 Map 中的所有元素拷贝到本 Map 中
void putAll(Map<? extends K, ? extends V> m);
// 返回本 Map 中所有 key 的 Set 视图
Set keySet();
// 返回本 Map 中所有 value 的 Collection 视图
Collection values();
// 返回本 Map 中所有 Entry 的 Set 视图
// 其中 Entry 是 Map 内部的一个接口，可以理解为 Map 的“元数据”
Set> entrySet(); 此外，JDK 1.8 又增加了不少方法，如下：
// 获取 key 对应的 value，若 value 为 null，则返回 defaultValue
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
// 遍历 Map 中的元素
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
// 通过给定的函数计算出新的 Entry 替换所有旧的 Entry
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
// 若 key 对应的 value 不存在，则把 key-value 存入 Map，否则无操作
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
// 若 key 对应的值等于 value，则移除 key；否则无操作
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
// 若 key 对应的值等于 oldValue，则将其替换为 newValue；否则无操作
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
// Map 中存在 key 时，将 key-value 存入，相当于：
/*
if (map.containsKey(key)) {
return map.put(key, value);
} else
return null;
}
*/
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
// 当 key 对应的 value 不存在时，使用给定的函数计算得出 newValue
// 并将 key-newValue 存入 Map
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
// 当 key 对应的 value 存在时，使用给定的函数计算得出 newValue，
// 当 newValue 不为 null 时将 key-newValue 存入 Map；否则移除 key
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
// 根据 key 和其对应的 oldValue，使用给定的函数计算出 newValue
// 若 newValue 为 null
// 若 oldValue 不为空或 key 存在，则删除 key-oldValue
// 否则无操作
// 若 newValue 不为 null，用 newValue 替换 oldValue
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
} PS: 1.8 中的几个方法看似比较复杂，但有些方法实质上相当于对一些 if...else 语句的封装，利用 lambda 表达式可以让代码更简洁。
Entry 接口
Map 接口内部还定义了一个 Entry 接口（上面已经出现），它其实相当于 Map 内部存储的「元数据」，也就是 键-值（key-value） 映射。方法列表如下：
其中前面几个方法都比较简单，这里分析下后面几个 JDK 1.8 引入的方法，如下：
// 返回一个比较器，它以自然顺序比较 Entry 的 key
public static , V> Comparator> comparingByKey() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
// 返回一个比较器，它以自然顺序比较 Entry 的 value
public static > Comparator> comparingByValue() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
// 返回一个比较器，它使用给定的 Comparator 比较 Entry 的 key
public static Comparator> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
// 返回一个比较器，它使用给定的 Comparator 比较 Entry 的 value
public static Comparator> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
} 小结
1. Map 接口虽然没有继承自 Collection 接口，但也是 JCF(Java Collections Framework) 的一部分；
2. Map 存储的是键-值（key-value）映射结构的对象；
3. Entry 接口定义在其内部，它是真正定义键-值映射的结构，相当于 Map 的「元数据」。
页面更新：2024-05-10
本站资料均由网友自行发布提供，仅用于学习交流。如有版权问题，请与我联系，QQ：4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号
