为什么链接列表是反向的？

Question

为什么链表是反转的？

我一直在听很多软件工程师谈论反转链表。反转链表有什么用？这样做而不是向后遍历有什么好处？

为什么在技术面试中使用它们？
除了技术面试还有什么用？

Answer 1

据我所知，有链表和双链表。当你使用双向链表时，每个节点都有一个指向下一个和前一个节点的指针，这样很容易向后遍历。当列表“仅链接”时，节点只有“next-reference”，因此您将无法向后遍历。我希望正确回答问题

Answer 2

反转递归函数结果的列表是很常见的。考虑一个 map 函数

   fn map (fun, lst) =
        local fn mp (in, out) = 
             if null(in)
             then out
             else mp(tail(in), fun(head(in)) :: out)
        return reverse(mp(lst, nil))

反转内部函数的结果，将结果顺序恢复为输入列表的顺序

如果您的语言支持变异，则有更有效的方法来执行此操作，即通过保留指向列表中最后一对的指针并在每次调用内部函数时附加一对。

Answer 3

反转链表在现实生活中时有出现。

最近我在实现 lock-free multi-producer single-consumer 工作队列时这样做了。堆栈是最简单的 lock-free 数据结构来实现，实现是一个 singly-linked 列表，因此我的多个生产者会将新工作推送到无锁堆栈上。

单个消费者可以立即获得整个堆栈，但随后必须反转它以按照正确的顺序创建任务队列。

就是说...您可能问错了问题。反转链表的任务是您可以执行的最简单的数据结构操作之一。如果你被教导这样做，那么它只是真正理解编程的漫长道路上的早期课程。如果你在面试中被问到这个问题，那么面试官想知道你是否是可以设计、实现和维护数据结构的程序员，或者你是否可以从 Whosebug 复制和修改答案，然后将东西粘合在一起你不懂。

为什么链接列表是反向的？

Why are Linked Lists Reversed?

algorithm

sorting

data-structures

linked-list

traversal