A quick cheat sheet / mini-quiz on LinkedLists to brush up on the fundamentals.
This blog post will be formatted with a question and then a corresponding answer. I find that having a question posed can help solidify my ability to recall information as well as force me to have a better understanding of the topic. See if it does the same for you.
As you go through the blog try to answer the questions in your own words before looking at the provided answer.
What is a Linked List?
- A linear data structure with composed of ‘nodes’ that are linked with pointers. They are null-terminated, indicating that the last node will point to a null value. The first node is termed the Head and the final node termed the Tail.
What is a Node?
- A node is an object composed of two (sometimes 3) elements: data and a reference aka value and pointer.
- The data/value stores the data while the reference/pointer points to the next node within the list.
- e.g → node = {value: (data), pointer: (reference to next node)}
What are the two types of Linked Lists — how are they different?
- Singly: composed of a value and a single pointer to the next node → traverses from head to tail
- Doubly: composed of a value and two pointers — one points to the previous node, the other points to the next node → traverse from head to tail or tail to head
What are the Pros and Cons of these two type of lists?
- Singley → takes less space due to having only one pointer, and therefore has less operations within insert and delete and thus slightly faster
Downside: cannot iterate backwards, if you lose the head node the list can be lost forever.
*When to use: when you have less memory or want to be careful about how much memory you have to use and your main goal is fast insertion and deletion → especially if you only insert to the front or end (think stack).
- Doubley → takes more space, but allows you to traverse backwards. If you need to delete a previous node you can do that fairly easily without traversal.
*When to use: good for when you don’t have many limitations for memory and when searching for elements.
Why would Linked Lists be better than Arrays or HashTables?
- Linked lists have a sort of loose structure → allows you to insert in the middle of the list by simply adjusting a few pointers. You can insert whatever you want.
- Compared to arrays → it doesn’t require a revision of indices within the arrays → O(n)
What are the bigO for linked list operations?
- prepend → O(1)
*inserting at the head only takes repositioning the pointer for the new head to the previous head - append → O(1)
*inserting at the tail only takes repositioning the pointer of the previous tail to the new tail - lookup → O(n)
*require you to traverse the list until you find the value - insert → O(n)
*requires you to traverse the list until you find the location to insert → then readjust the pointers adjacent to its location
** - delete → O(n)
*requires you to traverse the list until you find the location to delete → then readjust the pointers adjacent to its location
What is a pointer?
- A reference to another place/object/node in memory.
Define the structure of a linked list.
- We start the list with a Head node.
- Each node contains a bucket → each bucket contains two elements: value and next
- Each next element will contain the next node → a bucket with the same two elements: value and next.
- We know we’ve reached the end of the list when next points to null (null-terminated).
When defining a linked list, what is instantiated within the constructor method?
- head, tail, length
How does garbage collection impact Linked Lists?
- Garbage collection is available in higher-level languages like JS. It cleans up memory slots that do not have a reference pointer pointed at it.
- In regards to linked lists, garbage collection will automatically delete a node from memory if there is no pointer pointed at it → this allows for operations like remove() to simply reassign the pointers to the preceding node to the newly inserted node, without having to worry about deleting the unlinked node/removed node.
How would you write a linked list class?
Depending on the language you’re most familiar with the answer may vary. But take some time to walk through a solution. Consider what operations are inherent to linked lists, and try writing out a class definition for an array in pseudo-code (or actual code) and see how well you understand it.
That’s it for this mini-quiz/cheatsheet. Hope it tickled your brain and you had some fun!