list - Erlang 中可以定义循环列表吗？

Question

是否可以在erlang中定义循环列表？ http://en.wikipedia.org/wiki/Linked_list

第一个问题是 erlang 中的循环列表究竟意味着什么？ 它是否有两个元素，一个元素是它自己，它旁边的地址指向下一个元素，存储在列表中？

如果是这样，我可以说有可能在 erlang 中定义循环列表。 但我需要澄清天气是我认为的 erlang 中的循环列表吗？

Answer 1

没有内置的列表机制可以做到这一点。但是，您可以使用包含您访问过或未访问过的元素的元组来构建一个元组。

基本结构是一个包含两个列表的元组:{Old, New}。当您第一次从空列表开始时，它看起来像 {[],[]}。当您填充列表时，您将其填充到New列表中:

new() -> {[], []}.

insert(X, {Old, New}) -> {Old, [X|New]}.

peek({_Old, [H|_]}) -> X.

要在列表中移动，您要做的就是首先在新列表中查找，并将值放入旧列表中:

next({Old, [H|New]}) -> {[H|Old], New}.

这很好，它的工作原理就好像我们只是丢弃旧元素一样。当我们到达列表末尾时会发生什么？我们需要修复这个函数(还有 peek 函数):

peek({Old, []}) -> hd(lists:reverse(Old));
peek({_Old, [H|_]}) -> X.

next({Old, []}) -> 
    {[], lists:reverse(Old)}}.
next({Old, [H|New]}) -> 
    {[H|Old], New}}.

如果列表中没有任何内容，则会崩溃。如果您愿意，也可以通过特殊大小写来返回“未定义”:

next({[], []}) ->
    undefined;
next({Old, []}) -> 
    {[], lists:reverse(Old)}.
next({Old, [H|New]}) -> 
    {[H|Old], New}.

然后，您可以使用“下一步”、“查看”功能以及可能的“删除”功能(见下文)来执行正常操作。我们还可以添加“上一页”功能以允许向后浏览:

prev({[], []}) ->
    undefined;
prev({[], New}) -> 
    {lists:reverse(New), Old}.
prev({[H|Old], New}) -> 
    {Old, [H|New]}.

delete({Old, []}) -> {[], tl(lists:reverse(Old))};
delete({Old,[H|New]}) -> {Old, New};

这应该涵盖了大部分内容。