循环链表和跳跃列表的示例
我想询问您关于什么类型的程序甚至技术的想法，我可以更好地向我的朋友解释循环链表和跳过列表理论的用处。同行。
我的编程信念是，如果你给他们提供例子和隐喻，人们可以更好地理解一个概念。
只是您对要创建的示例程序或解决方案（编程技术或算法）的想法。
干杯!
I would like to ask for your ideas on what type of programs or even techniques in which I can better explain the usefulness of the theory of Circular Linked Lists and Skip Lists to my peers.
My programming belief is that one can grasp a concept better if you give them examples and metaphors.
Just your idea of sample programs to create or solutions (programming technique or algorithm).
Cheers!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
循环链表的一个很好的用途是作业调度系统，其中每个作业使用给定的资源（例如简单操作系统中的进程）获得一定的时间。
在这种情况下，拥有特定的
head没有什么意义，因为您总是在列表中循环，您需要的只是current指针。您可以在当前职位之后添加新职位，并使用current找到要删除的职位。进入下一个工作很简单：可能的跳过列表是列表形式的字典。您维护一个指向第一个单词
a的指针，它包含一个指向aardvark的普通指针和一个指向baa*a< /sup>。*a：实际上我不知道它们是否是正确的词，但它们应该很接近，希望你能明白这个想法。
A good use for circular linked lists is a job scheduling system where each job gets a certain amount of time with a given resource (such as processes in a simple operating system).
In that case, it makes little sense to have a specific
headsince you're always cycling around the list, all you need is thecurrentpointer. You can add new jobs after the current one and usecurrentto locate one for deletion. Advancing to the next job is a simple:A possible skip list is a dictionary in list form. You maintain a pointer to the first word
aand it contains a normal pointer toaardvarkand a skip pointer tobaa*a.*a: I actually don't know if they're the correct words but they should be close, and you'll hopefully get the idea.
跳跃列表基本上是放置在常规排序链接列表顶部的一组附加列表（或真正的链接），以帮助搜索列表。
跳跃列表在常规链表之上创建一种二叉搜索树，因此搜索操作需要 O(log N) 时间而不是 O(N)，从而使搜索速度更快。您可以在任何想要使用常规链接列表但需要更快访问的地方使用它们。
下面的页面有一个关于跳过列表的非常好的、易于理解的讨论：
http://igoro.com/archive/skip-lists-are-fascinating/
Skip lists are basically an additional set of lists (or really links) placed on top of a regular sorted linked list to assist in searching through the list.
Skip lists create a kind-of binary search tree on top of the regular linked list, so that search operations take O(log N) time instead of O(N), making them faster. You would use them anywhere you would want to use a regular linked list, but need faster access.
The following page has a really nice, easy-to-follow discussion on skip lists:
http://igoro.com/archive/skip-lists-are-fascinating/
来自维基百科：
循环列表如何工作的一个简单的可视化示例可能是想象一群人站成一个圆圈，每个人只知道他左边的人的名字。因此，要搜索组中的一个人，您可以从第一个人（在本例中为任意人）开始，然后移动到他知道名字的人（即他的左边），直到找到您要找的人或来再次回到第一个人。在该组中添加或删除一个人只需将一个人从圈子中放置/删除，然后更改他右边的人所知道的名字（如果是添加，则告诉他左边的人的名字） 。我希望这个例子有意义，这基本上就是我在学习链表时用来可视化它的方式。
跳跃列表支持快速 (O(log(n))) 操作，并且可以用作排序数据结构 - 非常类似于平衡二叉搜索树。这使得它们在我们需要快速数据插入/删除时间（类似于链表但不同于数组）并且还具有快速访问时间（类似于数组但不同于链表）时非常有用。它们也适合进行快速范围查询（例如，查找结构的索引 [i,j] 中所有元素的总和（或最大值、最小值、乘积等））。
我无法想出一个足够简单的现实世界隐喻来表示跳跃列表，数据结构看起来比我在日常生活中看到的对象要复杂得多。但是 wikipedia 的解释非常清楚，通过证明和算法来构建它应该是一个很好的选择起点。这是原始论文的链接，在我看来，该论文也非常可读。
From Wikipedia:
An easy to visualize example of how a circular list works might be to imagine a group of people standing in a circle where each person only knows the name of the person to his left. Thus to search for a person in the group, you start with the first person (an arbitrary person in this case) and move to the person he know the name of (i.e. to his left) until you find who you are looking for or come back to the first person again. Adding or removing a person to this group is simply done by placing/taking away a person from the circle and changing the name known by the person to his right (and telling him the name of the person to his left if it is an add). I hope this example makes sense, it is basically the way I used to visualize it when I was learning about linked lists.
Skip Lists support fast (O(log(n))) operations and can be used as a sorted data structure - much like balanced binary search tree. This makes them useful wherever we need fast data insert/remove times (like a linked list but unlike array) and also have fast access times (like an array but unlike in a linked list). They are also good for making fast range queries (e.g. find the sum (or max, min, product, etc.) of all elements in indices [i,j] of the structure).
I cannot think of a sufficiently simple real world metaphor for a skip list, the data structure looks quite more intricate than anything I can expect to see with objects in everyday life. But the wikipedia explanation is quite clear and working through the proof and algorithm for building it should be a good starting point. Here's a link to the original paper which is also quite readable IMO.