get()
public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); 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; } }双向链表的作用在这里就体现出来了, 根据所查找位置的不同, 从末节点或首节点进行查找. 效率提升了一倍.
Iterator()
public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious(); public E previous(); public int nextIndex(); public int previousIndex(); public void remove(); public void set(E e); public void add(E e); public void forEachRemaining(Consumer<? super E> action); }在iterator() 的实现中, 仅仅给出所实现的 API, 发现它实现的功能相当全面. 如果我们需要在遍历的同时做出某些操作, 最好不要用 foreach() 的方法, 去遍历这个集合, 而是应该调用 listIterator() 可以选择更多更全面, 更合适的额外操作.
总结1
在种种方法中, 有如下几个特点:
同样的, 集合是无序的, 秉承着先进后出, 栈的数据存储原则.(这里的先进后出, 指的是在遍历的时候, 所遵循的策略) 同时实现了List的所有方法, 支持 在某一个位置进行插入, 修改, 删除操作, 又或者插入最前, 最后, 或不选择. 可以插入重复元素, 或者null值.
但也可能是因为支持的操作太多, 导致给我的感觉它很混乱, 不够清晰明了.
它支持的操作是如此之多, 我们又该在什么时候使用链表呢?
必须是查找的次数远远小于增删的时候使用, 它的每一次查找都需要进行遍历操作, 而相比于 ArrayList() 的增删, 每次都需要复制数组, 增删的成本相当低廉.
同样的, 不适合在需要比较大小的场合里进行使用, 在对存储数据的要求上, 发现仅仅需要 equals()方法, 至于数据的大小, 是漠不关心的.
所以在需要排序的种种场合, ArrayList和LinkedList实在不是一个好选择.
但接下来再谈谈另一个地方, 会发现 LinkedList中, 不仅仅实现了List接口, 还有很多其他方法.
Deque
LinkedList还实现了另一个接口, Deque, 我们先来看看这个接口的API, 这个接口继承了另一个接口: Queue.
是的, 队列: add(E), offer(E), remove(), poll(), element(), peek();
队列的特点是先进先出. 实现也有两种方式, 数组和链表, 当然,双向链表是最合适的.
然而, LinkedList中不仅仅是实现了队列, 而是 Double ended Queue.叫做双向队列. 双向队列允许在头尾分别进行操作.
但是感觉API设计仍旧有难以理解的地方, poll() 和 pollFirst() 操作, 完全相同的定义和实现, 不太明白有什么区别.
Deque的设计同样让人感觉很混乱, 难以理解.
在这里就不看它的各种实现了, 因为是基于链表的操作, 当双向链表的操作不成问题的时候, 自然对于LinkedList的所有问题都不存在了.
总结2
在这里再回头看看 LinkedList这个数据结构, 在LinkedList来看, 才更近一步理解了, 在创建对象的时候一定要以接口来定义数据类型.
LinkedList集成了众多需要链表来实现的API, 在使用的时候最好明确, 究竟想要使用的是List 还是 队列. 又或者双向队列更适合你.
List的话, 需要重点关注的特点是: 增删操作远远大于查找操作. 而 队列的话, 就不用多说, 常规操作.
HashMap
散列表
在HashMap中, 有两个数据至关重要, 容量 和 负载因子. 在谈到这个数据的时候, 就需要来看另一个很有趣的数据类型.散列表.
散列表这种数据类型比较简单, 无论是从原理还是从实现来看, 首先说原理:
底层是数组, 存有两个数组, 一个保存键一个保存值, 又或者创建一个新的数据类型 Node, 保存键值对, 在数组中保存Node即可.
至于数据如何存储在散列表中呢?
无论哪一种方式都需要计算对应的散列值, 也就是用某一个数字 % 数组的容量, 所得的数就是当前元素在数组中所存储的位置. 至于查找的话, 同样的方式, 用求余所得的数字, 通过Array的索引去查找. 即可完成这一点.
所以关键点就在于这个数字怎么求取? 怎样的要求, 怎样的特点?
这个数字的求取尤为关键, 关系着散列表的性能. 称作散列函数.