程序猿修仙之路--数据结构之设计高性能访客记录系统

每个用户都有自己的个人空间，当有其他用户来访问的时候，需要添加访客记录，并且更新为最新的访客，这里设计到一个坑，如果存在这个用户的访问记录需要更新用户的最后访问时间。那这个需求在技术维度来说，有什么特点吗？ 先想10秒钟，在接着往下看！！！

有什么设计要点呢？

1. 用户的访客记录一定要缓存，要不然怎么抗住大并发呢?
2. 由于最新的访客记录变化非常快，要有一种能快速添加新数据，删除老数据的数据结构。

缓存的篇章今日暂且不说，说一下以上的第二点，也就引出了今日数据结构主角：链表

链表百科：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表属于线性结构。

链表分类

1. 单链表：链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。

   

public class Node<T>
    {
        //当前节点的数据元素
        public T Data { get; set; }
        //当前节点的下一个元素
        public Node<T> NextNode { get; set; }
    }
复制代码

2. 双向链表：每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。

   

public class Node<T>
    {
        //当前节点的前一个节点
        public Node<T> PreNode { get; set; }
        //当前节点的数据元素
        public T Data { get; set; }
        //当前节点的下一个元素
        public Node<T> NextNode { get; set; }
    }
复制代码

3. 循环链表：指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。