头插法建立单链表

尾插法建立单链表

头插法建立的链表输入顺序与结点次序相反，尾插法可以使二者顺序相同

R做索引，S做中介节点
代码链接
重点r=p;将尾节点更新为r

整表删除

参照删除单链表制定位置结点代码代码链接

快慢指针—>标尺思想

单链表与顺序存储结构优缺点

1.存储分配方式：
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;
单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
2.时间性能：
—查找
顺序存储结构O(1);
单链表O(n)
—插入和删除
顺序存储结构需要平均移动表长一半的元素，时间为O(n);
单链表在计算出某位置的指针后，插入和删除时间仅为O(1)
3.空间性能
顺序存储结构需要预分配存储空间，分大了容易造成空间浪费，分小了容易发生溢出
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

小结

1.频繁查找，较少插入删除操作，宜用顺序存储结构，如，游戏开发时用户注册的个人信息的存储
2.频繁插入删除操作，较少查找，宜用单链表结构，如游戏中的玩家的装备列表
3.当线性表大致长度已知，宜用顺序存储结构，反之，长度变化大或未知，则用单链表