What are the different types of Linked Lists which are commonly used?
I know and have used the following:
- Singly Linked List
- Doubly Linked List
- Circular List
What are the other kinds of lists that have been used by you or known to you?
views:
990answers:
5
+4
A:
Skip lists! Not really a type of linked list, but related, and pretty neato.
okay, it is either a type of linked list or a group of linked lists, depending on how you classify things, but it features O(log N) insertion/selection, which is pretty sweet for a linked list.
Jimmy
2010-03-05 08:55:59
A skip list actually *is* a kind of linked list, or at least a hybrid and mashup of multiple linked lists, depending on how you look at it.
Quinn Taylor
2010-03-05 09:10:32
mmmmm, I always considered skip lists as some weird half-tree/half-list mutant structure. The ontology of data structures is not my forte.
Jimmy
2010-03-05 09:14:43
A:
I could probably think up scenarios where it would be useful to be able to link from any element in a list to the first and last elements. If no-one else corrects me, I assert that this is called a High-Performance-Mark-List.
High Performance Mark
2010-03-05 08:58:23
I would say that maintaining 1 or 2 extra links from each node is a really bad idea. Particularly because it's easy to store a pointer each to the first and last elements outside the list nodes, and only have to update them in one place. Even in straight C (as opposed to object-oriented languages) I would opt to store two additional variables rather than encumber the linked list nodes with redundant data.
Quinn Taylor
2010-03-05 09:09:20
You always have the ability to point to first node (head) by definition. And it's common programming practice also to keep pointer to the last node (tail). Such data structure is called "head-tail linked list". Double-ended queues can be implemented on the basis of such lists so sometimes this terms are referred as synonyms. http://en.wikipedia.org/wiki/Double-ended_queue
kemiisto
2010-03-05 09:14:34
Sadly, the High-Performance-Mark-List turns out not to be a high-performance list. Sigghhh.
High Performance Mark
2010-03-05 09:31:44
+2
A:
Both stacks and queues are often implemented using linked lists, and simply restrict the type of operations which are supported. An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.
Vijay Mathew
2010-03-05 09:03:13
+3
A:
There is also a multiply-linked list.
In a multiply-linked list, each node contains two or more link fields, each field being used to connect the same set of data records in a different order (e.g., by name, by department, by date of birth, etc.). (While doubly-linked lists can be seen as special cases of multiply-linked list, the fact that the two orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.)
codaddict
2010-03-05 09:04:52
+4
A:
In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is related to the B-tree. - Wikipedia
XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. - Wikipedia
TheMachineCharmer
2010-03-05 09:04:59