data-structures - 如何在数组中实现链表？

Question

This question提到可以在数组中实现链表。

虽然我可以想象如何用多个数组来做到这一点，但如何用一个数组来完成？

编辑:考虑到需要从列表中删除和插入项目，这是否可以有效地完成 - 大概需要识别数组中的空闲元素？

Answer 1

如果它是一个对象数组，那么每个对象都会存储一个值和一个指向下一个对象的指针。

[0] -> {"a",1}
[1] -> {"b",2}
[2] -> {"c",4}
[3] -> {"1",5}
[4] -> {"d",7}
[5] -> {"2",6}
[6] -> {"3",8}
[7] -> {"e",-1}
[8] -> {"4",-1}

所以这里我有 2 个链表，第一个:

"a"-> "b"-> "c"-> "d"-> "e"

第二个:

“1”->“2”->“3”->“4”

两者都使用 -1 的索引作为列表的结尾。

然后您将需要多个指针(每个列表一个)来确定您在列表中的位置。

老实说，我什至不确定我是否理解这个问题，但无论如何都想抛出想法。