I Know a Node that Knows a Node
What is a Linked List and when are they useful?
I don’t know about you, but I am a huge fan of all sorts of links! I love links in an article that take you to a separate piece of information that provides clarity, I love a delicious sausage link with some toast and runny egg, and I love finding out someone I know has a link/connection to someone I need to know.
Links are very important not only in our everyday lives, but also in the world of programming. Today we are going to explore the benefits and use cases of the Linked List Data Structure.
Let’s get started!
What is a Singly Linked List?
A singly link list is a linear collection of nodes that are connected together via a link. Each node in the list contains some sort of data and a link to the next node. The data being stored in each node can be anything, examples being a digit, string, or another data structure such as an array.
What is a Doubly Linked List?
A doubly linked list is almost identical to a singly linked list except each node will not only hold a link to the next node, but also a link to the previous node.
Some Important Terminology For a Linked List
Head: the first node of linked list
Next: each node of the linked list will hold some data and a link to the next node. This link is called next. The link to next of the tail of a doubly linked list will point to null
Previous: each node of a doubly linked list will hold a link to the next node and a link to the previous node. The link to previous of the head will point to null
Tail: the last node of the linked list. Because this node is the end of the list, its next link will point to null
Length: an attribute of the linked list that lets you know how many nodes are part of the list.
When is a Linked List Useful?
Linked lists are much more efficient than an array when it comes to insertion and deletion of data. Because the nodes of a linked list are not indexed like the values in an array, a node can be deleted or inserted without having to re-index/reorder the other nodes. Linked lists also provide flexibility in size versus a fixed array that has an upper limit and the amount of memory directly correlates to that upper limit.
When is a Linked List Less Performant?
In contrast the lack of indices in a linked list makes random retrieval less efficient. Traversal of a singly linked list must begin at the head and follow the link to the next node until the desired node is reached. This is slightly more efficient for a doubly linked list due to the increased flexibility for direction changes (ability to look at next and previous). If space is a priority a link list may not be the best choice. They do require additional allocation in memory in order to store the pointers/links to previous and next.
What are some Real World Use Cases?
In the real world some pretty common use cases for linked lists would be a camera roll or a music playlist. Both scenarios require some order and knowing what data comes before and what data comes after a current photo or song. The ability to traverse through this data going forward and backward is very important for an optimal user experience.
Key Takeaways
- Nodes of a linked list are connected via pointers to the next or previous node
- Highly efficient for insertion and deletion of nodes
- Linked lists are rather slow when accessing a random index, due to the need to start at the head and iterate through the list
