CO2402 Advanced Programming with C++ Lecture 10 Notes

CO2402: Advanced Programming
with C++ Lecture 10


Introduction to Linked Lists

1. Overview

o A linked list is a data structure consisting of a sequence of
elements, each containing a reference (link) to the next
element in the sequence. This structure allows efficient
insertion and removal of elements.

Consider a system to record student marks where each student
has a varying number of modules. A linked list can dynamically
manage the memory required for storing module data.

2. Types of Linked Lists

o Singly Linked List: Each element points to the next one,
forming a unidirectional chain.

o Doubly Linked List: Each element has pointers to both the
next and previous elements.

o Other Variants: Queue, dequeue, etc.




Why Program Your Own Linked List?

 Understanding the underlying data structure helps in grasping more
complex structures like trees and graphs. Implementing a linked list
also helps in appreciating the importance of memory management
and pointer operations.

, The Element Class

1. Class Definition

o The CElement class represents an element in the linked list. It
contains data and a pointer to the next element.

Example:




2. Methods

o Constructor: Initializes the element with data.

o getData(): Returns the data stored in the element.

o getNext(): Returns the pointer to the next element.

o setNext(): Sets the pointer to the next element.

Example: