在做缓存设计的时候,可以用到链表的数据结构来做缓存设计。主体结构采用map,而存储的节点、数据采用双向链表。这里介绍单向链表,因为如果搞懂了单向链表,其实双向链表更好理解。
数据结构中的链表分为单向链表、双向链表、循环链表。单向链表的数据结构中通常会存在数据域和节点域:
如图1:单向链表的数据结构
public class LinkNode{
int value; // 数据域
LinkNode next; // 节点域,相当于c和c++中的指针
}
图1 链表的数据和节点
如图2:单向链表中有头节点和尾节点,同时可以看到节点中都是只有一个next的指针指向下一个节点。同时可以看到tail节点指向null。
双向链表:存在前驱节点和后继节点,基于前驱和后继节点可以很方便的表示节点元素间的关系。可以看到与单向链表不同的是存在的节点有前驱节点,同时是双向的。
LeetCode206题:单向链表的反转(如:(1->2->3->4)反转成(4->3->2->1)
在遍历链表时,首先将当前节点的下一个节点指向前驱节点,此时需要将当前节点的前节点变成当前节点,然后将当前节点变成下一个节点即可实现替换的关系,也即是一个从后往前的过程
实现过程:
public static LinkNode reverse(LinkNode head){
while(head != null){
LinkNode curr = head;
LinkNode prev = null;
// 如果当前节点不为空,则首先设置空节点,将当前节点的下一个节点指向前节点,同时前节点指向当前节点,当前节点指向next节点
while(curr!=null){
LinkedNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
单向链表去重(如:1->2->2->3->3->4)->去重后的效果:(1->4)
考虑单向链表中
一种情况:当前节点只有一个节点或者当前的节点与下一个节点不同时,此时进行节点指向。
一种情况:当前的节点的下一个节点域当前节点相同,此时需要进行去重处理,去重的过程就是一个节点指向修改的过程。
实现过程:
public static LinkNode dumpRemoveLinkList(LinkNode head){
while(head != null){
LinkNode dummy = new LinkNode();
LinkNode tail = dummy;
// 考虑单个元素和不相等情况
if(head.next == null || head.value!=head.next.value){
tail.next = head;
tail = head;
}
// 考虑相同情况,进行去重
if(head.next != null && head.value == head.next.value){
head = head.next;
}
// 拿到不同的数据的下一个数据的首个元素的节点
head = head.next;
}
tail.next = null;
return dummy.next;
}
了解了它的数据结构,前面我说到可以用在缓存上,下一篇我们来看它的使用场景。