Difficulty: Beginner | Prerequisites: Basic C syntax, pointers, structs, dynamic memory allocation (malloc/free).
Linked lists are one of the first data structures you meet after arrays, and they show up everywhere in systems programming, operating systems, and later courses on algorithms. They introduce you to pointer-based thinking, which is foundational for trees, graphs, and most non-trivial data structures. If you are comfortable with C pointers and malloc, you are ready. If pointers still feel shaky, review those first, because every operation on a linked list is a pointer operation.
A linked list is a chain of nodes where each node holds a value and a pointer to the next node. Unlike arrays, linked lists grow and shrink at runtime without pre-declaring a size. The trade-off is that you lose random access: to reach the fifth element, you must walk through the first four.
Node
The fundamental building block of a linked list. Each node contains two things: the data it stores (e.g. an int) and a pointer (next) to the following node in the chain. Think of it as a box holding a value with an arrow pointing to the next box.
Head
A pointer to the first node in the list. The head is how you enter the list; every traversal starts here. In simple terms, it is the front door of the linked list.
Tail pointer
An optional pointer to the last node in the list. Keeping one around makes appending to the end O(1) instead of O(n). Think of it as a bookmark for the back of the list so you do not have to walk the whole chain every time you add something at the end.
NULL
A special pointer value that means "nothing here." The last node's next pointer is set to NULL to signal the end of the list. In simple terms, NULL is the stop sign at the end of the chain.
Singly linked list
A list where each node points only to the next node. Traversal goes in one direction: front to back.
Doubly linked list
A list where each node has two pointers, one to the next node and one to the previous node. This lets you traverse in both directions, which is useful for operations like reverse traversal or deletion when you already have a pointer to the node.
Circular linked list
A list where the last node points back to the head instead of to NULL, forming a loop. Can be singly or doubly linked. Useful for things like round-robin scheduling.
Dynamic memory allocation
The process of requesting memory at runtime using malloc (and releasing it with free). Linked lists rely on this because nodes are created on the fly, unlike arrays whose size is fixed at compile time.
In C, a node is defined with a self-referential struct. The struct contains the data field and a pointer to another instance of the same struct:
typedef struct LLNode_s {
int data;
struct LLNode_s *next;
} LLNode;
data holds the value stored in the node.
next is a pointer to the next LLNode in the list, or NULL if this is the last node.
The struct tag LLNode_s is needed inside the definition because the typedef name LLNode is not available until the definition closes. This is a common point of confusion.
A wrapper struct for the list itself typically holds the head pointer:
typedef struct LList_s {
LLNode *head;
} LList;
This keeps the head pointer in one place and lets functions modify it without double-pointer gymnastics.
Singly linked list
Each node has one pointer (next).
One-directional traversal only.
Simplest to implement; lowest memory overhead per node.
Use when you only need forward traversal and insertions/deletions at the head or after a known node.
Doubly linked list
Each node has two pointers (next and prev).
Supports forward and backward traversal.
Deletion of a known node is simpler because you already have the previous pointer.
Costs one extra pointer per node in memory.
Circular linked list
The last node's next pointer points back to the head (singly circular) or the head's prev points to the last node as well (doubly circular).
No NULL terminator; you detect a full traversal by returning to the starting node.
Useful for cyclic processes like task schedulers and buffering.
Arrays:
Fixed size, set at compile time (in standard C).
O(1) random access by index.
Insertion and deletion in the middle cost O(n) because elements must shift.
Linked lists:
Dynamic size; nodes are allocated as needed.
No random access; reaching element k requires walking k nodes from the head (O(n)).
Insertion and deletion at a known position cost O(1) because you only redirect pointers.
Each node carries extra memory for the pointer(s).
The short version: arrays win on access speed, linked lists win on flexible sizing and cheap insertions/deletions.
Linked lists underpin many systems you interact with daily. The undo/redo stack in a text editor, the browser's forward/back history, and the process scheduler in an operating system all use linked-list variants. Music playlists that loop use circular linked lists.
Students often think linked lists are "better" than arrays. They are not universally better; they trade random access for flexible size and cheap insertions. The right choice depends on the use case.
Students often assume the head is a separate, special node with no data. The head is simply a pointer to the first node, which holds data like any other node.
Students sometimes forget that the last node's next must be set to NULL. Failing to do this causes traversal loops or segmentation faults.
Students often confuse the struct tag (LLNode_s) with the typedef name (LLNode) and wonder why the self-referential pointer uses the tag. The typedef is not yet available inside the struct definition, so the tag is required there.
⚠️ Expect questions asking you to compare arrays and linked lists by time complexity for access, insertion, and deletion.
⚠️ Know the difference between singly, doubly, and circular linked lists, and be able to name a use case for each.
⚠️ Be able to write a node struct from scratch in C, including the self-referential pointer.
⚠️ Understand why the wrapper struct (LList) with a head pointer exists and how it simplifies function signatures.
True or false: A singly linked list can be traversed backwards efficiently.
A: False. Singly linked lists support forward traversal only; backward traversal requires O(n) reversal or a doubly linked list.
Fill in the blank: The last node in a (non-circular) linked list has its next pointer set to ______.
A: NULL.
True or false: Accessing the 10th element of a linked list is O(1).
A: False. It is O(n) because you must traverse from the head.
Q: What are the two components stored in a singly linked list node?
A: The data (e.g. an integer) and a pointer to the next node.
Q: Why does the C struct for a linked list node use the struct tag (LLNode_s) for the self-referential pointer rather than the typedef name (LLNode)?
A: Because the typedef name is not available until the struct definition is complete; the tag is in scope during the definition.
Q: Name one advantage of a doubly linked list over a singly linked list, and one disadvantage.
A: Advantage: you can traverse in both directions (and delete a node without needing a separate pointer to its predecessor). Disadvantage: each node uses extra memory for the prev pointer.
Q: In what situation would a circular linked list be more appropriate than a standard singly linked list?
A: When the process is cyclic, such as round-robin task scheduling or a looping playlist, where after the last item you need to return to the first.
Q: What is the time complexity of accessing the kth element in a linked list, and why?
A: O(n). There is no indexing; you must walk through nodes sequentially from the head.
This material connects to stacks and queues, which are commonly implemented using linked lists (a stack is a linked list where you only insert and remove at the head; a queue uses head and tail pointers). It also lays the groundwork for trees and graphs, where nodes have multiple pointers rather than just one or two.
linked list, singly linked list, doubly linked list, circular linked list, node, head pointer, tail pointer, NULL pointer, dynamic memory allocation, malloc, free, self-referential struct, pointer-based data structure, arrays vs linked lists, sequential access, COP 3223, Computer Science I, UCF, data structures in C