在我的教科书,Java中的数据结构和算法中,作者说,在使用链接列表实施队列时,您选择了队列的前部,而排队的后部则是排队的后部。名单。这样,您可以从头部上移开并插入尾巴。

作者随后隐性地问:“为什么插入头部并在尾巴上移开是不好的?”没有提供答案。

我看不到真正的区别。实际上,“头”和“尾巴”只是我们定义的任意名称。如果我们添加头并创建对旧头的引用,然后从尾巴上移动并将尾巴移到尾巴上,那会是什么糟糕的?

作者问题的答案是什么?

有帮助吗?

解决方案

在单个链接列表中,每个元素都有指向下一个元素的指针。如果您有其他指向尾部元素的指针,则需要恒定的数字OG操作到 添加 在尾部的列表中:获取尾指针,在尾巴之后添加一个元素,将此新元素作为新尾部放置。从头部卸下也需要持续数量的操作:使您的新物品新事物,头,指向旧的头部。

然而, 去除 从尾巴开始,需要指针到前任到当前的尾巴。这将带您与有元素一样多的操作,即线性许多。

另一个解决方案是使用双重链接列表,然后您可以选择自己的内容,但是它使用了两倍的内存。

其他提示

从头部上移开并插入尾部都是持续的时间操作,并具有单一链接的列表,假设头和尾指针。在尾部插入也是恒定的时间。但是从尾巴上卸下意味着将尾指针移向头部,并且由于您没有后背指针,因此在不穿越整个列表的情况下无法在尾部找到元素。这使得插入是线性的,而不是恒定的时间操作,这就是为什么更糟的原因。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top