15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 5 of 12 in the free DSA Basics course · 6 lessons
This lesson covers the mental model and basic operations for Basic Linked Lists. A singly linked list stores values in separate nodes. Each node holds data and a reference to the next node, while a head reference identifies where the list begins.
You will follow references safely, visit nodes, add and remove nodes, simplify edge cases with helper nodes, and identify when a list loops back to its start instead of ending at null.
No prior roadmap lessons are required.
You should be comfortable with variables, simple conditionals, loops, and the idea that a variable can store a reference to an object or node.
Use this list throughout the path:
1head -> [4] -> [7] -> [9] -> nullEach bracket is a node. For example, [7] contains the value 7 and a next reference to [9].
Start by following the list from head:
1curr = head
2
3curr: [4] -> [7] -> [9] -> nullMove curr one node at a time. It visits 4, then 7, then 9, and finally becomes null.
To insert [6] after [4], preserve the old connection first:
1[6].next = [4].next // [6].next becomes [7]
2[4].next = [6]The result is:
1head -> [4] -> [6] -> [7] -> [9] -> nullTo delete [7], use its predecessor, [6], to bypass it:
1[6].next = [7].nextNow the list is:
1head -> [4] -> [6] -> [9] -> nullLater, the same values can form a circular list by changing the final link:
1head -> [4] -> [6] -> [9]
2 ^ |
3 |______________|The circular list has no null terminator, so it needs a different stopping rule.
Node Structure and Pointers defines what a node contains, what head refers to, and how next links nodes until null.
Traversal in Linked Lists follows references to inspect a list, count nodes, find a position, or locate the predecessor needed by later updates.
Insertion Techniques builds on traversal. Inserting at the front is local. Inserting after a position requires finding the correct node and connecting the new node without losing its old successor.
Deletion Techniques uses the same reference-update reasoning as insertion. Deletion reconnects a predecessor to a removed node’s successor.
Dummy and Sentinel Nodes addresses a head-operation boundary case: the first real node has no predecessor. A helper node can provide one.
Circular Linked List Concepts replaces the normal null ending rule. Trace ordinary lists and preserve links before reasoning about a structure that loops.
A linked list stores nodes separately. head identifies the first node, and each node provides the route to the next one. To reach later values, repeatedly follow next.
Traversal begins at head, processes the current node, then moves to curr.next. In an ordinary singly linked list, null means there are no more nodes. If there are nodes, visiting all of them takes linear time because each node is visited once. The traversal uses a fixed number of references and counters. Traversal does not mutate the list.
Insertion and deletion change links after you already have the needed node reference. For example, inserting after [4] is constant time because only two next references change. Inserting at a numbered position may require traversing from head first, making the full operation linear time. Insertion and deletion mutate next references and may mutate head.
Order matters when changing links. During middle insertion, connect the new node to the old successor before replacing the predecessor’s link. Otherwise, the route to the remaining suffix can be lost. During deletion, the predecessor’s next skips the removed node. Advancing a current pointer does not change the list structure.
A dummy node temporarily sits before the real head. The first real node then has a predecessor, so deletion logic handles head deletion with the same link update used for other deletions. After the operation, dummy.next is the real head. A sentinel node uses a similar idea and remains part of the list’s representation.
A circular list has a final node whose next points back to the first node. A curr != null loop never finishes on a nonempty circular list. Start at a known node and stop when you return to that same node after one complete cycle. Empty and one-node circular lists need explicit attention.
Draw head -> [4] -> [7] -> [9] -> null. Label each node’s data and next field. Then distinguish the null reference from a node containing 0.
Trace a traversal pointer on the example list. Record the values visited and count how many pointer advances occur before reaching null.
Insert [6] after [4]. Write the two reference assignments in the safe order, then redraw the list.
Insert a node at the front and update head. Then insert a node at a later zero-based position, noting which part requires traversal.
Delete [7] from head -> [4] -> [6] -> [7] -> [9] -> null by updating [6].next. Separately trace deletion of the first node and identify why head must change.
Add a temporary dummy node before the example list. Use it to remove a target value, including the case where the target is the first real node. Return dummy.next.
Convert the final ordinary list into a circular list by linking its last node back to head. Trace exactly one cycle and stop when the traversal pointer returns to the starting node, not when it reaches null.