In what situations should I use each kind of list? What are the advantages of each one?
A:
With singly linked lists you can only traverse forwards. With doubly linked lists you can traverse backwards as well as forwards through the list. In general if you are going to use a linked list, there is really no good reason not to use a doubly linked list. I have only used single linked in school.
Corey Sunwold
2009-04-03 03:18:02
Kudos on rejecting SLLs, they're only good for limited memory situations or as an intro to DLLs.
paxdiablo
2009-04-03 03:29:43
Or for queues :-) I stand corrected.
paxdiablo
2009-04-03 03:43:40
Or for immutability and sharing structure.
Brian
2009-04-03 05:29:39
why is he voted own?
FL4SOF
2009-04-03 06:19:02
I didn't vote him down (but I did remove my upvote, sorry @csunwold). Reason being: "...no good reason not to use a doubly linked list". Queues (not double ended) can be done efficiently with SLLs with less storage and CPU time than DLLs - that's at least one good reason to use SLLs.
paxdiablo
2009-04-03 07:14:20
+5
A:
Plain list:
Linked List:
Double Linked List:
Answer from comments section:
Plain list:
Stores each item sequentially, so random lookup is extremely fast (i.e. I can instantly say "I want the 657415671567th element, and go straight to it, because we know its memory address will be exactly 657415671567 bigger than the first item). This has little or no memory overhead in storage. However, it has no way of automatically resizing - you have to create a new array, copy across all the values, and then delete the old one. Plain lists are useful when you need to lookup data from anywhere in the list, and you know that your list will not be longer than a certain size.
Linked List:
Each item has a reference to the next item. This means that there is some overhead (to store the reference to the next item). Also, because they're not stored sequentially, you can't immediately go to the 657415671567th element - you have to start at the head (1st element), and then get its reference to go to the 2nd, and then get its reference, to get to the third, ... and then get its reference to get to the 657415671566th, and then get its reference to get to the 657415671567th. In this way, it is very inefficient for random lookup. However, it allows you to modify the length of the list. If your task is to go through each item sequentially, then it's about the same value as a plain list. If you need to change the length of the list, it could be better than a plain list. If you know the 566th element, and you're looking for the 567th, then all you need to do is follow the reference to the next one. However, if you know the 567th and you're looking for the 566th, the only way to find it is to start searching from the 1st element again. This is where Double Linked Lists come in handy...
Double Linked List:
Double linked lists store a reference to the previous element. This means you can traverse the list backwards as well as forwards. This could be very useful in some situations (such as the example given in the Linked List section). Other than that, they have most of the same advantages and disadvantages as a Linked List.
Answer from comments section:
For use as a queue:
You'd have to take all of those advantages and disadvantages into account: Can you say with confidence that your queue will have a maximum size? If your queue could be anywhere from 1 to 10000000000 elements long, then a plain list will just waste memory (and then may not even be big enough). In that case, I'd go with a Linked List. However, rather than storing the index of the front and rear, you should actually store the node.
Recap: A linked list is made up of "nodes", and each node stores the item as well as the reference to the next node
So you should store a reference to the first node, and the last node. Thus, when you enqueue, you stick a new node onto the rear (by linking the old rear one to the new rear one), and remember this new rear node. And, when you dequeue, you remove the front node, and remember the second one as the new "front node". That way, you don't have to worry about any of the middle elements. You can thus ignore the length of the queue (although you can store that too if you really want)
Smashery
2009-04-03 03:23:30
you can make a queue with a single-linked list, but with one pointer to the head, and one to the tail.
Mark
2009-04-03 03:30:49
I've added extra information relating to your queue question, in my answer, above.
Smashery
2009-04-03 03:36:35
Removed my comments saying DLL is better than SLL for queue since I didn't take into account which end was put and which was get. @Smashery's update makes it clear - you don't need DLL for a queue.
paxdiablo
2009-04-03 03:42:16
For a stack, you'd have exactly the same considerations - do we know how big the stack will get? If we have no idea, then a single-linked list is fine, except now we can forget about the rear element, and just add and remove items to and from the front of the Single Linked List.
Smashery
2009-04-03 03:47:06
ty, I was implementing them with plain lists, but I guess I will change to a sll.
brsunli
2009-04-03 03:49:22
plus it sounds easy, the modular arithmetic in c++ to deal with plain lists was giving me headache
brsunli
2009-04-03 03:51:05
If this is homework, I'd think twice about implementing a stack as a list. I suspect your educator wants to see you choose a suitable datatype for queue and stack. Stacks would almost *always* be done as fixed size arrays - just my $0.02.
paxdiablo
2009-04-03 03:57:39
Pax has a point - at my uni, we were first taught stacks and queues using arrays. If this is an education situation, it's highly likely they'll expect you to use fixed size arrays and just throw an error if you run out of room in the list.
Smashery
2009-04-03 04:14:07
Ummm, arrays aren't fixed-size. You can usually reallocate them larger. e.g., C's realloc or C++'s vector. But this is an expensive operation, usually requiring copying the entire array. So when you resize, you often double the size to reduce the expense. Stacks/queues are normally arrays.
derobert
2009-04-03 05:12:23
The major advantage of linked lists is that insert in the middle is very cheap — O(1). In an array, its O(n).
derobert
2009-04-03 05:14:22
Yes, arrays are fixed size; although you're right: vectors are not. If you have an array at memory location 0x123ABC, you cannot increase the size of it. As you've rightly said, you *can* reallocate... but this is not increasing the size of the array - this is creating an entirely new array.
Smashery
2009-04-03 05:25:56
@derobert, it's only O(1) if you already know the position you want to insert at. The operation of inserting a node into a sorted list in O(n) time complexity since you have to find where it goes. What you're saying is equivalent to "inserting into an array is O(1) if a hole already exists" :-)
paxdiablo
2009-04-03 07:10:58
+1
A:
Nobody mentioned my favorite linked list: circularly linked list with a pointer to the last element. You get constant-time insertion and deletion at either end, plus constant-time destructive append. The only cost is that empty lists are a bit tricky. It's a sweet data structure: list, queue, and stack all in one.
Norman Ramsey
2009-04-03 05:31:32
Empty lists aren't tricky, you just have to waste an element in the circular list. That way you can always distinguish between an empty and full one. They are nice, I'll grant you that.
paxdiablo
2009-04-03 07:17:11
A:
One advantage of a doubly-linked list is that removal of a node whose pointer is specified is O(1).
sigjuice
2009-04-03 06:04:31