Scribd Logo
Upload

Welcome to Scribd!

  • 17 views

    Fundamental Data Structures

    Uploaded by

    nabila rafique
    The document summarizes several common data structures: stack, queue, linked list, and B-tree. Stack and queue are linear data structures that follow LIFO and FIFO principles respectively. Linked lists use nodes connected by pointers and can be single, double, or circular linked. B-trees are non-linear with properties of being self-balancing and allowing multiple children, keys, and search efficiency. The summary provides the key attributes and operations for each data structure.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Fundamental Data Structures

    Uploaded by

    nabila rafique
    17 views15 pages
    The document summarizes several common data structures: stack, queue, linked list, and B-tree. Stack and queue are linear data structures that follow LIFO and FIFO principles respectively. Linked lists use nodes connected by pointers and can be single, double, or circular linked. B-trees are non-linear with properties of being self-balancing and allowing multiple children, keys, and search efficiency. The summary provides the key attributes and operations for each data structure.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes several common data structures: stack, queue, linked list, and B-tree. Stack and queue are linear data structures that follow LIFO and FIFO principles respectively. Linked lists use nodes connected by pointers and can be single, double, or circular linked. B-trees are non-linear with properties of being self-balancing and allowing multiple children, keys, and search efficiency. The summary provides the key attributes and operations for each data structure.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    17 views15 pages

    Fundamental Data Structures

    Uploaded by

    nabila rafique
    The document summarizes several common data structures: stack, queue, linked list, and B-tree. Stack and queue are linear data structures that follow LIFO and FIFO principles respectively. Linked lists use nodes connected by pointers and can be single, double, or circular linked. B-trees are non-linear with properties of being self-balancing and allowing multiple children, keys, and search efficiency. The summary provides the key attributes and operations for each data structure.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 15

    Elementary Data

    Structures
    Nabila Rafique
    MS220400029

    CS702- Advanced Algorithms Analysis and


    Design
    Points to Cover
    • Stack
    • Queue
    • Link List
    • B-Tree
    Overview
    Stack
    Linear Data Structure

    Last-In-First-Out (LIFO) principle.

    Operations

    Push: Adds an element to the top.


    Pop: Removes the topmost element.
    Top: Retrieves the topmost element without removing.
    Is Empty: Check If the stack have no element.
    Is Full: Check if the stack is full.
    Size: Return the size of stack

    Usage • Function call stack in programming languages.


    • Undo/ Redo functionality .
    Stack
    Linear Data Structure

    Working of Stack

    The video shows all the


    Operations of stack by
    animating data.
    Queue
    Linear Data Structure

    First-In-First-Out (FIFO) principle.

    Operations

    Enqueue: Adds an element to the back of the queue.


    Dequeue: Removes the frontmost element from the queue.
    Peek: Retrieves the frontmost element without removing.
    Is Empty: Check If the queue have no element.
    Is Full: Check if the queue is full.

     Print spooler in operating systems.


    Usage
     Task scheduling in computer science.
     Breadth-first search (BFS) algorithm.
    Queue
    Linear Data Structure

    Working of Queue

    The video shows all the


    Operations of queue by
    animating data.
    Link List
    Linear Data Structure

    Each node contains a value and a reference to next node.

    Insertion: Adds an element to link list.


    • Implement Stack and queue
    Operations

    Deletion: Removes the an element form link list.

    Usage
    • Perform arithmetic operation.
    Traversal: Access each element of link list.
    • Perform polynomial manipulation
    Search: Find a node in link list.
    Sort: Sort the nodes of link list.
    Link List
    Linear Data Structure

    Types of Link List

    Single Link list


    Each node point to next node

    Double Link list


    Each node point to next and previous node

    Circular Link list


    Each node point to next node and last node point
    to first.
    Link List
    Linear Data Structure

    Working of Link List

    The video shows all the


    Operations of Link List
    by animating data.
    B-Tree
    Non-Linear Data Structure

    A Self Balancing m-way tree, maintain sorted data with more than two Childrens and multiple keys at every node.

    B-Tree
    Properties: M=5
    1. Every node has at most m children.
    2. Every non-leaf has at least two children.
    3. Every internal node has at least ⌈m/2⌉ children.
    4. All leaves appear at same level.
    5. A non-leaf node with k children contain k-1 keys.
    B-Tree
    Non-Linear Data Structure

    Operations
    Remember
    Insert: Adds an element to B-tree in ascending order and
    restructure the tree if needed. After Operation the B-Tree
    Delete: Removes an element from B-Tree, rearrange elements in should have its all properties
    ascending order and restructure tree. satisfied
    Search: Search an element from B-Tree.

     File systems and databases for indexing.


    Usage
     Disk-Based data structures.
     Routers and network Switches.
    B-Tree
    Non-Linear Data Structure

    Types of B-Tree

    Data can only be stored on the leaf nodes.


    B+ Leaf nodes are linked together to make the search operations more efficient.

    B*
    Balances more neighboring internal nodes to keep them more densely packed.
    B* This variant ensures non-root nodes are at least 2/3 full instead of 1/2.
    Created to postpone splitting operation as long as they can
    B-Tree
    Non-Linear Data Structure

    Working of B-Tree

    The video shows all the


    Operations of B-Tree by
    animating data.
    Summary
    Data Structure

    POINTS STACK QUEUE LINK LIST B-TREE


    Data Linear Linear Linear Non-Linear
    structure
    Works on LIFO FIFO Nodes BST

    Operations PUSH, POP, TOP, Enqueue, Dequeue, Insertion, Deletion, Insert, Delete,
    SIZE, IS Empty, Is Full Peek, Is Empty, Is Full Traversal, Search, Sort Search

    Types Nill Nill Single, Double, Circular B+, B*

    Usage Undo/ Redo Task Scheduling Polynomial manipulation File systems

    Time O(n) O(n) O(n) O(log n)


    Complexity

    You might also like