为什么我们需要一个“循环链表"?(单个或双重)数据结构? [英] Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?

问题描述

为什么我们需要一个循环链表"(单向或双向)数据结构?

Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?

它解决了哪些简单链表(单链表或双链表)显而易见的问题?

What problem does it solve that is evident with simple Linked Lists (singly or doubly)?

推荐答案

使用它们的两个原因:

1) 一些问题域本质上是循环的.

1) Some problem domains are inherently circular.

例如，大富翁板上的方块可以用循环链表表示，以映射到它们的固有结构.

For example, the squares on a Monopoly board can be represented in a circularly linked list, to map to their inherent structure.

2) 一些解决方案可以映射到循环链表以提高效率.

2) Some solutions can be mapped to a circularly linked list for efficiency.

例如，抖动缓冲区是一种缓冲区，它从网络中获取编号的数据包并将它们按顺序放置，以便(例如)视频或音频播放器可以按顺序播放它们.太慢(滞后)的数据包将被丢弃.

For example, a jitter buffer is a type of buffer that takes numbered packets from a network and places them in order, so that (for example) a video or audio player can play them in order. Packets that are too slow (laggy) are discarded.

这可以用循环缓冲区表示，无需不断分配和释放内存，因为插槽可以在播放后重新使用.

This can be represented in a circular buffer, without needing to constantly allocate and deallocate memory, as slots can be re-used once they have been played.

它可以用一个链表来实现，但是会不断地增加和删除列表，而不是替换常量(更便宜).

It could be implemented with a linked-list, but there would be constant additions and deletions to the list, rather than replacement to the constants (which are cheaper).

这篇关于为什么我们需要一个“循环链表"?(单个或双重)数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！