使用数组实现链表的一个问题
来源：11-1 结语
慕运维2948618
2022-06-19
老师，您好。我想使用数组实现链表，我想问一个问题。
假设现在数组链表是这样的：[Node(“A”, 3), Node(“B”, 2), Node(“C”, -1), Node(“D”, 1)]。
假设head指向0，那么此时链表就是 A -> D -> B -> C。
现在我想把节点B删除。那么删除后的数组为[Node(“A”, 3), null, Node(“C”, -1), Node(“D”, 2)]。
问题是这样的，在添加新的节点时，如何在这个被删除的空余的地方插入，是不是只能遍历一遍数组，找到空缺的位置？感觉这样很低效，老师有什么巧妙的设计吗？
写回答
1回答
-
使用一个队列 q，记录空闲索引，删除的时候，把删除位置的索引入队。
每次插入新元素的时候，先看队列 q 是否为空，如果不为空，取出队首的索引，在这个索引位置添加新元素。否则说明数组中没有“残缺”的位置，在整个数组的最后添加新元素。
继续加油！：）
122022-06-19
相似问题