Unit-1 Data Structures
What is Data Structures?
A data structure is a way of organizing and storing data in a computer
so that it can be accessed and used efficiently. It refers to the logical
or mathematical representation of data, as well as the
implementation in a computer program.
Need of Data Structure:
1.As applications are becoming more complex and the amount of
data is increasing every day, which may lead to problems with data
searching, processing speed, multiple requests handling, and many
more.
2. Data Structures support different methods to organize, manage,
and store data efficiently.
3.With the help of Data Structures, we can easily traverse the data
items.
4. Data Structures provide Efficiency, Reusability, and Abstraction.
Advantages of Data Structures:
1. Efficiency: Data structures allow for efficient storage and
retrieval of data, which is important in applications where
performance is critical.
2. Flexibility: Data structures provide a flexible way to organize
and store data, allowing for easy modification and
manipulation.
3. Reusability: Data structures can be used in multiple programs
and applications, reducing the need for redundant code.
4. Maintainability: Well-designed data structures can make
programs easier to understand, modify, and maintain over time
Applications of Data Structures:
1. Databases: Data structures are used to organize and store data
in a database, allowing for efficient retrieval and manipulation.
2. Operating systems: Data structures are used in the design and
implementation of operating systems to manage system
resources, such as memory and files.
3. Computer graphics: Data structures are used to represent
geometric shapes and other graphical elements in computer
graphics applications.
4. Artificial intelligence: Data structures are used to represent
knowledge and information in artificial intelligence systems.
Data structures can be classified into two broad categories:
1)Linear Data Structure:
A data structure in which data elements are arranged sequentially or
linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure.
Examples are array, stack, queue, list etc.
Static data structure: Static data structure has a fixed memory
size. It is easier to access the elements in a static data
structure.
An example of this data structure is an array.
Dynamic data structure: In the dynamic data structure, the size
is not fixed. It can be randomly updated during the runtime
which may be considered efficient concerning the memory
(space) complexity of the code.
Examples of this data structure are queue, stack, etc.
Types of Linear Data Structure:
1] Arrays –
An array is a collection of similar data elements stored at contiguous memory
locations. It is the simplest data structure where each data element can be
accessed directly by only using its index number.
2] Linked List –
A linked list is a linear data structure that is used to maintain a list-like
structure in the computer memory. It is a group of nodes that are not stored at
contiguous locations. Each node of the list is linked to its adjacent node with
the help of pointers.
3] Stack – A Stack is a linear data structure that holds a linear, ordered
sequence of elements. It is an abstract data type. A Stack works on the LIFO
process (Last in First Out), i.e., the element that was inserted last will be
removed first.
4] Queues-
A queue is a linear data structure that stores the elements sequentially. It uses
the FIFO (First in First Out) approach for accessing elements.
2) Non-linear data structure:
Data structures where data elements are not placed sequentially or
linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only.
Examples of non-linear data structures are trees and graphs.
1)Trees:
Tree data structure is a hierarchical structure that is used to
represent and organize data in a way that is easy to navigate and
search.
It is a collection of nodes that are connected by edges and has a
hierarchical relationship between the nodes.
2)Graphs: Consist of nodes (vertices) connected by edges. Graphs
model relationships between objects, like social networks or
transportation systems.
Operations On Data Structure:
1)Traversing:
Traversing a Data Structure means to visit the element stored in it. It visits data
in a systematic manner. This can be done with any type of DS.
2) Searching:
Searching means to find a particular element in the given data-structure. It is
considered as successful when the required element is found. Searching is the
operation which we can performed on data-structures like array, linked-list,
tree, graph, etc.
3) Insertion:
It is the operation which we apply on all the data-structures. Insertion means
to add an element in the given data structure. The operation of insertion is
successful when the required element is added to the required data-structure.
The operation of insertion is successful when the required element is added to
the required data-structure.
4)Deletion:
It is the operation which we apply on all the data-structures. Deletion means to
delete an element in the given data structure. The operation of deletion is
successful when the required element is deleted from the data structure. The
deletion has the same name as a deletion in the data-structure as an array,
Linear Data Structure:
Linked Lists:
A linked list is a linear data structure which can store a collection of
"nodes" connected together via links i.e. pointers.
Linked lists nodes are not stored at a contiguous location, rather they
are linked using pointers to the different memory locations.
A node consists of the data value and a pointer to the address of the
next node within the linked list.
A linked list is a dynamic linear data structure whose memory size can be
allocated or de-allocated at run time based on the operation insertion or
deletion, this helps in using system memory efficiently
. Linked lists can be used to implement various data structures like a
stack, queue, graph, hash maps, etc.
A linked list starts with a head node which points to the first node. Every node
consists of data which holds the actual data (value) associated with the node
and a next pointer which holds the memory address of the next node in the
linked list. The last node is called the tail node in the list which points to null
indicating the end of the list
Types of Linked List:
1) Singly Linked Lists:
Singly linked lists contain two "buckets" in one node; one bucket holds the
data and the other bucket holds the address of the next node of the list.
Traversals can be done in one direction only as there is only a single link
between two nodes of the same list.
2)Circular Linked Lists:
Circular linked lists can exist in both singly linked list and doubly linked list
Since the last node and the first node of the circular linked list are connected,
the traversal in this linked list will go on forever until it is broken.
3)Doubly Linked List:
A doubly linked list is a data structure that consists of a set of nodes,
each of which contains a value and two pointers, one pointing to the
previous node in the list and one pointing to the next node in the list.
This allows for efficient traversal of the list in both directions, making it
suitable for applications where frequent insertions and deletions are
required.
In a data structure, a doubly linked list is represented using nodes that
have three fields:
1. Data
2. A pointer to the next node (next)
3. A pointer to the previous node (Prev)
4)Circular doubly linked list:
Circular doubly linked list is a more complexed type of data structure in
which a node contains pointers to its previous node as well as the next
node.
Circular doubly linked list doesn't contain NULL in any of the node. The
last node of the list contains the address of the first node of the list.
The first node of the list also contains address of the last node in its
previous pointer.
