数据结构学习笔记：链表基础(一)
一.学习链表的意义
链表是一种最重要的动态数据结构
更深入的理解引用(或者指针)
更深入的理解递归
组织更加复杂的数据结构
二.什么是链表(Linked List)
数据存储在"节点"(Node)中
优点：真正的动态，不需要处理固定容量的问题
缺点：失去了随机访问的能力
数组和链表的对比:
数组最好用与索引有语意的情况.scores[2]
最大的优点:支持快速查询
链表不适合用于索引有语意的情况
最大的优点:动态，插入和删除可以达到o(1)的复杂度
三.数据结构
1.单向链表
单向链表组成：
数据字段+指针字段
物理结构：
分散的，不必分配连续的内存
逻辑上的结构：
逻辑结构：
1.单向链表所有的节点都知道它下一个节点在哪里，却无法知道前一个节点在哪里，所以它的每一个节点需要维护一个链表头指针。
2.单向链表有第一个节点和最后一个节点的，最后一个节点指向的是null。
2.环形链表
环型链表组成：
数据字段+指针字段
物理结构：
分散的，不必分配连续的内存
逻辑结构：
1.单向链表最后一个节点指向的是null，为链弥补单向链表的不足，环形链表最后一个节点指向的是第一个节点。它的数据结构是没有第一个节点也没有最后一个节点的，每一个节点都是第一个节点。其它与单向数据结构一致。
3.双向链表
左指针字段+数据字段+右指针字段
物理结构：
分散的，不必分配连续的内存
逻辑结构：
1.所有的节点知道下一个节点在哪里也知道上一个节点在哪里。
2.通常会加上一个链表头，链表头不存放数据，左指针指向最后一个节点，右指针指向下一个节点。
四：LRUCache
数据结构：
创建：创建时必须指定最大长度
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
插入:使用双向链表来存储数据，插入操作时间复杂度为O(1),当LRUCache未满时，会在表头插入一条数据，当LRUCache已满时，会先在表头插入一条数据，再从表尾删除一条数据
/**
* Caches {@code value} for {@code key}. The value is moved to the head of
* the queue.
*
* @return the previous value mapped by {@code key}.
*/
@Nullable
public final V put(@NonNull K key, @NonNull V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
if (size <= maxSize || map.isEmpty()) {
break;
}
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
查询：使用HashMap来保存key与Node节点的对应关系，从而实现查询O(1)的复杂度。查询命中的把查到的数据移动到表头。
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot
* be created.
*/
@Nullable
public final V get(@NonNull K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
五:LinkedHashMap
LinkedHashMap是HashMap的子类，在HashMap基础上维护了一个双向链表,它可以保持插入顺序的LinkedHashMap，也可以保持访问顺序的LinkedHashMap。
数据结构：
每put一个数据先将其保存到哈希表中对应的位置上，再将其将其插入到双向链表的尾部。
实现的是HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
问题：它重写链HashMap的put方法怎么实现这个过年，LinkedHashMap重写了newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
head:双向链表头节点的header
tail:双向链表头节点的尾部
accessOrder:
值为true时，按照访问顺序存储,值为false时，表示按照插入顺序存储
get方法：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
注意这里afterNodeAccess方法，如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做；
如果是按照访问的先后顺序排序的话，则将e移到链表的尾处
链表相关资料连接：
算法与数据结构体系课
https://class.imooc.com/sc/105/learn
通俗易懂讲解 链表
https://zhuanlan.zhihu.com/p/29627391
链表实战（带图分析）
https://www.jianshu.com/p/9a4561d42e9a
LruCache
https://blog.csdn.net/u014106644/article/details/91797484
