views:

388

answers:

4

I note that Scheme and Lisp (I guess) support circular lists, and I have used circular lists in C/C++ to 'simplify' the insertion and deletion of elements, but what are they good for?

Scheme ensures that they can be built and processed, but for what?

Is there a 'killer' data structure that needs to be circular or tail-circular?

+2  A: 

For example a double linked list data structure is "circular" in the Scheme/LISP point of view, i.e. if you try to print the cons-structure out you get backreferences, i.e. "cycles". So it's not really about having data structures that look like "rings", any data structure where you have some kind of backpointers is "circular" from the Scheme/LISP perspective.

A "normal" LISP list is single linked, which means that a destructive mutation to remove an item from inside the list is an O(n) operation; for double linked lists it is O(1). That's the "killer feature" of double linked lists, which are "circular" in the Scheme/LISP context.

antti.huima
You say that 'normal' LISP lists are single linked - I understand that. But are you also saying that circular-lists in LISP/Scheme are doubly-linked?
philcolbourn
I think what he was saying was "if you have a double-linked list, it is circular". In lisp/scheme parlance, a circular list only means that there is at least one reference further down the list to at least one cell closer to the beginning.
Vatine
Yeah, he's saying that doubly linked lists fulfill the requirements for being 'circular'.
Cam
In C, a doubly-linked-list need not be circular although that might be a convention. I also don't think that deletion is O(1) as you would need to step through the list to find the item to delete. This would be O(n) wouldn't it?
philcolbourn
Deleting "the current element" in a double-linked list is O(1), deleting another element is O(N). Deleting "the current element" in a single-linked list is O(N), but deleting "the lemenet after the current element" is O(1).
Vatine
@philcolburn: A double-linked list in C fulfills the minimum criterion for a double-linked list, there is a reference to a "previous" as well as a "next" element. If there's at least one element where you can follow a sequence of pointers and end up at the original element, the structure is circular.
Vatine
+5  A: 

Saying it supports 'circular lists' is a bit much. You can build all kinds of circular data structures in Lisp. Like in many programming languages. There is not much special about Lisp in this respect. Take your typical 'Algorithms and Datastructure' book and implement any circular data structure: graphs, rings, ... What some Lisps offer is that one can print and read circular data structures. The support for this is because in typical Lisp programming domains circular data structures are common: parsers, relational expressions, networks of words, plans, ...

It is quite common that data structures contain cycles. Real 'circular lists' are not that often used. For example think of a task scheduler which runs a task and after some time switches to the next. The list of tasks can be circular so that after the 'last' task the scheduler takes the 'first' task. In fact there is no 'last' and 'first' - it is just a circular list of tasks and the scheduler runs them without end. You could also have a list of windows in a window system and with some key command you would switch to the next window. The list of windows could be circular.

Lists are useful when you need a cheap next operation and the size of the data structure is unknown in advance. You can always add another node to the list or remove a node from a list. Usual implementations of lists make getting the next node and adding/removing an item cheap. Getting the next element from an array is also relatively simple (increase the index, at the last index go to the first index), but adding/removing elements usually needs more expensive shift operations.

Also since it is easy to build circular data structures, one just might do it during interactive programming. If you then print a circular data structure with the built-in routines it would be a good idea if the printer can handle it, since otherwise it may print a circular list forever...

Rainer Joswig
By 'support' I was referring to specific syntax to describe circular lists for reading and writing (as you say). eg. `(#0=(1 2) (x y . #0#))`; also scheme's `list?` predicate specifies that a circular list is not a list - or is this implementation specific?
philcolbourn
Ok, I can see that a task scheduler is a circular-list. A good example. In LISP or Scheme, how would you insert or remove a task?
philcolbourn
@philcolbourn The specific syntax you mention works in Lisp for all kinds of data structures with cycles. Not just circular lists. You can use destructive list operations to add an object to a circular list. That's a typical programming exercise in Lisp and/or programming courses...
Rainer Joswig
@Rainer Joswig OK, so circular lists make accessing the next item easy (no base-case) but require non-functional `set-car!` and `set-cdr!` operations to alter the list.
philcolbourn
A: 

Have you ever played Monopoly?

Without playing games with counters and modulo and such, how would you represent the Monopoly board in a computer implementation of the game? A circular list is a natural.

John R. Strohm
`how would you represent the Monopoly board in a computer implementation of the game?` ... As an array, so that I wouldn't have to iterate through each square on the board every move.
Cam
To be honest you would just keep a pointer to current square, so you would not have to that.
UK-AL
+2  A: 

Hello,

Adding and removing elements to the beginning of a list is cheap. To add or remove an element from the end of a list, you have to traverse the whole list.

With a circular list, you can have a sort of fixed-length queue.

Setup a circular list of length 5:

> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))

Let's add a number to the list:

 > (set-car! q 6)

Now, let's make that the last element of the list:

 > (set! q (cdr q))

Display the list:

 > (take q 5)
 (2 3 4 5 6)

So you can view this as a queue where elements enter at the end of the list and are removed from the head.

Let's add 7 to the list:

> (set-car! q 7)
> (set!     q (cdr q))
> (take q 5)
(3 4 5 6 7)

Etc...

Anyways, this is one way that I've used circular-lists.

I use this technique in an OpenGL demo which I ported from an example in the Processing book.

Ed

dharmatech
Wouldn't it be easier to use an array for this?
philcolbourn