Unit 2 of 4 · BCA Sem 2

Unit 2: Linked lists

Data Structures-I notes · PTU syllabus (UGCC2506)

3 min read5 topics10 exam questions
On this page
  1. Unit summary
  2. Linked list and comparison with arrays
  3. Representation in memory
  4. Singly linked list operations
  5. Doubly and circular linked lists
  6. Applications of linked lists
  7. Key terms
  8. Quick revision
  9. Important questions

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
1

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.

ComparisonArray vs linked list
Array
Linked list

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

2

Topic 2

Representation in memory

GraphA singly linked list: each node holds data and the address of the next node
10next20next30nextSTARTNULL

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).

3

Topic 3

Singly linked list operations

  • Traversal: start with ptr = start; while ptr != NULL, process ptr->data and move ptr = ptr->next.
  • Search: traverse and compare each node's data with the item: O(n).
ProcessInserting a node at the beginning
  1. 1Create a new node

    newnode = malloc(...)

  2. 2Store data

    newnode->data = item

  3. 3Link to old first node

    newnode->next = start

  4. 4Move START

    start = newnode

  • Insert at end: traverse to the last node and set last->next = newnode, with newnode->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; then free(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.

4

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.
ComparisonTypes of linked list
Pointers per node
Main advantage

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.

5

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

  1. Q1.Define a linked list.
  2. Q2.Give two advantages of linked lists over arrays.
  3. Q3.What is a NULL pointer in a linked list?
  4. Q4.Differentiate between singly and doubly linked lists.
  5. Q5.What is a circular linked list?
  6. Q6.List two applications of linked lists.

Long-answer questions

  1. Q1.Compare arrays and linked lists in detail.
  2. Q2.Write algorithms to insert a node at the beginning, at the end and after a given node of a singly linked list.
  3. Q3.Explain deletion of a node from a doubly linked list with a diagram.
  4. 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.

WhatsApp us