单链表实现规范探讨：存储头节点+长度，还是头、尾节点+长度？

单链表的这两种实现方式都属于规范实现，具体选哪种完全看你的业务场景对操作效率的需求：

• 仅存储head（头节点）与size（长度）的实现

  • 特点：结构简单，占用内存少，不用额外维护尾节点的引用，能避免尾节点引用失效的问题（比如删除最后一个节点时，不用遍历更新尾节点）。
  • 短板：做尾部插入、尾部删除操作时，必须从头节点开始遍历到链表末尾，时间复杂度是O(n)，效率偏低。
  • 适用场景：如果你的链表操作以头部增删、遍历为主，不需要频繁操作尾部，这种实现足够用。

• 同时存储head、tail（尾节点）与size的实现

  • 特点：尾部插入操作可以直接通过尾节点完成，时间复杂度降到O(1)，在频繁插尾部的场景下性能提升明显。
  • 短板：需要额外维护尾节点的引用，做删除最后一个节点、删除中间节点导致尾节点变动这类操作时，必须同步更新尾节点，代码复杂度更高，容易出现尾节点引用错误的bug。
  • 适用场景：如果需要频繁执行尾部插入操作（比如用单链表实现队列），这种实现更合适。

没有绝对的“最优规范”，不管是教材还是工业界的实现，两种方式都有广泛应用——比如不少轻量单链表会选前者，而需要高效尾部操作的场景会选后者。

内容的提问来源于stack exchange，提问作者Vivyen