loading...

Looking At Linked Lists

denisepen profile image Denise Pen ・1 min read

A linked list is a data structure that includes a 'linked' sequence of nodes. Each node contains data.

In a singly linked list each node points to the next node in the linked list:

Imgur

In a doubly-linked list each node points to the next node as well as the previous node:

Imgur

In order to access a single node you must traverse the entire linked list until you land on that node.

For example, to find node 4 we must start at node 1, move to node 2, then node 3, and finally to node 4:

Imgur

This is very different from an array where each value can be found by using it's index, or a dictionary (hash/object) where a value can be found using it's key.

One benefit of a linked list is that you can add a node to the beginning of a linked list using constant time (O(1)). This means that subsequent nodes do not need to be re-indexed as they do in an array. The newest node simply becomes the "head" of the linked list.

Imgur

Have you ever used linked lists in your applications?

If so why did you choose them over other data structures?

Originally published at http://deniseonaquest.com/looking_at_linked_lists

Discussion

pic
Editor guide
Collapse
jwollner5 profile image
John 'BBQ' Wollner

I haven't used linked lists in 30y,but at that time, I was working on a banking application and we needed to track and present a set of chronological transactions. We did not have a meaningful RDBMS for PC's, so we created our own in memory and disk persisted, using essentially the same linkage, translating the pointers into primary keys. The product never made it to market (long story) and I have rarely used this approach since.

That said, it underpins a number of standard data structures used today, just hidden in the background.

Collapse
denisepen profile image
Denise Pen Author

Which data structures are you referring to when you say "it underpins a number of standard data structures used today". I'm assuming stacks and queues. Is there anything else?

Also, thanks for responding. I'm learning so much from reading responses to all the blog posts.

Collapse
jwollner5 profile image
John 'BBQ' Wollner

I was thinking ques and stacks, but also task continuations / cancelations - all linking of a form

Collapse
dystroy profile image
Denys Séguret

There are three things to know regarding linked list based structures (including double linked lists and more complex structures):

  • they're very rarely the most efficient structure, even if their theoretical big O cost is pretty. They consume a lot of memory and this memory is fragmented.

  • they almost always imply tricky corner cases which means a big test list and some unexpected bugs after months or years of production (true story, and that was billions of computations during 15 years until a case that I finally understood)

  • sometimes they're useful... probably not for your problem, and you should have checked you didn't in fact need a ring buffer or a vector, but yes there are still some use cases...