[go: up one dir, main page]
Scribd
Upload
146 views15 pages

DSA PPT

Uploaded by

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

DSA PPT

Uploaded by

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

Linked Lists

DATA STRUCTURES AND ALGORITHMS


Introduction to Linked Lists
In computer science, a linked list is a linear data
structure where elements are stored in nodes. Each node
points to the next node in the sequence, forming a chain.
Linked lists are fundamental in understanding data
structures and are used in various applications.

2
Representation of Linked Lists
Linked lists are represented using nodes with two fields: data and a pointer
to the next node. The last node points to null, indicating the end of the list.
This structure allows for dynamic memory allocation and efficient insertion
and deletion operations.
Types of Linked
Lists
● Single Linked List
● Doubly Linked List
● Circular Linked List

4
Single Linked List

A singly linked list consists of nodes where each node has a


single pointer to the next node. Traversal is forward-only,
making it efficient for certain operations. However, it does not
support reverse traversal without additional pointers.
Doubly Linked List

In a doubly linked list, each node contains two pointers: one to the next
node and one to the previous node. This facilitates bidirectional traversal,
enabling efficient operations such as insertion and deletion at both ends of
the list.
Circular Linked List

A circular linked list is a variation where the last node points back to the first
node, forming a loop. This structure is useful for applications requiring
continuous data access, such as round-robin scheduling and circular buffers.
It is of two types:
->Circular Singly Linked List
->Circular Doubly Linked List
Applications of Linked Lists
● Applications that have an MRU list ( a linked list of file
names)

● The cache in the browser that allows you to hit the BACK
button ( a linked list of URLs)

● Undo functionality in Photoshop or Word ( a linked list of


state)

● A stack, hash table, and binary tree can be implemented


using a
8
Doubly linked list.
Trees
DATA STRUCTURES AND ALGORITHMS
Introduction to Trees
● The Tree is a Non-Linear data structure that consists
of nodes and is connected by edges.
● The Tree data structure allows easier and quicker
access to the data element.
● They model relationships between data entities in a
parent-child fashion, allowing efficient data
retrieval, insertion, and deletion.

10
Tree
Terminologies
● Node : Fundamental unit of a tree that holds
data.
● Root : The topmost node in a tree, from which all
other nodes descend.
● Parent : A node that has child nodes connected
below it.
● Child : Nodes directly connected to another
node when moving away from the root.
● Leaf (External Node) : A node that has no
children.
● Internal Node : A node that has at least one
child.
● Depth : The level of a node in the tree relative to ● Subtree : A tree formed by a node
the root. Root has depth 0. and all its descendants.
● Height : The maximum depth of any node in the
11
tree.
Representation of Trees
● Array Representation :
.->Parent and child relationships are
defined by index calculations.
->Efficient for complete binary trees..

● Linked Representation :
->Each node stores data and
pointers/references to its children.
->Suitable for dynamic allocation
of memory and flexible tree structures.
Tree Traversals
● Depth-First Traversals :

Preorder Traversal:
Visit the root node first.
Recursively visit the left subtree.
Recursively visit the right subtree.

Inorder Traversal:
Recursively visit the left subtree.
Visit the root node. ● Breadth-First Traversal (Level-
Recursively visit the right subtree.
Order):
Postorder Traversal: Visit nodes level by level from left to
Recursively visit the left subtree. right.
Recursively visit the right subtree. Uses a queue to maintain the current
Visit the root node last. level of nodes.
Applications of Trees
1. Binary Search Trees (BST):
Efficient for searching, insertion, and deletion operations.
Used in databases, symbol tables, and dynamic sets.
2. Expression Trees:
Represent mathematical expressions for evaluation.
Used in compilers, calculators, and symbolic algebra.
3. Trie (Prefix Tree):
Store and retrieve strings efficiently.
Used in autocomplete features and dictionary implementations.
4. Huffman Trees:
Data compression through Huffman coding.
Used in file compression algorithms (e.g., ZIP files).
5. Decision Trees:
Represent decisions and their consequences.
Used in decision-making processes and
14 machine learning
algorithms.
ThankYou
Do you have any questions?
Tejaswi Pannala

CREDITS: This presentation template was created by


Slidesgo, and includes icons by Flaticon, and infographics
& images by Freepik

You might also like