Stack Bash - Master data structures and algorithms

Linked List Data Structure

A linked list is a data structure that is made up of a group of nodes that are connected to eachter.
A node often contains:
  1. Some data.
  2. A pointer to the next node in the linked list.
The head of the linked list is a pointer to the first node in the list.
While the tail of a linked list is a pointer to the last node
Here's an example of a linked list of numbers:
Example of a Linked List with a head and tail


In Python, the above linked list can be implemented below:
We are left with head and tail to access data in the linked list.

Linked List Big O Overview

Note to get to another node, for example the third node, we must iterate through each node's next pointer until we reach the third one.

Linked List Pros

  1. Append to the end of the list in constant time
new_node = Node(data) = new_node
tail = new_node
  1. Similarly, prepend in constant time
new_node = Node(data) = head
head = new_node
  1. A linked list doesn't need a preset size since new nodes can be added any time.

Linked List Cons

The main con with a linked list is that accessing any other node costs O(n) time.
Another con is that since nodes in the list aren't necessarily in contiguous location in memory, which makes it not cache-friendly.

8 Essential Linked Lists Coding Interview Problems

Master Linked Lists by trying the coding challenges below.
  1. 1.Insert NodeEasy
  2. 2.Remove NodeEasy
  3. 3.Find the MiddleEasy
  4. 4.Add Linked ListsEasy
  5. 5.Reverse Linked ListMedium
  6. 6.Detect CycleMedium
  7. 7.Merge Linked ListsMedium
  8. 8.Pivot Linked ListHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.