链表的再次深入

链表的再次深入"/>

链表的再次深入

链表的底层存储结构

相对比于数组，链表更加复杂，在底层存储结构上，链表的特定与数组也截然不同。

数组需要一块连续的内存空间进行存储，对内存的要求比较高，假如我们需要创建一个数组需要申请100MB的内存空间，但是内存中没有连续的存储空间时，即使剩余的内存空间大于100MB,也会申请失败。

而链表却与之相反，它并不需要一块连续的内存空间，链表通过“指针”，将一块块零散的内存块（一般在链表中称之为节点）串联起来，这样就有效避免了因没有连续的内存而导致创建失败的问题。

但是两种不同的数据结构决定了两者有着不同的优势，想比于数组，链表更见适合插入和删除操作。

链表的定义和操作

在链表中，为了将所有的结点串联起来，每个结点除了存储数据本身外，还需要额外的存储下一个结点的地址，我们把记录下一个结点地址的指针称为next指针。

从图中可以看出，有两个结点比较特殊，一个是第一个结点一个是最后一个结点。我们把第一个结点称为头结点，通常用来存储链表的基地址，也就是起始地址，我们从头结点开始，可以遍历整个链表。尾结点是链表最后一个结点，他的next指针不是指向最后一个结点，而是指向一个空地址，在java中用null表示。

下面看看链表的定义

public class LinkedList{public class Node{public int data;public Node next;}private Node head = null;
}

数组为了保证数据的连续性，插入和删除需要进行数据的搬移，时间复杂度较高，但是对于链表来说，因为其本身的存储空间是不连续的，所以只需要去操作他的地址就可以实现对结点的插入和删除操作。相对于数组来说，插入和删除操作更加的高效，时间复杂度尾O(1).

下面看看查找，插入，删除操作的代码。

//查找
public Node find(int value){Node p = head;while(p != null && p.data != value){p = p.next;}return p;
}
//插入
void insert(Node b,Node x){//在结点b后插入新的结点if(b == null){x.next = head;head = x;} else {x.next = b.next;b.next = x;}
}
//删除
void remove(Node a,Node b){//在已知前驱结点a的情况下，删除结点bif(a == null){head = head.next;} else {a.next = a.next.next;}
}

 链表的数据并非是连续存储的，想要查找第k个元素，需要从链表的头结点开始，依次遍历结点。下面看看代码。

public Node get(int k){Node p = head;int i = 0;while(p != null && i != k){i++;p = p.next;}return p;
}

因为链表没有随机寻址的特性，查找元素需要顺序遍历，所以在查找元素上没有数组高效，时间复杂度为O(n);

链表的变形结构

循环链表是一种特殊的单链表，与单链表唯一的区别就是尾结点，单链表的尾结点指向的为一个空地址null，而循环链表指向的是一个头结点。和单链表相比，循环链表的优点是从链尾遍历到链头比较方便，当处理的数据具有环形结构的特定时，用循环链表比较方便，比如著名的约瑟夫环问题。（文章结尾写上约瑟夫环代码）

接下来看看双向链表

单链表只有一个遍历方向，而双向链表有两个遍历方向，一个pre指针（用来指向它前面的那个结点），一个next指针。

下面看看双向链表的定义

public class DoubleLinkedList{public class Node{public int data;public Node pre;public Node next;}private Node head = null;
}

 从图中可以看出存储同样多的数据，因为pre指针的存在，使得一个结点会占用更多的内存空间，但是这样也是会有好处，会给查找前驱结点带来方便。这时候可能会有疑问，单链表的插入、删除的时间复杂度已经很高了O(1)，双向链表怎么还能高效，其实单链表的插入删除是有条件的，我们都需要从表头遍历要查找元素的值。

在实际开发中，从链表中删除一个数据无非两种情况。一种是删除“值等于给定值”的结点，一种是删除给定指针指向的结点。

第一种情况：

//在单链表中删除等于val中的值
public void remove(int val){Node q = head;Node p = null;//遍历查找qwhile(q != null && q.data != val){p = q;q = q.next;}if(q != null){if(p == null){//q是头结点head = q.next;} else {p.next = q.next;}}
}//在双向链表中删除值等于val的节点
public void remove(int val){Node q = head;while(q != null && q.data != val){q = q.next;}//找到val值if(q != null){if(q.pre == null){head = q.next;} else {q.pre.next = q.next;}}
}

尽管单纯的删除操作的时间复杂度是O(1)，但是遍历查找的时间复杂度是O(n),因此无论是单链表还是双链表，对应的时间复杂度为O(n)。

第二种情况

对于第二种情况，尽管我们已经找到要删除的节点，但是删除节点q需要直到前驱节点，而单链表并不支持直接获取前驱节点，因此为了找到节点q的前驱节点，我们需要从头遍历链表，直到p.next = q为止。说明节点p就是节点q的前驱节点。所以单链表的时间复杂度为O(n)，又因为双向链表提前保存了前驱结点的地址，不需要遍历查找结点，此时的时间复杂度为O(1)。

看代码

//单链表中删除节点q
void remove(Node q){if(q == null){return;}if(head == q){head = q.next;}Node p = head;while(p.next != null && p.next !=q){p = p.next;}if(p.next != null){p.next = q.next;}
}
//双向链表中删除节点q
void remove(Node q){if(q == null){return;}if(q.pre == null){head = q.next;return;}q.pre.next = q.next.next;
}

同理，对于在某个指定节点面前插入一个节点，双向链表的效率也是比单链表要高。如果把循环链表和双向链表整合在一起，就形成了双向循环链表。

约瑟夫环问题

//约瑟夫环java实现
//约瑟夫环问题的起源来自犹太历史学家约瑟夫和他的朋友以及39其余的犹太人，总共41人为了躲避敌人，藏在一个山洞中，
//39个犹太人决定宁愿死也不被敌人抓到，于是决定自杀，所有人排成一个圈，由第一个人开始报数，每当数到3，就自杀。
//这个游戏接着从自杀的位置开始，还是从1数到3。依次类推，约瑟夫将朋友和自己安排在了16和31的位置，最后顺利逃过了
//自杀这一劫，因为最后就剩他一个人了
public class Node{public int data;public Node next;public Node(){}public Node(int data){this.data = data;}
}public class JosefCircleMain {public static void count(int n){//数到三的时候出局int k = 3;//创建头结点Node head = new Node();Node cur = head;//循环创建节点for(int i=1;i<=n;i++){Node node = new Node(i);cur.next = node;cur = node;}//有数据的部分成为一个环cur.next = head.next;//创建一个指针指向head.nextNode p = had.next;//循环退出的条件是最后只剩一个结点，也就是这个结点的下一个结点是它本身while(p.next!=p){//正常报数的遍历逻辑for(int i=1;i<k-1;i++){p = p.next;}//当数到3的时候，出局System.out.print(p.next.data+"->");p.next = p.next.next;p = p.next;}//最后剩下的一个结点System.out.println("(left:"+p.data+")");}
}

 LRU缓存淘汰算法

import java.util.LinkedHashMap;
import java.util.Collection;
import java.util.Map;
import java.util.ArrayList;/**
* An LRU cache, based on <code>LinkedHashMap</code>.
*
* <p>
* This cache has a fixed maximum number of elements (<code>cacheSize</code>).
* If the cache is full and another entry is added, the LRU (least recently used) entry is dropped.
*
* <p>
* This class is thread-safe. All methods of this class are synchronized.
*
* <p>
* Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br>
* Multi-licensed: EPL / LGPL / GPL / AL / BSD.
*/
public class LRUCache<K,V> {private static final float   hashTableLoadFactor = 0.75f;private LinkedHashMap<K,V>   map;
private int                  cacheSize;/**
* Creates a new LRU cache.
* @param cacheSize the maximum number of entries that will be kept in this cache.
*/
public LRUCache (int cacheSize) {this.cacheSize = cacheSize;int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1;map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) {// (an anonymous inner class)private static final long serialVersionUID = 1;@Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {return size() > LRUCache.this.cacheSize; }}; }/**
* Retrieves an entry from the cache.<br>
* The retrieved entry becomes the MRU (most recently used) entry.
* @param key the key whose associated value is to be returned.
* @return    the value associated to this key, or null if no value with this key exists in the cache.
*/
public synchronized V get (K key) {return map.get(key); }/**
* Adds an entry to this cache.
* The new entry becomes the MRU (most recently used) entry.
* If an entry with the specified key already exists in the cache, it is replaced by the new entry.
* If the cache is full, the LRU (least recently used) entry is removed from the cache.
* @param key    the key with which the specified value is to be associated.
* @param value  a value to be associated with the specified key.
*/
public synchronized void put (K key, V value) {map.put (key, value); }/**
* Clears the cache.
*/
public synchronized void clear() {map.clear(); }/**
* Returns the number of used entries in the cache.
* @return the number of entries currently in the cache.
*/
public synchronized int usedEntries() {return map.size(); }/**
* Returns a <code>Collection</code> that contains a copy of all cache entries.
* @return a <code>Collection</code> with a copy of the cache content.
*/
public synchronized Collection<Map.Entry<K,V>> getAll() {return new ArrayList<Map.Entry<K,V>>(map.entrySet()); }} // end class LRUCache
------------------------------------------------------------------------------------------
// Test routine for the LRUCache class.
public static void main (String[] args) {LRUCache<String,String> c = new LRUCache<String, String>(3);c.put ("1", "one");                           // 1c.put ("2", "two");                           // 2 1c.put ("3", "three");                         // 3 2 1c.put ("4", "four");                          // 4 3 2if (c.get("2") == null) throw new Error();    // 2 4 3c.put ("5", "five");                          // 5 2 4c.put ("4", "second four");                   // 4 5 2// Verify cache content.if (c.usedEntries() != 3)              throw new Error();if (!c.get("4").equals("second four")) throw new Error();if (!c.get("5").equals("five"))        throw new Error();if (!c.get("2").equals("two"))         throw new Error();// List cache content.for (Map.Entry<String, String> e : c.getAll())System.out.println (e.getKey() + " : " + e.getValue()); }

代码出自： An LRU cache class based on java.util.LinkedHashMap