Circular Linked Lists – Attributes, Implementation and Uses

http://onebyezero.blogspot.com/2014/06/circular-linked-lists-attributes.html

by pagejim • 12 years ago

41 7 12 years ago

onebyezero.blogspot.com

vijayaggarwal• 12 years ago

In a circular linked lists you can have easy access to end of the list.

This is not true for circular linked lists in general. A few special cases where this is true:

1. If the list is doubly linked.

2. If the list maintains pointers to both head and tail nodes (trivial).

3. If the list maintains a single pointer but uses it to refer to the tail node instead of the head node. Head node can then be easily reached as tail->next.

Of course, data structures can be tweaked in innumerable ways to add special properties. So one cannot possibly list all ways of adding easy tail-node-access to circular linked lists.

S4M• 12 years ago

Is this a response to the blog post "The Worst Programming Interview Question" that went last time on HN?

https://news.ycombinator.com/item?id=7953725

hga• 12 years ago

Jiri Soukup (http://www.amazon.com/Taming-Pattern-Classes-Persistence-Pro... I've sworn off using C++ in the future, but keep this one book using it handy, it's got a lot of generally useful advice, much from hard lessons learned in VLSI CAD and other early industrial uses of C++) is fond of these, and I've found them very useful in times past. Particularly elegant in that they eliminate special case code for the beginning and ending of the list.

robmccoll• 12 years ago

Performance tip (for circular linked lists and linked lists in general): store your list nodes in a dynamically allocated array. Keep freed nodes in an in-place freed list inside the array and in a stack-like structure in-place beyond the part of the array that is currently in use. This cuts down on fragmentation in the memory allocator since you are allocating one larger contiguous chunk of memory instead of many smaller pieces, keeps your data closer together in the memory space to help with cache performance and prefetching, and allows you to switch to array indices instead of pointers. Why array indices? If the data uses indices for its references rather than pointers, sharing it across process memory spaces at different addresses is trivial. It also allows you to serialize the data to disk or the wire without having to perform any changes to the representation.

CocaKoala• 12 years ago

Oh geeze, list_heads. I remember wrangling with these when I was taking an OS class. In particular, my partner and I lost points on a project because we (and basically everybody else in the class) failed to recognize a subtle bug in how we were traversing lists.

Say you have a task_struct, and you want to iterate through the list of that task's children. You look through the code and you see

struct list_head children; /* list of my children * /
struct list_head sibling; /* linkage in my parent's children * /

And because it's late and you've been working for hours, you say "Ah ha! We'll just iterate through the children list_head, which is the list of the task's children, and that will give us what we want!"

But it turns out that's not how it works, because list_heads aren't linked lists like how you're used to thinking of them from your class on Data Structures! Here's what happens when you run your naive code iterating through children!

You start at task_struct foo, and you follow the pointer to a child of foo. Now, you follow children again, because you're still thinking that children is the list_head of foo's children. But you're wrong, because now you're in task_struct bar, and list_head children is now a list of bar's children; what you should be doing is iterating through list_head siblings!

We were pretty salty about losing the points, as I recall. On the other hand, after that experience we were very careful about keeping track of which struct we were in during any particular operation on a list_head, and I can remember how how they work (and how angry they made me) long after the class is over.

dpark• 12 years ago

This sounds like an issue of poor naming. The confusion goes away if "children" is renamed as"first_child". Perhaps not a likely option if that naming convention is spread through the Linux kernel, though.

a1369209993• 12 years ago

Actually, the problem is that you're iterating through task_structs when you should be iterating through struct list_heads:

  struct list_head* head = &this->children;
  struct list_head* i = head->next;
  for(; i!=head ;i=i->next)
      {
      task_struct* child = container_of(i,task_struct,sibling);
      /* do stuff */
      }

Circular Linked Lists – Attributes, Implementation and Uses

Related Stories