Data Structures and Algorithms: “Mastering Linked Lists: From Novice to Node Ninja”

“Demystifying Linked Lists: A Comprehensive Guide to Node Structures”

· Intro: · Singly linked list (Uni-directional) · Doubly linked list (Bi-directional) · Circular linked list ∘ Pros 🔥 ∘ Cons 🤕 · GIFs ∘ Prepend ∘ Append ∘ Delete a Node · Insert an Item · Reverse · Big O Performance Analysis · Linked Lists in the Real World · Linked Lists in Interviews

Intro:

A linked list is a common data structure that is made of a chain of nodes. Each node contains a value and a pointer to the next node in the chain.

• The first node of a linked list is called the head, and the last node is usually called the tail.
• The head pointer points to the first node, and the last element of the list points to null. When the list is empty, the head pointer points to null.
• Linked lists can dynamically increase in size.
• It is easy to insert and delete from a linked list because unlike arrays, as we only need to change the pointers of the previous element and the next element to insert or delete an element.
• The elements are not stored at contiguous locations.
• They are commonly used to implement other data structures like Lists, stacks/queues or bucketing for hash tables..

Singly linked list (Uni-directional)

• A singly linked list is unidirectional, meaning that it can be traversed in only one direction from head to the last node (tail).
• A singly linked list means that each node will point to the next one in the list. This means you can move forward through the list but not backward.

Doubly linked list (Bi-directional)

These contain a pointer to the next node as well as the previous node.

This ensures that the list can be traversed in both directions. A DLL node has three fundamental members:

• The data
• Pointer to the next node
• Pointer to the previous node

Circular linked list

Circular linked lists function circularly: the first element points to the last element, and the last element points to the first. A single linked list and double linked list can be made into a circular linked list. The most important operations for a circular linked list are:

• insert − insert elements at the start of the list
• display − display the list
• delete − delete elements from the start of the list

Pros 🔥

• Flexible Size / Distributed: Data does not need to be sequential in memory. We can arbitrarily add/remove items in a linked list as long as we have a way to point to the next item.
• Ordered: Linked lists provide order by pointing to the next item in the linked list.
• Fast Insert / Delete: If we have access to a node (typically the head or tail), we get fast inserts and deletes because the only thing that is required is updating a pointer.
• Have faster prepends and faster appends than dynamic arrays, but they have slower lookups.

Cons 🤕

• Slow Lookups: There is no direct access to data (no keys/indexes). We must iterate through the list sequentially to perform a lookup.

GIFs

Prepend

Append

Note: If we did have access to the tail, we could also append in O(1) time.

Delete a Node

Insert an Item

Reverse

Big O Performance Analysis

Linked Lists in the Real World

• Browser back and forward buttons (doubly linked list where each page knows the one you visited before and after)
• Implementing stacks and queues (fast operations at the ends)
• Blockchain (distributed nodes are doubly linked lists that point to the one before and after)
• “Undo” button in your text editor

The pattern is that for all these implementations, they simply point to the item before and after the current one.

Linked Lists in Interviews

• Be comfortable taking an input head node of a singly linked list and iterating from there
• Always keep the runner technique in mind
• Understand how to manage multiple pointers
• Know the different linked list techniques and operations

Thank you for reading!

If you liked the article, please share and give some claps so others can find it 👏👏👏👏👏 !!!!