algorithm - 单向链表尾部

Question

如果你想像这样创建一个单向链表:

struct Node { 
    int data;
    Node *next;
};

struct List{ 
    Node *head;
    // Node *tail; --> necessary?
    Node *last;
};

并且这个列表有方法“append”、“remove”、“printList”和“findElement”。有必要有尾部吗？因为使用“last”您可以解决最后一个节点。

那么什么时候需要所有三个节点“head”、“tail”和“last”呢？例如，当你想将排序后的节点插入到列表中时？

Answer 1

不，没有必要。 tail 等于 head->next，因此它是多余的，并且会增加簿记开销以保持此字段更新。

另请注意，字段 last 有点不寻常。在大多数用例中，您将元素添加到单向链表的头部，并在真正需要添加到末尾时使用不同的数据结构。