Singly Linked List · Data Structures and Algorithms

Singly Linked List

CSC-211 · Semester III · Data Structures and Algorithms

beginner25 minAvailable

Linked listDynamic memory · nodes & pointers

Head

Length

3nodes

Lab brief

Objective

Build and manipulate a singly linked list, observing how each node stores a value and a single pointer to the next node.

Theory & concepts

A linked list stores elements in nodes scattered across memory, each node holding a value and a next pointer to the following node. The head marks the first node; the last node's next is null. Inserting at the head or deleting the head is O(1), but finding or inserting at an arbitrary position requires a traversal from the head, O(n) — the opposite trade-off from an array.

Rendering diagram…

Singly linked list with head and next pointers

insertHead(v) → new.next := head; head := new       O(1)
insertEnd(v)  → walk to last; last.next := new       O(n)
search(v)     → walk from head until found / null    O(n)
deleteHead()  → head := head.next                    O(1)
No wasted shifting; extra pointer memory per node.

Prerequisites

Lesson: Arrays and the linked list family
Pointers/next references

Instructions

1Insert at the head and watch the new node appear in front with a fresh next pointer.
2Insert at the end and watch the last node's pointer update.
3Delete the head and confirm the second node becomes the new head.
4Search for a value and follow the traversal highlight node by node.

Tasks

Build a chain
Insert 10, 20, 30 at the head and describe the final order.
Delete head
Delete the head and confirm the new head is correct.
Traverse for search
Search for the last value and count pointer hops.

Self-check

Nodes and next pointers are correct after each operation.
The student states the O(1) head operations and O(n) traversal cost.
Pointer updates during insertion/deletion are explained.

Environment

node viewnext arrowsinsert head/enddeletesearch

Singly Linked List · Data Structures and Algorithms · Learn CSIT