circular-buffer - 环形缓冲区和循环链表有什么区别？

Question

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

Ring Buffer 的目的是什么，而循环链表不能，反之亦然？

Answer 1

环形缓冲区是一个连续的内存块，其中包含您的项目，当您到达终点时，您会循环回到起点:

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

=== increasing memory ===>

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

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

=== increasing memory ===>

与环形缓冲区相比，循环链表与固定数组相比具有相同的优势。它的大小可以不同，您可以插入和删除项目而无需随机播放。

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

当您知道其中允许的最大条目或不介意限制它时，往往会使用环形缓冲区。例如，如果您有一个通信协议(protocol)可以在缓冲区满时限制发送方，从而给接收方时间 catch 。

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