What exactly is a data structure?

• A data structure is a way to store, organize, and manage information

-or data- in a way that allows you as the programmer to easily
access or modify the values within them.
• Essentially, it’s a way for us to store a set of related information that
we can then use for our programs.
• Data Structures, and the algorithms used to interact, modify, and
search through them provide the backbone for many of the
programs you’ll end up writing.
• Stack data structure is most suitable to implement redo-undo
feature. This is because the stack is implemented with LIFO(last in
first out) order which is equivalent to redo-undo feature i.e. the last
re-do is undo first.
• To store an image, array data structure is used.
• Social media for contact information: Graph data structure
ABSTRACT DATA TYPE
• Data type of a variable is the set of values that the variable can take. We
have already read the basic data types in C include int, char, float, and
double.
• Abstract The word ‘abstract’ in the context of data structures means
considered apart from the detailed specifications or implementation.
• ADTs are similar to User defined data types which defines operation on
values using functions without specifying function details and how the
operations are performed.
• Stack ADT
• push() – Insert an element at one end of the stack called top.
• pop() – Remove and return the element at the top of the stack, if it
is not empty.
• peek() – Return the element at the top of the stack without
removing it, if the stack is not empty.
• size() – Return the number of elements in the stack.
• isEmpty() – Return true if the stack is empty, otherwise return false.
• isFull() – Return true if the stack is full, otherwise return false.
Queue ADT
• enqueue() – Insert an element at the end of the queue.
• dequeue() – Remove and return the first element of the queue, if
the queue is not empty.
• peek() – Return the element of the queue without removing it, if the
queue is not empty.
• size() – Return the number of elements in the queue.
• isEmpty() – Return true if the queue is empty, otherwise return
false.
• isFull() – Return true if the queue is full, otherwise return false.
Primitive and Non-primitive Data Structures
• Primitive data structures are the fundamental data
types which are supported by a programming
language. Some basic data types are integer, real,
character, and boolean. The terms ‘data type’, ‘basic
data type’, and ‘primitive data type’ are often used
interchangeably.

• Non-primitive data structures are those data

structures which are created using primitive data
structures. Examples of such data structures include
linked lists, stacks, trees, and graphs. Non-primitive
data structures can further be classified into two
categories: linear and non-linear data structures.
Classification of Data Structures
Linear and Non-linear
Structures
•LINEAR DATA STRUCTURE:
• If the elements of a data structure are stored in a linear or sequential
order, then it is a linear data structure.
• Examples include arrays, linked lists, stacks, and queues.
• Linear data structures can be represented in memory in two different
ways.
• One way is to have to a linear relationship between elements by means
of sequential memory locations.
• The other way is to have a linear relationship between elements by
means of links
NON-LINEAR DATA STRUCTURE
• if the elements of a data structure are not stored
in a sequential order, then it is a non-linear data
structure.

• The relationship of adjacency is not maintained

between elements of a non-linear data structure.

• Examples include trees and graphs.

• C supports a variety of data structures.

In a linear data structure, data
elements are arranged in a linear In a non-linear data structure, data
1. order where each and every element elements are attached in hierarchically
is attached to its previous and next manner.
adjacent.
In linear data structure, single level Whereas in non-linear data structure,
2.
is involved. multiple levels are involved.
Its implementation is easy in
While its implementation is complex in
3. comparison to non-linear data
comparison to linear data structure.
structure.
In linear data structure, data While in non-linear data structure, data
4. elements can be traversed in a elements can’t be traversed in a single
single run only. run only.
While in a non-linear data structure,
In a linear data structure, memory is
5. memory is utilized in an efficient way.
not utilized in an efficient way.

Its examples are: array, stack, While its examples are: trees and
6.
queue, linked list, etc. graphs.
Applications of linear data Applications of non-linear data
7. structures are mainly in application structures are in Artificial Intelligence
Static data structure

• In Static data structure the size of the structure is fixed. The content of
the data structure can be modified but without changing the memory
space allocated to it.
Dynamic data structure
• In Dynamic data structure the size of the structure is not
fixed and can be modified during the operations performed
on it. Dynamic data structures are designed to facilitate
change of data structures in the run time.
•
Aspect Static Data Structure Dynamic Data Structure

Memory is allocated at
Memory allocation Memory is allocated at run-time
compile-time

Size is fixed and cannot be Size can be modified during

Size
modified runtime

Memory utilization may be Memory utilization is efficient as

Memory utilization
inefficient memory can be reused

Access time is faster as it is Access time may be slower due

Access
fixed to indexing and pointer usage

Arrays, Stacks, Queues, Trees Lists, Trees (with variable size),

Examples
(with fixed size) Hash tables
operations on Data Structures.
• Data structure operations are the methods used to manipulate the data in a
data structure. The most common data structure operations are:
• Traversal
Traversal operations are used to visit each node in a data structure in a
specific order. This technique is typically employed for printing, searching,
displaying, and reading the data stored in a data structure.
• Insertion
Insertion operations add new data elements to a data structure. You can do
this at the data structure's beginning, middle, or end.
• Deletion
Deletion operations remove data elements from a data structure. These
operations are typically performed on nodes that are no longer needed.
• Search
Search operations are used to find a specific data element in a data
structure. These operations typically employ a compare function to
determine if two data elements are equal.
• Sort
Sort operations are used to arrange the data elements in a data
structure in a specific order. This can be done using various sorting
algorithms, such as insertion sort, bubble sort, merge sort, and quick
sort.
• Merge
Merge operations are used to combine two data structures into one.
This operation is typically used when two data structures need to be
combined into a single structure.
• Copy
Copy operations are used to create a duplicate of a data structure.
This can be done by copying each element in the original data
structure to the new one.