Plain, linked and double linked lists: When and Why?

Question

In what situations should I use each kind of list? What are the advantages of each one?

Scalable

Answer 1

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)

Humblebee

What list do you recommend to implement a queue? – Scalable

you can make a queue with a single-linked list, but with one pointer to the head, and one to the tail. – Impeditive

Thank you, this is really clarifying. – Scalable

I've added extra information relating to your queue question, in my answer, above. – Humblebee

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. – Mouthful

and it sounds really easy to implement – Scalable

what about a stack, which is the better one to implement? – Scalable

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. – Humblebee

ty, I was implementing them with plain lists, but I guess I will change to a sll. – Scalable

plus it sounds easy, the modular arithmetic in c++ to deal with plain lists was giving me headache – Scalable

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. – Mouthful

but plain list are implemented with fixed size arrays isn't? – Scalable

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. – Humblebee

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. – Milligram

The major advantage of linked lists is that insert in the middle is very cheap — O(1). In an array, its O(n). – Milligram

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. – Humblebee

@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" :-) – Mouthful

Answer 2

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.

Honour

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. – Mouthful

Answer 3

One advantage of a doubly-linked list is that removal of a node whose pointer is specified is O(1).

Ohm

Answer 4

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.

Asuncionasunder

Kudos on rejecting SLLs, they're only good for limited memory situations or as an intro to DLLs. – Mouthful

Or for immutability and sharing structure. – Repudiation

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. – Mouthful

Answer 5

Doubly-linked list provides several advantages over a singly linked list:

Easier traversal: With a doubly linked list, each node has a pointer to both the previous and next node, allowing for easy traversal in both directions. This is useful for certain types of algorithms that need to move both forwards and backwards through the list.

Faster deletion: In a singly linked list, when you want to delete a node, you need to traverse the list to find the node before it, so that you can update the next pointer. In a doubly linked list, the node you want to delete already has a pointer to the previous node, so you can update the previous node's next pointer directly, making deletion faster.

Easier insertion: Similar to deletion, in a singly linked list, you need to traverse the list to find the node before the one you want to insert. With a doubly linked list, you can insert a new node directly before or after a given node, without the need to traverse the list.

Easier to implement in-place modification: With a doubly linked list, it is easy to move elements around within the list without creating new list elements or destroying old ones.

Easier to implement Queue and Stack : A doubly linked list makes it easy to implement queue and stack data structures.

Andes