Difficulty: Introductory to Intermediate | Prerequisites: Arrays, pointers in C, dynamic memory allocation (malloc/free)
Linked lists are the first data structure most CS students encounter beyond arrays, and they underpin stacks, queues, graphs, and hash tables later in the course. Where arrays give you fast random access but rigid sizing, linked lists give you flexible, node-by-node memory allocation at the cost of sequential access. Understanding linked lists also forces you to get comfortable with pointers and heap memory, which is the real pedagogical point. If you are shaky on pointer syntax or malloc, revisit those before diving in here.
TL;DR: A linked list stores elements in individually allocated nodes connected by pointers. You gain flexible insertion and deletion but lose random access. Singly linked lists point forward only; doubly linked lists point both ways; circular lists loop back to the start.
Singly linked list
A linear data structure where each node holds a data field and a single next pointer to the following node. The last node's next is set to NULL.
In simple terms, think of it as a chain where each link knows about the next link but has no idea what came before it.
Doubly linked list
A linked list where each node contains three fields: data, next, and prev. The prev pointer allows traversal in both directions.
In simple terms, each link in the chain knows both its neighbour ahead and its neighbour behind.
Circular linked list
A linked list (singly or doubly) in which the last node's next pointer points back to the head node rather than to NULL. This allows traversal from any node to every other node without restarting from the head.
Think of it as a ring rather than a chain: there is no natural "end."
Head pointer
A pointer to the first node of a linked list. Most list operations begin by following this pointer.
Tail pointer
A pointer to the last node. Not always maintained, but when it is, it makes insertion at the end O(1).
Dummy head node (sentinel node)
A placeholder node at the front of the list that holds no real data. Its purpose is to simplify insertion and deletion logic by eliminating special cases for an empty list or for operations on the first element.
In simple terms, it is a fake first node that exists so your code never has to ask "is the list empty?" as a separate branch.
NULL terminator (in singly linked lists)
The convention that the last node's next pointer is set to NULL, signalling the end of the list. Circular lists do not use this convention.
Linked lists support dynamic memory allocation: the list grows and shrinks as nodes are added or removed, with no need to declare a fixed size up front.
Linked lists allow constant-time insertion at the beginning (O(1)), because you only update the head pointer and one next pointer.
Arrays provide random access in O(1) via indexing. Linked lists do not. Accessing the kth element requires walking k nodes from the head, making access O(n). This is the single most important difference to remember.
Deletion of a known node is efficient in linked lists (pointer reassignment) compared to arrays (which require shifting elements).
Each node: data + next pointer.
Traversal is forward-only. To reach any element, you start at the head and follow next pointers.
Searching for a value is O(n) in the worst case, because you may need to visit every node.
Insertion at the beginning is O(1). Insertion at the end is O(n) unless you maintain a tail pointer.
Deletion of a node requires access to the node before the one you want to remove, because you need to update that predecessor's next pointer. This is the main disadvantage compared to doubly linked lists.
Each node: data + next + prev.
Traversal works in both directions: forward via next, backward via prev.
Uses more memory per node than a singly linked list (one extra pointer per node).
Insertion and deletion are conceptually cleaner because you always have access to both neighbours, but you must update more pointers per operation. Forgetting to update the prev pointer during insertion or deletion will make the list inconsistent, and backward traversal will break silently.
The last node's next pointer points to the head instead of NULL.
Allows traversal from any node to every other node, which is useful for round-robin scheduling, circular buffers, and similar applications.
Standard while (temp != NULL) traversal loops do not work here because no node is NULL. You need a do...while loop that checks whether you have returned to the starting node.
Insertion at the beginning (singly): O(1)
Insertion at the end (singly, no tail pointer): O(n)
Search (singly or doubly): O(n)
Deletion of a known node (doubly): O(1) for the pointer work, assuming you already have a reference to the node
Random access by index: O(n) for all linked list types
Linked lists are the backbone of more complex structures: hash tables use them for chaining, operating systems use circular lists for process scheduling (round-robin), and undo/redo stacks in editors often rely on doubly linked list logic. If you have ever wondered how a music player loops a playlist, that is a circular linked list at work.
Students often assume linked lists support random access like arrays. They do not. There is no indexing operator; you must traverse from the head.
Students confuse "efficient deletion" with "O(1) deletion." Deletion of a node is only O(1) if you already have a pointer to it (and, for singly linked lists, to its predecessor). Finding the node to delete is still O(n).
In circular lists, students frequently use while (temp != NULL) for traversal. This causes an infinite loop because no node in a circular list is NULL. Use a do...while loop that terminates when temp returns to the head.
Students sometimes forget to update the prev pointer when inserting into a doubly linked list. The list will appear correct when traversed forward but will be broken when traversed backward.
⚠️ Expect questions that ask you to compare arrays and linked lists. The answer almost always hinges on random access (arrays win) vs dynamic insertion/deletion (linked lists win).
⚠️ Know the three fields in a doubly linked list node (data, next, prev) cold. Fill-in-the-blank questions test this directly.
⚠️ Circular list traversal bugs are a favourite exam topic. Be ready to identify the difference between a while loop and a do...while loop in this context.
⚠️ Understand why insertEnd with a singly linked list head pointer passed by value cannot modify the caller's pointer. This is a common bug-tracing question (see the code notes for detail).
True or False: A singly linked list allows backward traversal.
A: False. Only doubly linked lists support backward traversal via the prev pointer.
Fill in the blank: In a circular singly linked list, the last node's next pointer points to ____.
A: The head node.
True or False: Searching for an element in a singly linked list is O(log n).
A: False. It is O(n), because there is no way to skip ahead; you must check nodes sequentially.
Fill in the blank: A dummy head node simplifies insertion and deletion by avoiding special cases for ____.
A: The head (i.e. operations on the first element, or on an empty list).
Q: Which of the following is NOT an advantage of linked lists over arrays: dynamic memory allocation, constant-time insertion at the beginning, random access of elements, or efficient deletion of nodes?
A: Random access of elements. Arrays support O(1) random access; linked lists do not.
Q: What is the time complexity of searching for an element in a singly linked list?
A: O(n). You may need to traverse the entire list.
Q: What is the main disadvantage of singly linked lists compared to doubly linked lists?
A: You cannot traverse backward, and deleting a node requires access to the previous node (which means an extra traversal to find it).
Q: Compare the memory usage of singly vs doubly linked lists.
A: Doubly linked lists use more memory per node because each node stores an additional prev pointer.
Q: What is the benefit of using a dummy head node in a linked list?
A: It simplifies insertion and deletion logic by eliminating the need for special-case handling when the list is empty or when operating on the head node.
This material connects directly to stacks and queues, which are often implemented using linked lists under the hood. It also sets the stage for hash tables (chaining uses linked lists to handle collisions) and graph representations (adjacency lists are arrays of linked lists). If you are heading into trees next, note that a tree node is essentially a linked list node with two (or more) next pointers instead of one.
linked list, singly linked list, doubly linked list, circular linked list, node, head pointer, tail pointer, NULL terminator, sentinel node, dummy head, dynamic memory allocation, pointer traversal, insertion at beginning, deletion by value, O(n) search, linked list vs array, COP 3502, Computer Science I, UCF, data structures in C