环形缓冲区和循环链接列表有什么区别？

Question

环形缓冲区和循环链接列表有什么区别？

环形缓冲区服务于循环链接列表的目的是什么,反之亦然？

Answer 1

环形缓冲区是一个连续的内存块,其中包含您的项目,当您到达最后时,您将循环回到开始:

+----------------------+
|                      |
+-->| a | b | c | d |--+

=== increasing memory ===>

由于链表性质,循环链表根本不必是连续的,因此所有元素都可以分散在内存中.它只是遵循循环元素的属性:

+---------| d |<-----------------+
|                                |
+-->| a |------------->| b |--+  |
                              |  |
            +-----------------+  |
            |                    |
            +-->| c |------------+

=== increasing memory ===>

圆形链表与链表相对于固定数组的环形缓冲区具有相同的优点.它的大小可以不同,您可以插入和删除项目而不需要随机播放.

缺点也是类似的,如果您正在扩展或收缩列表,则没有O(1)数组访问和增加的工作.

当您知道其中允许的最大条目,或者不介意限制它时,将倾向于使用环形缓冲区.例如,如果你有一个通信协议,当缓冲区变满时可以限制发送端,给接收方时间赶上.

循环链接列表示例将是操作系统中的进程列表,您需要能够添加或删除进程,但不关心列表的头部,只关注当前项目.