Unit 2: Linked Lists

Singly, doubly and circular lists

Learning Outcomes
  • Explain the node and pointer model
  • Implement singly, doubly and circular linked lists
  • Insert and delete nodes at any position
  • Compare linked lists with arrays

Singly Linked List

Each node stores a data value and a pointer to the next node, and the list is reached through a head pointer. Insertion at the head is O(1), but searching for a value is O(n) because nodes must be visited in sequence.

struct Node { int data; Node* next; }; Node* head = nullptr;

Doubly and Circular Lists

A doubly linked list adds a previous pointer so the list can be traversed in both directions, while a circular list links the last node back to the first, which is useful for round-robin processing.

struct DNode { int data; DNode* prev; DNode* next; };

Operations and Trade-offs

Given a reference to a node, linked lists support O(1) insertion and deletion and grow dynamically, but they give up O(1) random access and use extra memory for the pointers.

// insert a new node at the head Node* n = new Node{value, head}; head = n;

Summary

This unit covered the pointer based linked list family, their core operations, and the trade-offs that make them preferable to arrays when frequent insertion and deletion are required.

Exercises

  • Implement insertion at the beginning and end of a singly linked list.
  • Write a function to reverse a singly linked list.
  • Detect whether a linked list contains a cycle.
  • Compare arrays and linked lists across access, insertion and memory.
← PreviousCourse HomeNext →