社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
转载自：https://www.cnblogs.com/xdecode/p/9321848.html
最近在整理数据结构方面的知识, 系统化看了下Java中常用数据结构, 突发奇想用动画来绘制数据流转过程.
主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的.
HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下:
经典的双链表结构, 适用于乱序插入, 删除. 指定序列操作则性能不如ArrayList, 这也是其数据结构决定的.
add(E) / addLast(E)
add(index, E)
这边有个小的优化, 他会先判断index是靠近队头还是队尾, 来确定从哪个方向遍历链入.
1 if (index < (size >> 1)) {
2 Node<E> x = first;
3 for (int i = 0; i < index; i++)
4 x = x.next;
5 return x;
6 } else {
7 Node<E> x = last;
8 for (int i = size - 1; i > index; i--)
9 x = x.prev;
10 return x;
11 }
靠队尾
get(index)
也是会先判断index, 不过性能依然不好, 这也是为什么不推荐用for(int i = 0; i < lengh; i++)的方式遍历linkedlist, 而是使用iterator的方式遍历.
remove(E)
底层就是一个数组, 因此按序查找快, 乱序插入, 删除因为涉及到后面元素移位所以性能慢.
add(index, E)
扩容
一般默认容量是10, 扩容后, 会length*1.5.
remove(E)
循环遍历数组, 判断E是否equals当前元素, 删除性能不如LinkedList.
经典的数据结构, 底层也是数组, 继承自Vector, 先进后出FILO, 默认new Stack()容量为10, 超出自动扩容.
push(E)
pop()
Stack的一个典型应用就是计算表达式如 9 + (3 - 1) * 3 + 10 / 2, 计算机将中缀表达式转为后缀表达式, 再对后缀表达式进行计算.
中缀转后缀
计算后缀表达
与Stack的区别在于, Stack的删除与添加都在队尾进行, 而Queue删除在队头, 添加在队尾.
ArrayBlockingQueue
生产消费者中常用的阻塞有界队列, FIFO.
put(E)
put(E) 队列满了
1 final ReentrantLock lock = this.lock;
2 lock.lockInterruptibly();
3 try {
4 while (count == items.length)
5 notFull.await();
6 enqueue(e);
7 } finally {
8 lock.unlock();
9 }
take()
当元素被取出后, 并没有对数组后面的元素位移, 而是更新takeIndex来指向下一个元素.
takeIndex是一个环形的增长, 当移动到队列尾部时, 会指向0, 再次循环.
1 private E dequeue() {
2 // assert lock.getHoldCount() == 1;
3 // assert items[takeIndex] != null;
4 final Object[] items = this.items;
5 @SuppressWarnings("unchecked")
6 E x = (E) items[takeIndex];
7 items[takeIndex] = null;
8 if (++takeIndex == items.length)
9 takeIndex = 0;
10 count--;
11 if (itrs != null)
12 itrs.elementDequeued();
13 notFull.signal();
14 return x;
15 }
最常用的哈希表, 面试的童鞋必备知识了, 内部通过数组 + 单链表的方式实现. jdk8中引入了红黑树对长度 > 8的链表进行优化, 我们另外篇幅再讲.
put(K, V)
put(K, V) 相同hash值
resize 动态扩容
当map中元素超出设定的阈值后, 会进行resize (length * 2)操作, 扩容过程中对元素一通操作, 并放置到新的位置.
具体操作如下:
1 //定义两条链
2 //原来的hash值新增的bit为0的链，头部和尾部
3 Node<K,V> loHead = null, loTail = null;
4 //原来的hash值新增的bit为1的链，头部和尾部
5 Node<K,V> hiHead = null, hiTail = null;
6 Node<K,V> next;
7 //循环遍历出链条链
8 do {
9 next = e.next;
10 if ((e.hash & oldCap) == 0) {
11 if (loTail == null)
12 loHead = e;
13 else
14 loTail.next = e;
15 loTail = e;
16 }
17 else {
18 if (hiTail == null)
19 hiHead = e;
20 else
21 hiTail.next = e;
22 hiTail = e;
23 }
24 } while ((e = next) != null);
25 //扩容前后位置不变的链
26 if (loTail != null) {
27 loTail.next = null;
28 newTab[j] = loHead;
29 }
30 //扩容后位置加上原数组长度的链
31 if (hiTail != null) {
32 hiTail.next = null;
33 newTab[j + oldCap] = hiHead;
34 }
继承自HashMap, 底层额外维护了一个双向链表来维持数据有序. 可以通过设置accessOrder来实现FIFO(插入有序)或者LRU(访问有序)缓存.
put(K, V)
get(K)
accessOrder为false的时候, 直接返回元素就行了, 不需要调整位置.
accessOrder为true的时候, 需要将最近访问的元素, 放置到队尾.
removeEldestEntry 删除最老的元素
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
目录
JDK api对LinkedList的介绍：
Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
大意是LinkedList基于双向链表实现了List接口和Deque(double ended queue 双向队列)接口，允许插入任意对象，包括Null。LinkedList是一个在平常开发中经常使用的类，由于它是基于链表实现的，插入删除相对于ArrayList需要考虑动态扩容，复制原数组到新数组来说，非常简单。它实现了Deque接口，在我们需要进行先进先出FIFO操作时非常方便。
LinkedList 是一个继承于AbstractSequentialList的双向链表，AbstractSequentialList 提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。实现了List接口,实现了Deque,Queue接口，能够进行队列先进先出FIFO操作。
内部类Node实现双向链表的基础。
private static class Node<E> {
//数据域
E item;
//指向下一个节点
Node<E> next;
//指向上一个节点
Node<E> prev;
//构造方法
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//表示链表的长度
transient int size = 0;
//链表的第一个节点
transient Node<E> first;
//链表的最后一个节点
transient Node<E> last;
无参构造方法
提供的无参构造方法是一个空方法，即size为0，first，last为null。因为LinkedList是链表结构，不必要像ArrayList去初始化底层数组。
public LinkedList() {
}
有参构造方法
首先调用无参构造方法，再调用addAll方法，在后面详细介绍这个方法。
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
add(E e)
add方法主要调用了linkLast方法，也就是从链表尾部插入元素，首先新建一个节点，它的前一个节点是链表的尾部节点，下一个节点为空，再将last指向这个新插入的节点，如果之前的last不为空（即链表不是第一次插入元素），我们把之前的last节点的next指向现在的last节点，如果为空，说明我们是第一次插入元素，之前的first，last都为null,那我们就把first也只想新插入的节点。下图展示了链表的结构和插入过程：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
add(int index, E element)
把新元素插入链表指定索引位置index处。首先检查待插入位置index是否合法(0<=index<=size),如果index不合法，抛出异常。index在范围内，若index等于size，就表示要把这个新元素插入到LinkedList的末尾，调用linkLast方法；否则，说明要把这个新元素插入到LinkedList的中间,调用linkBefore方法，把元素插入到指定节点的前面，需要传入两个参数：插入数据e,节点，我们使用node(int index)找到这个节点，作为传入参数，linkBefore具体注释在代码里。
由此可以看出，LinkedList插入元素相对简单，只需要找到插入元素的位置并改变指向前一个节点和指向后一个节点，就能够顺利的插入元素，这是由于链表的特性决定的。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//找到succ的上一个节点
final Node<E> pred = succ.prev;
//新节点插入到前继节点pred,后继节点succ之间
final Node<E> newNode = new Node<>(pred, e, succ);
//后继节点的prev指向新节点
succ.prev = newNode;
//前继节点pred为空，则新节点作为首节点first，否则把前一个节点的next指向新节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//如果index<size/2,从前半部分找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
addAll(Collection<? extends E> c)
LinkedList的有参构造方法调用了addAll(Collection<? extends E> c)方法，将一个集合对象保存的元素插入到LinkedList的末尾。首先调用toArray方法将集合对象转换为数组，再找到插入位置的前继节点pred和后继节点succ,然后把数组中的元素依次连接到链表上去。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
//Collection对象转换为Object数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//pred插入位置的前继节点，succ插入位置
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//将数组元素连接到链表上，每次通过节点Node构造方法指定前继节点
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//根据succ插入位置节点是否为空确定for循环最后一个元素的后继节点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
get(int index)
通过索引找到这个位置节点，返回这个节点保存的数据。首先检查元素索引是否合法（注意与插入位置索引的范围区别，插入元素可以到size，作为最后一个元素，查找元素最大只能到size-1），索引合法，通过node(int index)方法找到这个元素。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
set(int index, E element)
将指定索引位置处节点保存的值设置为新的传入的数据，并返回保存的老的数据。set方法的实现其实就比get方法多一步：把原来的数据替换为新的数据。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
remove(int index)
根据索引找到对应位置的节点，将节点移除，返回移除节点的数据。首先通过checkElementIndex检查传入的索引是否合法，索引在范围内，调用node(int index)找到这个节点，调用unlink移除这个节点，首先保存待移除节点x的下一个节点next,上一个节点prev,如果prev为空，说明待移除的节点是首节点，那么移除了这个节点，下一个节点就是首节点；prev不为空，将prev的next指向next节点，待移除节点x的prev置为空。如果next为空，说明待移除节点是末尾节点，那么移除了这个节点，上一个节点prev就是末尾节点了；若不为空，把next的prev指向prev节点，同时把待移除节点的next置为空。
移除节点主要分为两部，把待移除节点的前后两个节点相互连接起来，把节点从链表移除；把待移除节点的prev,next置为空，和链表断除联系。正好是插入的逆过程。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
offer(E e)
Deque接口继承了Queue接口，LinkedList实现了队列先进先出的特性，offer方法将元素插入到队列，调用了linkLast方法。
public boolean offer(E e) {
return add(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
poll()
从队列中取出元素，队列中取元素肯定是从队列的头部取元素，并返回节点保存的值。(f == null) ? null : unlinkFirst(f)三目表达式判断首节点是否为空，若为空直接返回null,不为空，调用unlinkFirst方法。通过调用unlinkFirst方法移除首节点。
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
//保存首节点的下一个节点next
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
//next为空，那么总共只有一个节点，直接令last为空，不为空的话next就是首节点，把它的prev指向null
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
remove()
从队列中取出元素，这个方法与poll方法唯一的差别是首节点是空的话remove方法会抛异常，poll方法不会。JDK的解释：Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.从队列取出元素还是建议用poll方法。
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
peek()
返回队列首节点保存的值，不从队列中移除首节点。只通过一个三目运算符就实现了功能。
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
push(E e)
Deque接口代表着双端队列，那么意味着也能从队首插入元素，队尾取出元素。push方法表示将这个LinkedList作为一个先进后出的栈Stack使用。从栈的顶部插入元素，也就是从list的头部插入元素，调用了linkFirst方法。
public void push(E e) {
addFirst(e);
}
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
//新元素作为首节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
pop()
pop方法表示将这个LinkedList作为一个先进后出的栈Stack使用。从栈的顶部取出元素，调用了removeFirst方法。
public E pop() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
listIterator()
通过iterator或listIterator方法返回一个ListIterator迭代器，迭代器是通过一个内部类ListItr实现ListIterator接口实现的。
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
ListItr内部类
使用foreach遍历最终是通过迭代器来进行遍历的，由于LinkedList是线程不安全的，所以迭代时通过比较modCount值是否改变来判断是否有其他线程在使用LinkedList。
private class ListItr implements ListIterator<E> {
//上一个迭代元素
private Node<E> lastReturned;
//下一个要迭代的元素
private Node<E> next;
//下一个迭代元素的下标
private int nextIndex;
private int expectedModCount = modCount;
//调用iterator方法默认index为零，从头开始遍历
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
//判断是否还有没有遍历完的元素，比较下一个元素的下标与size的大小关系
public boolean hasNext() {
return nextIndex < size;
}
//把lastReturned,next依次向后移，并返回之前next指向元素保存的数据
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
//与next配合使用
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
//比较是否有多个线程操作LinkedList,确保fail-fast机制
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
LinkedList是基于双向链表实现的List,适用于频繁增加、删除元素的场景，LinkedList不是线程安全的，在多线程环境下不能
正常的使用。LinkedList的源码总体上分析比较简单，但是LinkedList的功能很多的，能做普通的List使用，LinkedList实现了双向队列Deque,也可以做先入先出的队列或先入后出的栈使用。
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
