Scribd
Upload
9 views

Lecture 8 LU4 Data Structures

Uploaded by

karabomarope07
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

Lecture 8 LU4 Data Structures

Uploaded by

karabomarope07
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 21

What is a Data structure

• A data structure is a way of organizing and storing data


in a computer so that it can be used efficiently.

• It defines a specific way to represent, store, and access


data, along with operations that can be performed on
that data.

• Data structures are fundamental building blocks in


computer science and programming because they allow
programmers to solve complex problems by efficiently
organizing and manipulating data.
What is a data structure
Data Structure
Why are Data Structures Important

• Efficient Data Storage: Data structures provide efficient


ways to store and organize large volumes of data. They
optimize memory usage and enable fast access to data
elements

• Efficient Data Retrieval and Manipulation: Different data


structures support various operations like insertion, deletion,
search, and traversal efficiently. Choosing the right data
structure allows programmers to perform these operations
quickly, which is crucial for writing efficient algorithms.

• Algorithm Design: Many algorithms rely on specific data


structures to work efficiently. Understanding data structures
helps programmers choose the most appropriate algorithm for
a given problem and optimize its performance.
Why are Data Structures Important

• Code Reusability and Modularity: Data structures promote


code reusability and modularity by encapsulating data and
operations into reusable components. This makes code easier
to maintain, debug, and extend

• Problem Solving: Data structures provide tools and


techniques for solving a wide range of problems in various
domains, such as sorting, searching, graph traversal, and
more. They serve as the foundation for solving complex
computational problems.

• Scalability: As programs grow in complexity and size,


efficient data structures become even more critical. Choosing
the right data structure from the beginning can significantly
impact the scalability and performance of a software system.
Why are Data Structures Important

• Data structures are essential in programming because


they enable efficient storage, retrieval, and manipulation
of data, which are fundamental operations in almost
every software application.

• Understanding data structures allows programmers to


write efficient code, design better algorithms, and solve
complex problems effectively
Generic operation of a non-primitive data
structure

• Searching – We can easily search for any data element


in a data structure.

• Sorting – We can sort the elements either in ascending


or descending order :

• Insertion – We can insert new data elements in the data


structure.

• Deletion – We can delete the data elements from the


data structure.

• Updating – We can update or replace the existing


elements from the data structure.
Structure

• Structures (also called structs) are a way to group several


related variables into one place. Each variable in the structure
is known as a member of the structure.

• Unlike an array, a structure can contain many different data


types (int, float, char, etc.).
Arrays

• C++ provides a data structure, the array, which stores a


fixed-size sequential collection of elements of the same type.

• An array is used to store a collection of data, but it is often


more useful to think of an array as a collection of variables of
the same type
Linked List

• A linked list is a linear data structure consisting of a


sequence of elements called nodes.

• Unlike arrays, linked lists do not have a fixed size, and


memory allocation can be dynamic.

• A linked list is composed of elements known as "Nodes" that


are divided into two parts. The first component is the part
where we store the actual data, and the second is a part
where we store the pointer to the next node. This type of
structure is known as a "singly linked list”.
Linked List

• A singly linked list's structure is illustrated in the diagram below.


Linked List

• As we have seen in the above part, the first node of the linked
list is known as the "head," while the last node is called the
"tail."

• The "head" of a linked list refers to the first node in the list.

• It serves as the starting point or entry point for accessing the


elements of the list.

• The head node contains the data of the first element in the list
and a pointer to the next node (the second element).
Linked List

• The "tail" of a linked list refers to the last node in the list.

• It marks the end of the list and is typically used to identify


where the list terminates.

• The tail node contains the data of the last element in the list
and usually points to nullptr (or NULL in C/C++), indicating
the end of the list
Types of Linked Lists

• Singly Linked List: Each node points to the next node in


the sequence.

• Doubly Linked List: Each node has pointers to both the


next and previous nodes in the sequence.

• Circular Linked List: The last node points back to the first
node, forming a circular structure.
Operations on Linked List

• Insertion: Add a new node at the beginning, end, or middle of


the list.
• Deletion: Remove a node from the list.
• Traversal: Visit each node in the list.
• Searching: Find a specific node based on its value.
• Modification: Update the value of a node.
• Concatenation: Combine two linked lists.
• Reversal: Reverse the order of nodes in the list.
• Merging: Merge two sorted linked lists into one sorted list.
Advantages of Linked List

• Dynamic Memory Allocation: Linked lists can grow or shrink


dynamically during program execution.

• Efficient Insertion and Deletion: Inserting or deleting elements


from a linked list requires adjusting pointers, which can be
done efficiently.

• No Wastage of Memory: Linked lists only use memory


necessary for storing data and pointers.
Disadvantages of Linked List

• Lack of Random Access: Unlike arrays, accessing elements in


a linked list requires traversing from the beginning.

• Extra Memory Overhead: Each node in a linked list requires


additional memory for storing pointers.

• Sequential Access: Traversing a linked list sequentially can be


slower than accessing elements directly in an array.
Linked List
Linked List
QUESTIONS

You might also like