SarahKate31
Programmer
Can you give me any information or links to understand multilists composed of singly circular linked lists?
Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations derfloh on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Singly circular linked list & Multilists
- Thread starter SarahKate31
- Start date
- Status
Well, I haven't seen many resources on the subject. Multi-lists are rather uncommon, as the iterations would suck Time Complexity and be a breeding ground for errors. Are you looking for information on writting a multilist using circular list(s) or are you looking for documentation on a standard implementation?
I realize that I am not being much help, but it is a topic that I am intrested in. More over I am curious as to why a multi-list would be a container of choice (perhaps for a multi-queue of sorts)?
I realize that I am not being much help, but it is a topic that I am intrested in. More over I am curious as to why a multi-list would be a container of choice (perhaps for a multi-queue of sorts)?
I'm not sure what you mean by multi-lists. Do you mean a list that contains items that have more than one occurrence? If that is the case, you can use an ordinary STL list for that.
As for circular lists, it is basically a case of roll your own. It is just a normal list where the tail points to the head. Using STL to do this is just too difficult.
As for circular lists, it is basically a case of roll your own. It is just a normal list where the tail points to the head. Using STL to do this is just too difficult.
chipperMDW
Programmer
Actually, using the STL to implement a circular list would be pretty easy. You'd just create an iterator adaptor for a regular list::iterator. It would probably be easiest to have it tied to a specific list (theList), and change the increment operator so that, when the iterator equals theList.end(), it becomes equal to theList.begin() instead. The decrement operator would be similar. (Of course, I'm probably missing some basic reason why this wouldn't work, so correct me if you see I'm wrong).
As for a multi-list, do you mean a list where each element has several fields, and you can iterate through the list different ways based on which field you're looking at? e.g. to keep a group of people simultaneously sorted by age, weight, and height in the same "multi-list"?
As for a multi-list, do you mean a list where each element has several fields, and you can iterate through the list different ways based on which field you're looking at? e.g. to keep a group of people simultaneously sorted by age, weight, and height in the same "multi-list"?
multi-list would be a true multi dimentional list... A list of nodes that point forward, back, up and down... A cirular linked list in and of it'sself is fairly easy, but a multi-dimentional cirular list is a lot more difficult. Frankly I can't think of a real world application that you wouldn't just use a list of lists for, but it is at least a neat idea to play with (perhaps I write one... hmm...).
- Status