A.1.5: Linked Lists
Learning Objectives
Linked lists store ordered data using nodes that each contain a payload and a pointer to the next node
A pointer is a memory address, called "pointer" for illustration purposes
When to use linked lists vs arrays
How to execute common linked list operations such as inserting and deleting nodes
Introduction
Linked lists store ordered lists of data where elements (aka "nodes") may not be stored in contiguous blocks of memory. Each node contains a payload (numbers in above illustration) and a pointer to the next node (arrows in above illustration).
The benefit of noncontiguous data is that inserting or deleting a node from anywhere in a linked list is an O(1)
operation because only adjacent nodes need updating, instead of all subsequent elements in an array. The drawback of this is that accessing an element in the middle of a linked list requires O(n)
traversal, instead of O(1)
access with an array.
Below is a comparison of runtimes for common array and linked list operations.
Operation  Runtime (Arrays)  Runtime (Linked Lists) 

Insertion/Deletion (start) 


Insertion/Deletion (middle) 


Insertion/Deletion (end) 


Access element at specific index 


We typically use linked lists when we need efficient deletion of the first element in a list, for example to implement queues. We also use linked lists when we may not have sufficient contiguous storage space, for example in file systems on our hard drives.
Common Linked List Operations
Linked list node definition
The following linked list node definition is the definition LeetCode uses for linked list problems. Each node will have 2 properties val
and next
that can be accessed with dot notation like with any other class instance, e.g. node.val
and node.next
, where node
is a ListNode
instance.
Linked list traversal
Given a linked list head node node
, we can traverse the linked list with a while loop and calling node = node.next
at the end of the loop, where next
is a property of the linked list node that points to the next node.
Insert and delete node in linked list
To insert a node in a linked list we need to:
Point the "next" pointer in the new node to the node ahead of it in the list
Point the "next" pointer of the node behind the new node to the new node
To delete a node in a linked list we need to:
Point the "next" pointer of the previous node to the node after the current node, effectively removing the current node from the chain of nodes in the linked list
Exercises
After attempting each problem, find solutions in the Leaderboard tab (HackerRank, may be on left side of page) or Solution or Discuss tabs (LeetCode) on that problem's page. If you get stuck for more than 15 minutes, review and understand the solutions and move on. Come back and reattempt the problem after a few days.
For problems with both HackerRank and LeetCode, implement a solution on the platform you are least comfortable with; feel free to submit on both.
PreClass
Print the elements of a linked list (HackerRank)
Insert a node at the tail of a linked list (HackerRank)
Part 1
Insert a node at the head of a linked list (HackerRank)
Insert a node at a specific position in a linked list (HackerRank)
Delete a node from a linked list (HackerRank)
Remove linked list elements (LeetCode)
Part 2
Palindrome linked list (LeetCode)
Middle of the linked list (LeetCode)
Print the elements of a linked list in reverse (HackerRank)
Compare two linked lists (HackerRank)
Part 3
Get the value of the node at a specific position from the tail (HackerRank)
Delete duplicate value nodes from a sorted linked list (HackerRank, LeetCode)
Hint: Keep track of prev node and next node. When we encounter duplicate, update prev node's next value to next node
Merge two sorted linked lists (HackerRank, LeetCode)
Reverse a linked list (HackerRank, LeetCode)
Hint: For given node, keep track of old next node and new next node
Hint: Inside while loop:
Old next node is
node.next
Assign
node.next
to new next node (the node we just visited)Assign new next node variable to
node
Assign
node
to old next node
More Comfortable
Find the merge point of two joined linked lists (HackerRank, LeetCode)
Insert a node into a sorted doubly linked list (HackerRank)
Reverse a doubly linked list (HackerRank)
Detect whether a linked list contains a cycle (HackerRank, LeetCode)
Last updated