Unit 2: Linked lists
Data Structures-I notes · PTU syllabus (UGCC2506)
On this page
Unit summary
A linked list stores elements in nodes scattered anywhere in memory, each node pointing to the next. Unlike an array, it can grow and shrink at run time and allows fast insertion and deletion. This unit covers singly, doubly and circular linked lists.
After this unit you can
- Compare arrays and linked lists
- Represent a linked list in memory using nodes and pointers
- Traverse, insert, delete and search in singly, doubly and circular lists
- List applications of linked lists
PTU syllabus topics
- Definition
- comparison with arrays
- representation
- singly/doubly/circular linked lists — traversing
- inserting
- deleting
- searching
- applications of linked lists
Topic 1
Linked list and comparison with arrays
A linked list is a linear collection of nodes, where each node contains data and a pointer (link) to the next node. The first node is reached through a pointer called START (or HEAD); the last node's link is NULL.
Memory
Consecutive locations
Scattered; nodes linked by pointers
Size
Fixed at declaration
Dynamic: grows and shrinks
Access
Direct by index: O(1)
Sequential from START: O(n)
Insertion/deletion
Slow: elements must be shifted
Fast: only pointers change
Extra memory
None
One pointer per node
Topic 2
Representation in memory
The last node's next field is NULL; START holds the address of the first node
cstruct node {
int data;
struct node *next;
};
struct node *start = NULL;New nodes are created at run time with malloc(sizeof(struct node)) and released with free(). Free nodes can also be kept in an AVAIL list (free storage list).
Topic 3
Singly linked list operations
- Traversal: start with
ptr = start; whileptr != NULL, processptr->dataand moveptr = ptr->next. - Search: traverse and compare each node's data with the item: O(n).
- 1Create a new node
newnode = malloc(...)
- 2Store data
newnode->data = item
- 3Link to old first node
newnode->next = start
- 4Move START
start = newnode
- Insert at end: traverse to the last node and set
last->next = newnode, withnewnode->next = NULL. - Insert after a given node:
newnode->next = loc->next; loc->next = newnode; - Delete: make the previous node skip the deleted one:
prev->next = loc->next;thenfree(loc). Deleting the first node changes START.
Example
Insert 15 after 10 in the list 10 → 20 → 30: loc points to the node 10. Step 1: newnode->next = loc->next — the new node now points to 20. Step 2: loc->next = newnode — 10 now points to 15. Result: 10 → 15 → 20 → 30. If the two steps are done in the opposite order, loc->next already points to the new node, so the link to 20 is lost and the rest of the list cannot be reached.
Exam tip
Always handle the special cases: empty list (underflow), inserting into an empty list and deleting the first node.
Topic 4
Doubly and circular linked lists
- Doubly linked list: each node has two pointers, prev and next, so it can be traversed in both directions and a node can be deleted without searching for its predecessor. It uses more memory.
- Circular linked list: the last node points back to the first instead of NULL, so the list can be traversed from any node. It is useful for round-robin scheduling.
Singly
One (next)
Simple, least memory
Doubly
Two (prev, next)
Two-way traversal, easy deletion
Circular
One, last points to first
Continuous looping from any node
Example
Deleting a node from a doubly linked list: to remove 20 from 10 ⇄ 20 ⇄ 30, with loc pointing to 20: loc->prev->next = loc->next (10 now points forward to 30), loc->next->prev = loc->prev (30 now points back to 10), then free(loc). Two pointers change and no search for the previous node is needed — the main advantage over a singly linked list.
Exam tip
When writing linked-list algorithms, draw boxes and arrows for a small list before and after the operation; examiners give marks for the diagram as well as the code.
Topic 5
Applications of linked lists
- Implementing stacks and queues dynamically.
- Polynomial representation and addition: each node stores a coefficient and an exponent.
- Dynamic memory management (free lists).
- Undo/redo, browser back/forward history (doubly linked list) and music playlists (circular list).
Key terms
- Node
- An element of a linked list holding data and a link
- START/HEAD
- Pointer to the first node of the list
- NULL pointer
- Marks the end of a singly linked list
- Doubly linked list
- A list whose nodes link to both previous and next nodes
- Circular linked list
- A list whose last node points back to the first
Quick revision
- Linked list = dynamic size, sequential access, cheap insert/delete.
- Insert at beginning: newnode->next = start; start = newnode.
- Delete: prev->next = loc->next; free(loc).
- Doubly: two-way; circular: last → first.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a linked list.
- Q2.Give two advantages of linked lists over arrays.
- Q3.What is a NULL pointer in a linked list?
- Q4.Differentiate between singly and doubly linked lists.
- Q5.What is a circular linked list?
- Q6.List two applications of linked lists.
Long-answer questions
- Q1.Compare arrays and linked lists in detail.
- Q2.Write algorithms to insert a node at the beginning, at the end and after a given node of a singly linked list.
- Q3.Explain deletion of a node from a doubly linked list with a diagram.
- Q4.Explain the representation of polynomials using linked lists.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures-I, or to ask about studying BCA at Synetic.
