单向链表也称为单向链表，是链表中最简单的形式，每个节点包含两个域、一个信息域(元素域)和一个链接域。 此链接指向链表中的下一个节点，最后一个节点的链接字段指向空值。
表元素域elem用于存储特定的数据。 链接域next用于存储下一个节点的位置(python中的标识符)；变量p指向链表的首个节点)的位置，一旦从p出发，就能够找到表中的任意节点。 节点实现classsinglenode(object ) :“”单链接列表的节点“”“def _ _ init _”self，item ) : # _item存储数据元素self 识别下一个节点self.next=None链表的操作is_empty (链表长度travel为空) )的链表末尾添加元素add(item )链表的开头item )在定位元素search(item )查找节点中实现remove (item )删除节点的单链表classsinglelinklist(object ) : ' '单链表' ' lf._head=nodedefis_empty ) self ) : ' '确定链表是否为空的' ' returnself.__head==nonedef cur是起始节点cur==none : count=1#将cur向后移动一个位置cur=cur.nextreturncountdeftravel (self ) : ' ' '链表' ' cur=self._ _ '。
defadd(self，item ) : " "头部添加元素“”#首先，创建包含item值的节点node=singlenode(item )。 新节点的链接域next指向第一个节点，即_head指向的位置node.next
defappend(self， item )在：“”末尾添加元素“”“节点=单节点”item ) #时，首先确定链表是否为空，如果为空链表，则_head为新节点if self=none : cur=cur.next cur.next=node在指定位置添加元素
definsert(self，pos， item ) : " "指定位置追加要素" " #如果指定位置pos在第一个要素之前，则只要执行头部插入的ifpos=03360self.add )指定位置超过了链表的末尾， 运行末尾插入elifpos(self.length(-1 ) :self.append ) item )，指定位置else:node=singlenode(item ) count=0 # 找到pre并从指向指定位置的第一个节点移动到指定位置pre=self._headwhilecount(pos-1 ) : count =1 pre=pre.next #将新节点的next移动到插入位置的节点
defremove(self，item ) :“”删除节点“”“cur=self._head pre=None while cur！=None: #
找到了指定元素 if cur.item == item: # 如果第一个就是删除的节点 if not pre: # 将头指针指向头节点的后一个节点 self._head = cur.next else: # 将删除位置前一个节点的next指向删除位置的后一个节点 pre.next = cur.next break else: # 继续按链表后移节点 pre = cur cur = cur.next 查找节点是否存在 def search(self,item): """链表查找节点是否存在，并返回True或者False""" cur = self.__head while cur != None: if cur.item == item: return True cur = cur.next return False 链表与顺序表的对比链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。
操作链表顺序表访问元素O(n)O(1)在头部插入/删除O(1)O(n)在尾部插入/删除O(n)O(1)在中间插入/删除O(n)O(n)注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。
写链表代码建议 理解指针或引用的含义警惕指针丢失重点留意边界条件处理举例画图，辅助思考 如何实现LRU缓存淘汰算法缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。
这些策略你不用死记，我打个比方你很容易就明白了。假如说，你买了很多本技术书，但有一天你发现，这些书太多了，太占书房空间了，你要做个大扫除，扔掉一些书籍。那这个时候，你会选择扔掉哪些书呢？对应一下，你的选择标准是不是和上面的三种策略神似呢？
我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。如果此数据没有在缓存链表中，又可以分为两种情况： 如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。