Source: Exam 2 Key, University of Central Florida
Tags: linked list, singly linked list, doubly linked list, head pointer, tail pointer, node struct, pointer manipulation, traversal, insertion, deletion, O(1) insertion, C programming
Difficulty: Intermediate Prerequisites: Comfortable with C pointers, dynamic memory allocation (malloc/free), and structs. Recursion notes from this same exam are also helpful, since several linked-list questions require recursive solutions.
Linked lists are the first dynamic data structure most CS students meet. Unlike arrays, they do not require contiguous memory or a fixed size at creation time. This exam tests your understanding of how nodes connect through pointers, the time complexity of common operations, the correct C struct definition, and your ability to write (or trace) code that inserts, removes, or traverses nodes. If you are shaky on pointer syntax in C (->, *, &), shore that up before diving into linked-list operations.
A linked list is a chain of heap-allocated nodes, each holding data and a pointer to the next node (and, in a doubly linked list, the previous node). The head pointer gives you entry to the list. Insertion at the head is O(1); accessing the nth element or inserting at the tail (without a tail pointer) is O(n).
Singly linked list
A data structure where each node contains a data field and a single pointer to the next node. Traversal is one-directional: you can move forward from head to tail, but not backwards.
Doubly linked list
A data structure where each node contains a data field, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions, at the cost of extra memory per node.
Node
The building block of a linked list. In C, typically defined as a struct containing data and one or more pointers. Think of it as a box that holds a value and an arrow pointing to the next box.
Head pointer
A pointer that always points to the first node in the list (not the last). If the list is empty, head is NULL.
Tail pointer
An optional pointer that tracks the last node. Keeping a tail pointer lets you insert at the end in O(1) time instead of O(n), because you skip the traversal.
NULL
The sentinel value that marks the end of a linked list. The last node's next pointer is set to NULL, which is how traversal loops know to stop.
malloc
The C library function that allocates memory on the heap. Every new node in a linked list is created with malloc (or a similar allocator).
free
The C library function that deallocates heap memory. When you remove a node from a list, you must free it to avoid memory leaks.
The correct C definition uses a pointer to the struct type for the next field:
struct node {
int data;
struct node *next;
};
Common wrong answers on this exam include using int next (an integer cannot store an address), struct node next without the asterisk (this would try to embed an entire node inside itself, which is impossible), or node *next without the struct keyword (not valid in C unless you use a typedef).
A typical typedef version:
typedef struct node {
int data;
struct node *next;
} Node;
Each node has exactly one pointer: next.
Nodes do not contain a pointer to the previous node. That is a doubly linked list feature.
The head pointer points to the first node, not the last.
The last (tail) node's next pointer is NULL.
Each node has two pointers: next and prev.
Traversal works in both forward and backward directions.
Uses more memory per node than a singly linked list because of the extra pointer.
Insert at head: O(1). You allocate a node, point its next to the current head, and update head. Two pointer assignments, no traversal.
Insert at tail (no tail pointer): O(n). You must traverse the entire list to find the last node.
Insert at tail (with tail pointer): O(1). The tail pointer gives you direct access.
Access the nth element: O(n). There is no index-based random access; you must walk the list from the head.
Search for a value: O(n). Worst case, you check every node.
Remove last node: O(n) for a singly linked list (you need the node before it). O(1) for a doubly linked list if you keep a tail pointer.
The correct pointer update sequence is:
newNode->next = head;
head = newNode;
Order matters. If you set head = newNode first, you lose the reference to the rest of the list. If you set newNode->next = NULL instead of head, you disconnect the chain.
Full example:
Node *head = NULL;
Node *newNode = malloc(sizeof(Node));
newNode->data = 10;
newNode->next = head;
head = newNode;
printf("%d", head->data); // prints 10
The correct loop pattern uses the head pointer (or a copy of it) and advances with head = head->next:
while (head != NULL) {
printf("%d", head->data);
head = head->next;
}
Common wrong versions:
while (head->next != NULL) skips the last node.
head[i].data treats the list like an array, which is not valid for heap-allocated nodes connected by pointers.
head.data uses dot notation instead of arrow notation; head is a pointer, so you need ->.
head++ does pointer arithmetic, which does not follow the next link and produces undefined behaviour.
Given a list 1 -> 2 -> 3 -> 4 with head pointing to the node containing 1:
head->next->next->data evaluates to 3 (skip two links from head, then read the data).
The key disadvantage tested on this exam: accessing a random element is not a constant-time operation. Arrays give you O(1) random access via indexing; linked lists require O(n) traversal.
Linked lists do not have a fixed size (that is an array limitation), and they are not slower at head insertion (that is an array weakness, since arrays require shifting elements).
Recursive solution:
Node *removeOdd(Node *head) {
if (head == NULL) return NULL;
Node *newNext = removeOdd(head->next);
if (head->data % 2 == 1)
return newNext;
head->next = newNext;
return head;
}
The function processes the rest of the list first (post-order style), then decides whether to keep the current node based on whether its data is odd. If odd, it skips the node and returns the cleaned-up tail. If even, it wires itself into the cleaned-up tail and returns itself.
Iterative solution (for reference):
Node *removeOdd(Node *head) {
// Remove leading odd nodes
while (head != NULL && head->data % 2 == 1) {
Node *temp = head;
head = head->next;
free(temp);
}
if (head == NULL) return NULL;
Node *prev = head;
Node *curr = head->next;
while (curr != NULL) {
if (curr->data % 2 == 1) {
Node *temp = curr;
prev->next = curr->next;
curr = curr->next;
free(temp);
} else {
prev = curr;
curr = curr->next;
}
}
return head;
}
Two exam variants gave a sorted linked list and code that walks through it, checking the difference between consecutive nodes:
If the difference exceeds a threshold (e.g. 15 or 10), a new node is inserted between them with a value equal to the current node's data plus 10. The inner while loop repeats this until the gap is small enough.
If the difference is below a second threshold (e.g. 4 or 5), the next node is removed.
Version 1 (thresholds 15 and 4):
Starting list: 20 -> 48 -> 57 -> 60 -> 66 -> 70 -> 75 -> 77 -> 82
Step-by-step changes:
48 - 20 = 28 > 15, insert 30 after 20
48 - 30 = 18 > 15, insert 40 after 30
48 - 40 = 8, not > 15, move on
60 - 57 = 3 < 4, remove 60
77 - 75 = 2 < 4, remove 77
Final list: 20 -> 30 -> 40 -> 48 -> 57 -> 66 -> 70 -> 75 -> 82
Version 2 (thresholds 10 and 5):
Starting list: 20 -> 48 -> 57 -> 60 -> 66 -> 69 -> 75 -> 77 -> 82
Step-by-step changes:
48 - 20 = 28 > 10, insert 30 after 20
48 - 30 = 18 > 10, insert 40 after 30
48 - 40 = 8, not > 10, move on
60 - 57 = 3 < 5, remove 60
69 - 66 = 3 < 5, remove 69
77 - 75 = 2 < 5, remove 77
Final list: 20 -> 30 -> 40 -> 48 -> 57 -> 66 -> 75 -> 82
The key to tracing these correctly is to note that the inner while loop can fire multiple times for a single pair (filling large gaps with several new nodes), and that after an insertion curr advances to the newly inserted node, not past it.
Operation complexity cheat sheet (singly linked list, no tail pointer):
Operation | Time |
|---|---|
Insert at head | O(1) |
Insert at tail | O(n) |
Insert at tail (with tail pointer) | O(1) |
Access nth element | O(n) |
Search for a value | O(n) |
Delete head | O(1) |
Delete tail | O(n) |
Linked lists underpin many higher-level data structures. Stacks and queues are commonly implemented as linked lists. Hash tables use linked lists for collision resolution (separate chaining). Operating systems use doubly linked lists for process scheduling queues. Understanding the pointer mechanics here translates directly to working with trees and graphs later in the course.
Students often think the head pointer points to the last node. It points to the first. The last node is the one whose next is NULL.
A common mistake is reversing the two-step head insertion: setting head = newNode before newNode->next = head. This orphans the existing list.
Students frequently assume linked lists can be indexed like arrays (head[i]). They cannot. You must traverse.
In a singly linked list, each node does not have a pointer to the previous node. That is a doubly linked list feature. Confusing the two will cost marks on true/false questions.
⚠️ The struct definition question appears regularly. Know that next must be declared as struct node *next (pointer), not struct node next (value) or int next.
⚠️ Pointer update order for head insertion is tested in isolation. The correct sequence is always: point the new node at the old head, then update head.
⚠️ The linked-list tracing questions (insert/remove based on difference thresholds) require careful step-by-step work. Write out the list state after every change, exactly as the exam key does.
⚠️ Know which operations are O(1) for a singly linked list: only insert at head (and delete at head). Everything else is O(n) without a tail pointer.
⚠️ The removeOdd function (or similar filter-by-condition) can appear as either a recursive or iterative coding question. Be able to write both versions.
True or false: in a singly linked list, each node contains a pointer to the previous node. (False)
True or false: a doubly linked list allows traversal in both directions. (True)
Fill in the blank: the head pointer of a linked list points to the __________ node. (first)
True or false: inserting a node at the beginning of a singly linked list takes O(n) time. (False, it is O(1))
What is the running time to access the nth element of a singly linked list? (O(n))
Q: What is a correct struct definition for nodes of an integer linked list in C?
A: struct node { int data; struct node *next; }; The next field must be a pointer to the same struct type.
Q: What is the correct pointer update sequence when inserting a new node at the beginning of a singly linked list?
A: newNode->next = head; followed by head = newNode;. The new node must point to the old head before head is reassigned.
Q: Which of the following is a correct loop to traverse a singly linked list?
A: while (head != NULL) { printf("%d", head->data); head = head->next; }. This visits every node and stops when it passes the last one.
Q: Given head pointing to the list 1 -> 2 -> 3 -> 4, what does head->next->next->data evaluate to?
A: 3. Starting from node 1, next reaches node 2, the second next reaches node 3, and data reads 3.
Q: Which of the following operations has O(1) running time in a simple singly linked list?
A: Insert at beginning (head). All other standard operations (insert at tail, remove last, search) require traversal and are O(n).
Q: What is a disadvantage of a singly linked list compared to an array?
A: Accessing a random element is not a constant-time operation. Arrays support O(1) indexing; linked lists require O(n) traversal.
Q: If we keep a tail pointer in addition to the head pointer, what improves?
A: Insert at the tail becomes O(1) instead of O(n), because you no longer need to traverse the entire list to find the last node.
Q: Write a recursive function that removes all nodes with odd values from a singly linked list.
A: See the removeOdd function above. Base case: if head is NULL, return NULL. Recurse on head->next. If current node's data is odd, skip it by returning the recursed result. Otherwise, wire the current node to the recursed result and return the current node.
Linked lists lead directly into stacks and queues (which are often implemented as linked lists with restricted insertion/removal points). They also appear inside hash table implementations as the chains in separate chaining. The recursive linked-list operations on this exam tie back to the recursion material: if you understand how the call stack works from the recursion notes, tracing recursive list manipulation becomes much more manageable.
linked list, singly linked list, doubly linked list, node, head pointer, tail pointer, NULL pointer, struct node, malloc, free, dynamic memory, pointer manipulation, insert at head, insert at tail, traversal, linked list traversal, O(1) insertion, O(n) access, linked list vs array, removeOdd, recursive linked list, iterative linked list, COP 3502, Computer Science I, UCF, C programming, exam 2 review