链表（上）

链表结构

存储结构

内存分布

单链表

1. 单链表结构

2. 插入和删除

循环链表

双向链表

双向循环链表

链表 VS 数组性能大比拼

解答开篇

思路： 维护一张有序单链表，越靠近链表尾部的节点越早访问

1. 如果已经在链表中的数据
   1. 将其从原来位置删除，并插入到头部
2. 如果不在链表中
   1. 空间已满，则删除尾部节点，在头部节点插入
   2. 空间未满，直接插入头部

扩展

问题： 如果字符串用单链表来存储的，如何判断是否是回文

1. 用快慢指针确定中点指针
2. 慢指针移动时，将节点倒置
3. 在中间指针分别向前后向后移动进行比较