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