上次我们简单的对比了一下数组和链表的区别和各自的优缺点，今天我们来详细看一下链表这个结构。
链表的结构五花八门，我们几天主要看一下三种最常用的链表结构：单链表、双向链表和循环列表。
- 单链表
我们首先来看一下最简单、最常用的单链表。前边我们已经知道链表是通过指针将一些分散的内存块连接到一起。其中，我们把每个内存块叫做链表的一个结点。为了将每个结点连接到一起，每个结点不仅存储数据，而且还需要记录下一个结点的地址。我们把这个记录下一个结点的指针称为后继指针next。我们通过下边示意图来更形象的了解一下。
image.png
从图中我们可以看到，单链表是单方向顺序的一个线性表。其中有两个结点比较特殊，分别是第一个和最后一个结点。我们通常把第一个结点叫做头结点，最后一个结点叫做尾结点，头结点用来记录链表的基地址，这样我们就可以遍历得到整个结点，尾结点是最后一个结点，它的指针指向一个空地址NULL，这样我们通过判断后继指针next是不是NULL来确定某个结点是不是尾结点。
前边我们在数组和链表中已经详细介绍了链表的插入和删除，在这里我们不做过多的描述，而是通过示意图的方式更清楚的了解。针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度为O(1)。
image.png
- 双向链表
单链表只有一个指针，每个结点都只有一个后继指针next指向下一个结点的地址。而双向链表，顾名思义，它有两个方向，所以每个结点不仅有一个指向下一个结点的后继指针next，还有一个指向前一个结点的前驱结点prev。同样我们通过示意图来看一下。
image.png
从图中我们看到，与单链表相比，双向链表的每个结点还需要存储指向前一个结点的指针，所以，同样多的数据，双向链表比单链表需要更多的存储空间。两个指针虽然比较浪费空间，但是双向链表可以双向遍历，灵活性更高。
双向链表在删除、插入结点上更加高效，前边我们讲过单链表的删除和插入操作的时间复杂度为O(1)，但是双向链表的为什么会更高效呢，因为单链表的分析只是理论上得到的，但是实际情况中是不准确的，是需要前提条件的。
下面我们分析一下实际情况中的操作。我们先来看插入操作，实际情况中的插入操作可以分为这两种情况：
- 在值等于某个指定值的结点前或者后插入结点
- 在给定指针后边插入结点
对于第一种情况，不管是单链表还是双向链表，都需要从头一个一个遍历直到找到特定值的结点，然后执行插入操作虽然插入的时间复杂度为O(1)，但是遍历的时间复杂度为O(n)，所以在值等于某个指定值的结点前或者后插入结点的时间复杂度为O(n)。
对于第二种情况，我们通过给定指针可以直到插入结点的位置，但是我们需要直到给定指针的前驱结点，如果是单链表，我们依然需要通过从头开始遍历找到前驱结点，需要的时间复杂度为O(n)，但是对于双向链表就简单多了，我们只需要通过前驱结点的指针就能得到前驱结点，需要的时间复杂度为O(1)。
同理，参照我们上边插入操作的分析，删除结点双向链表同样比单链表灵活得多。
还有就是在有序链表中，双向链表的按值查询也比单链表也快一些，因为我们可以记录上次查找的位置x，然后通过比较查询值x的大小来决定向前还是向后，可以比单链表节省时间。
通过上边单链表和双向链表的比较，我们有学习了灵位一个非常重要的知识点，那就是用空间换时间的思想，当内存空间充足时，如果我们对执行效率有更高的要求，可以用牺牲内存而换取效率的办法，也就是选择空间复杂度相对比较高，但是时间复杂度低的算法或者数据结构（实际应用中，缓存就是利用空间换时间的思想）。相反，如果内存比较紧张，我们就可以用时间换空间的算法或数据结构。
- 循环链表
循环链表一种特殊的单链表，与单链表唯一的区别就是，循环链表的尾结点的指针指向头结点而不是指向空地址。如下示意图所示。
image.png
和单链表相比，循环列表的优点就是从链尾到链头比较方便。比如需要处理的数据具有环形结构特点时，用循环列表就非常合适。虽然单链表也可以实现，但是循环链表的代码要简洁的多。
链表的应用
我们已经学习了三种简单且最常见的链表，那么链表在实际的应用中是怎么用的呢？一个经典的链表使用场景就是LRU缓存淘汰法。
缓存的大小有限，但缓存的空间被用满的时候，我们该把哪些数据清除出去呢？LRU缓存淘汰法就是其中的一种策略，把最近最少用的数据清除出去。
那用链表怎么实现这个算法呢，下边我们来看一下基于单链表的Java实现。
package linked.singlelist;
import java.util.Scanner;
/**
* 基于单链表LRU算法（java）
*
*/
public class LRUBaseLinkedList<T> {
/**
* 头结点
*/
private SNode<T> headNode;
/**
* 链表长度
*/
private Integer length;
/**
* 链表容量
*/
private Integer capacity;
public LRUBaseLinkedList(Integer capacity) {
this.headNode = new SNode<>();
this.capacity = capacity;
this.length = 0;
}
public void add(T data) {
SNode preNode = findPreNode(data);
// 链表中存在，删除原数据，再插入到链表的头部
if (preNode != null) {
deleteElemOptim(preNode);
intsertElemAtBegin(data);
} else {
if (length >= this.capacity) {
//删除尾结点
deleteElemAtEnd();
}
intsertElemAtBegin(data);
}
}
/**
* 删除preNode结点下一个元素
*
* @param preNode
*/
private void deleteElemOptim(SNode preNode) {
SNode temp = preNode.getNext();
preNode.setNext(temp.getNext());
temp = null;
length--;
}
/**
* 链表头部插入结点
*
* @param data
*/
private void intsertElemAtBegin(T data) {
SNode next = headNode.getNext();
headNode.setNext(new SNode(data, next));
length++;
}
/**
* 获取查找到元素的前一个结点
*
* @param data
* @return
*/
private SNode findPreNode(T data) {
SNode node = headNode;
while (node.getNext() != null) {
if (data.equals(node.getNext().getElement())) {
return node;
}
node = node.getNext();
}
return null;
}
/**
* 删除尾结点
*/
private void deleteElemAtEnd() {
SNode ptr = headNode;
// 空链表直接返回
if (ptr.getNext() == null) {
return;
}
// 倒数第二个结点
while (ptr.getNext().getNext() != null) {
ptr = ptr.getNext();
}
SNode tmp = ptr.getNext();
ptr.setNext(null);
tmp = null;
length--;
}
private void printAll() {
SNode node = headNode.getNext();
while (node != null) {
System.out.print(node.getElement() + ",");
node = node.getNext();
}
System.out.println();
}
public class SNode<T> {
private T element;
private SNode next;
public SNode(T element) {
this.element = element;
}
public SNode(T element, SNode next) {
this.element = element;
this.next = next;
}
public SNode() {
this.next = null;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public SNode getNext() {
return next;
}
public void setNext(SNode next) {
this.next = next;
}
}
public static void main(String[] args) {
LRUBaseLinkedList list = new LRUBaseLinkedList();
Scanner sc = new Scanner(System.in);
while (true) {
list.add(sc.nextInt());
list.printAll();
}
}
}
欢迎关注公众号：「努力给自己看」
公众号200x200
网友评论