Data Structure in C++ – Class 12 Computer Science Notes
Chapter 8 - Data Structures in C++
Contents
Introduction
A computer program works with data. For example, a student record may contain a name, roll number, marks and address. When a program has to store and process a large amount of data, simply storing the data is not enough. The data should be arranged in a suitable way so that it can be accessed and processed easily.
The way in which data is organized and stored in a computer is called a data structure.
Data structures are an important part of programming because they help us store data efficiently and perform operations such as insertion, deletion, searching and sorting.
What is Data?
Data means raw facts or values that can be processed by a computer.
For example:
- 25
- 45.5
- “Rahul”
- A
- 2026
These values by themselves may not give complete information. After processing, data can become meaningful information.
Example
Suppose the marks of a student are:
75, 82, 68, 91
These are data. If we calculate the total and average marks, the result gives useful information.
What is a Data Type?
A data type tells the computer what kind of value a variable can store.
For example, an integer variable stores whole numbers, while a character variable stores a single character
Common C++ Data Types
Data Type | Purpose | Example |
int | Stores whole numbers | int age = 18; |
float | Stores decimal numbers | float price = 25.5; |
double | Stores larger decimal values | double salary = 45678.50; |
char | Stores a single character | char grade = ‘A’; |
bool | Stores true or false | bool pass = true; |
Syntax
data_type variable_name;
Example
int marks;
float percentage;
char grade;
bool result;
Types of Data Types in C++
C++ data types can broadly be divided into:
- Primitive data types
- Non-primitive data types
Primitive Data Types
Primitive data types are the basic data types provided by the programming language. They are used to store a single value.
Some commonly used primitive data types in C++ are:
- int
- char
- float
- double
- bool
Example
int age = 18;
char grade = ‘A’;
float percentage = 85.5;
bool passed = true;
Here, each variable stores a single value.
Non-Primitive Data Types
Non-primitive data types are formed using primitive data types. They are generally used to store a collection of values or more complex data.
Examples include:
- Arrays
- Structures
- Classes
- Linked lists
- Stacks
- Queues
- Trees
For example, an array can store the marks of many students instead of using a separate variable for every student.
int marks[5] = {75, 82, 68, 91, 88};
What is a Data Structure?
A data structure is a particular way of organizing and storing data in a computer so that the data can be accessed and processed efficiently.
In simple words:
A data structure is a method of arranging data in a program so that it can be used efficiently.
For example, if we want to store the marks of 50 students, using an array is more convenient than creating 50 separate variables.
int marks[50];
Need for Data Structures
Data structures are useful when a program has to deal with a large amount of data.
They help in:
- Storing data in an organized manner
- Accessing data easily
- Searching for data
- Inserting new data
- Deleting existing data
- Sorting data
- Managing memory efficiently
- Making programs easier to design and maintain
Choosing a suitable data structure can make a program faster and more efficient.
Classification of Data Structures
Data structures can be classified in different ways.
A simple classification is:
Data Structures
→ Simple
→ Compound
Compound data structures can further be classified as:
→ Linear
→ Non-linear
Simple Data Structure
A simple data structure generally deals with a single value.
Examples include:
- Integer
- Character
- Float
- Double
- Boolean
Example
int age = 18;
Here, age stores only one integer value.
Compound Data Structure
A compound data structure is formed by combining multiple data elements.
Examples include:
- Array
- Structure
- Stack
- Queue
- Linked List
- Tree
For example:
int marks[5] = {75, 82, 68, 91, 88};
The array contains five values and therefore can be used to store a collection of related data
Linear Data Structure
In a linear data structure, elements are arranged sequentially, one after another.
Each element generally has a predecessor and/or successor, except the first and last elements.
Examples:
- Array
- Stack
- Queue
- Linked List
Simple representation
10 → 20 → 30 → 40 → 50
The elements are arranged in a sequence.
Non-Linear Data Structure
In a non-linear data structure, elements are not arranged in a single sequence. An element may be connected to more than one other element.
Examples:
- Tree
- Graph.
Array
An array is a collection of elements of the same data type stored under one name.
The elements of an array are stored in consecutive memory locations and are accessed using an index.
Syntax
data_type array_name[size];
Example
int marks[5];
This creates an integer array capable of storing five values.
Structure
A structure is a user-defined data type that allows us to group different types of data under one name.
For example, information about a student may contain:
- Roll number – integer
- Name – string
- Marks – float
These different types of data can be grouped using a structure.
Syntax
struct structure_name
{
data_type member1;
data_type member2;
data_type member3;
};
Example
struct Student
{
int roll;
char name[30];
float marks;
};
Stack
A stack is a linear data structure in which insertion and deletion take place from the same end, called the top.
A stack follows the principle:
LIFO – Last In, First Out
This means the element inserted last is removed first.
Real-life example
Think about a stack of plates. If several plates are placed one above another, the plate placed last on the top is normally removed first.
Queue
A queue is a linear data structure in which insertion and deletion take place at different ends.
A queue follows:
FIFO – First In, First Out
The element inserted first is removed first.
Real-life example
Consider a queue of students waiting at a counter. The student who arrives first is normally served first.
Linked List
A linked list is a linear data structure in which elements are stored in separate nodes. The nodes are connected using pointers.
Unlike an array, the elements of a linked list do not have to occupy consecutive memory locations.
Each node generally contains:
- Data
- A pointer to the next node
Basic structure of a node
struct Node
{
int data;
Node *next;
};
Here:
- data stores the value.
- next stores the address of the next node.
Tree
A tree is a non-linear data structure in which data elements are arranged in a hierarchical manner.
A tree consists of nodes connected by edges.
Trees are commonly used to represent hierarchical information.
Examples include:
- File and folder systems
- Organization structures
- Family trees
- Searching and sorting applications
Graph
A graph is another important non-linear data structure. It consists of a collection of vertices (or nodes) connected by edges.
For example:
Graphs can be used to represent:
- Road networks
- Computer networks
- Social networks
- Connections between web pages
Common Operations on Data Structures
Different data structures support different operations. Some commonly performed operations are:
Traversal
Visiting each element of a data structure one by one.
Insertion
Adding a new element.
Deletion
Removing an existing element.
Searching
Finding a particular element.
Sorting
Arranging elements in a particular order, such as ascending or descending order.
Updating
Changing the value of an existing element
Quick Revision
Data
Raw facts and values that can be processed by a computer.
Data Type
Specifies the type of value that a variable can store.
Data Structure
A method of organizing and storing data so that it can be accessed and processed efficiently.
Primitive Data Structure
Deals with basic values such as integers, characters and floating-point numbers.
Non-Primitive Data Structure
Used to organize collections of data or more complex data.
Linear Data Structure
Elements are arranged sequentially.
Examples: Array, Stack, Queue, Linked List.
Non-Linear Data Structure
Elements are not arranged in a single sequence.
Examples: Tree, Graph.
Array
Collection of elements of the same data type stored under one name.
Structure
User-defined data type that groups different types of data under one name.
Stack
Linear data structure that follows LIFO.
Queue
Linear data structure that follows FIFO.
Linked List
Collection of nodes connected using pointers.
Tree
Non-linear data structure used to represent hierarchical data.
Graph
Non-linear data structure consisting of vertices and edges.
Important Points for Examination
- A data structure is used to organize and store data efficiently.
- Arrays store elements of the same data type.
- Array indexing starts from 0 in C++.
- A structure can contain members of different data types.
- A stack follows LIFO (Last In, First Out).
- Push inserts an element into a stack.
- Pop removes an element from a stack.
- A queue follows FIFO (First In, First Out).
- Enqueue inserts an element into a queue.
- Dequeue removes an element from a queue.
- A linked list consists of nodes connected using pointers.
- A tree is a non-linear and hierarchical data structure.
- A graph consists of vertices and edges.
- Arrays, stacks, queues and linked lists are examples of linear data structures.
Trees and graphs are examples of non-linear data structures