Data Structures

Presented By: [Link] Zahid

Lecturer CS APC(G)
 Introduction to Data Structures

• Data structures are ways of organizing and storing data.

• They help in efficient access and modification of data.
• Determines efficiency of operations like insertion, deletion,
searching, and retrieval.
• Examples: Arrays, Stacks, Queues, Linked Lists, Graphs, Trees.
• Use Case:
• Banking systems use queues for customer service.
Why Data Structures
are Important?
• Provide efficient ways to manage large amounts of data.
• Improve algorithm performance.
• Affect time complexity of operations.
• Dictate how data is arranged in memory.
Example:
• Array vs Linked List for insertion:
– Array requires shifting elements → costly.
– Linked list only changes pointers → efficient.
 Arrays
• Simplest data structure.
• An array stores elements of the same type in contiguous memory.
• Access: Elements accessed using index (fast lookup).
• Insertion: Adding new element may require shifting.
• Deletion: Removing element also requires shifting.
• Advantages:
– Fast access ,Efficient memory use
• Limitations:
– Fixed size, Resizing is costly., Cannot store heterogeneous data.
Arrays
Array

Not Array

Array
 1-D Arrays

One-Dimensional Array (1-D):

• Stores elements in a single
list.
• Accessed using single index.
• Used for storing student
marks, salaries, product
prices.
 2-D Arrays

Two-Dimensional Array (2-D)

• Also called matrix or table.
• Access requires row and
column indices.
• Use Cases:
– Storing images (pixel grid).
– Seating arrangements in
halls.
 Linked List

• A linked list is a collection of nodes.

• Each node = data + pointer.
• Pointer stores the address of next node.
• Capable to store different types of data
• Dynamic in size(they can grow and shrink as
required)
 Linked List

• Operations:
– Insertion: Add node by
updating pointers.
– Deletion: Remove node by
adjusting pointers.
– Traversal: Accessing each
node one by one.
• Use Cases:
– Music playlists.
– Navigation systems
(previous/next locations).
– Undo/Redo operations.
 Linked List
Singly Linked List: (regular linked list)
• Each node has:
– Data
– Pointer to next node.
• Last node points to NULL.
• Use Case:
– Maintaining a to-do list where tasks are
added/removed.
 Linked List
Doubly Linked List:
• Each node has 3 parts:
– Data
– Pointer to next node
– Pointer to previous node
• Traversal in both directions.
• Use Case:
– Browser history navigation (back & forward
buttons).
– Train bogies attached in both directions.
Linked List
 Linked List
Circular Linked List:
• Last node points to first node.
• Forms a loop.
• Use Case:
– Multiplayer games (players take turns
in a circle).
 Linked List
• Singly Circular LL:

• Doubly Circular LL:

 Stack
• A stack follows Last In First Out (LIFO)/First In Last Out (FILO).
• important for understanding algorithms that need to manage
tasks in a specific order
• memory efficient
• size of the stack could be fixed or dynamic
• Operations:
– Push: Add a new element at the top of stack.
– Pop: Remove existing element from the top of stack.
– Top: Return the top element without removing it.
– IsEmpty: Check, if stack is empty.
– IsFull: Check, if stack is full.
• Use Case:
– Expression evaluation (infix → postfix).
Stack
 Queues
• A queue follows First In First Out (FIFO).
• useful for managing tasks that need to be
processed in the order they arrive
• Unlike stack, the operations on queues occur
at two ends
• Use Case:
– Printer Jobs
– Ticket counters & customer service
– CPU Task scheduling
 Queues

• Operations:
– Enqueue: Add a new element at
the end (back/tail/rear) of the
queue.
– Dequeue: Remove existing
element at the start (front/head)
of the queue.
– Front: Return the start element
without removing it.
– IsEmpty: Check if the queue is
empty.
– IsFull: Check if the queue is full.
 Graphs
• A graph consists of nodes (vertices) and edges.
• Can represent complex relationships and networks (social, transport, etc.)
• They are essential for algorithms related to network analysis, shortest paths
(e.g., Dijkstra's algorithm)
• Operations:
– Add Vertex: Add a new node to the graph.
– Add Edge: Create connection between two nodes.
– Remove Vertex/Edge: Delete node or edge from the graph.
– Traversal: Visiting graph in specific order. (Depth First Search (DFS),
Breadth First Search (BFS))
 Graphs
• Use Cases of Graphs
– Social Networks: Friends, followers,
connections.
– Maps & Navigation: Finding shortest paths.
– Resource Management: Project task
dependencies.
– Internet: Hyperlinks between web pages
 Types of Graphs
Connected Graph Directed Graph
• At least one path exists • Edges have directions
between every pair of associated with them.
nodes. • Example: Twitter follow
• Example: Road map of a system (A → B).
city.
 Types of Graphs
Connected Graph Directed Graph
 Trees
• A tree is a hierarchical structure with root and children
nodes.
• Root: Top most node
• Directly connected nodes make a relationship of parent-
child.
• Leaf node: node with no child
• Edge: Line that represents relationships between nodes
• Node = value + pointer to its child
• Binary Tree: Each node has at most 2 children.
Trees
 Trees
• Operations:
– Insertion: Add a new node at specified location in the tree.
– Deletion: Remove existing node
– Search: Find specific node in a tree
– Traversal: Visiting tree in a specific order. (In-order, Post-order,
Pre-order)
 Trees
• In-order traversal: Left-Root-Right
 Trees
• Pre-order traversal: Root-Left-Right
 Trees
• Post-order traversal: Left-Right-Root
 Comparison
Structure Principle Advantages Use case
Array Indexed Storage Fast Access, Simple Student marks,
images
Linked List Nodes with pointers Dynamic size, easy Playlist, undo/redo
insertion
Stack LIFO/FILO Memory efficient, Recursion, undo
easy to manage
Queue FIFO/LILO Fair processing Customer service,
order CPU scheduling
Graph Vertices + Edges Represents complex Social networks,
networks maps
Trees Hierarchical Fast searching, File systems,
structure sorting, flexible databases,
(parent → child) hierarchy organizational
charts
 How Data Structures Support
Computational Thinking:
Problem Decomposition:
• Help break problems into manageable components.
• Simplify the design and implementation of algorithms.
Efficiency Considerations:
• Illustrate trade-offs between different operations (e.g., access time vs.
insertion time).
• Guide the choice of the most appropriate structure for a problem.
Algorithmic Thinking:
• Aid in developing and analyzing algorithms.
• Improve problem-solving skills by selecting the right data structure.
Key Takeaway:
• Data structures are not just tools for storing data, they shape the way we
approach problem-solving and algorithm design.
• Mastery of these concepts is crucial for developing efficient algorithm.