Scribd Logo
Upload

Welcome to Scribd!

  • 21 views

    L2 18 and 19 Mar Sequences

    Uploaded by

    Punnag Choudhury
    The document discusses data structures and their uses. It defines what a data structure is, focusing on arrays and linked lists. It provides examples of common operations for each, including their time complexities, and compares their static and dynamic capabilities.

    Copyright:

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

    L2 18 and 19 Mar Sequences

    Uploaded by

    Punnag Choudhury
    21 views57 pages
    The document discusses data structures and their uses. It defines what a data structure is, focusing on arrays and linked lists. It provides examples of common operations for each, including their time complexities, and compares their static and dynamic capabilities.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses data structures and their uses. It defines what a data structure is, focusing on arrays and linked lists. It provides examples of common operations for each, including their time complexities, and compares their static and dynamic capabilities.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    21 views57 pages

    L2 18 and 19 Mar Sequences

    Uploaded by

    Punnag Choudhury
    The document discusses data structures and their uses. It defines what a data structure is, focusing on arrays and linked lists. It provides examples of common operations for each, including their time complexities, and compares their static and dynamic capabilities.

    Copyright:

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

    Structuring DATA

    FM131 Programming and Data Structures


    18 MAR 2024
    Logistics
    How are you ?
    Pressure ?

    Questions – Complexity?

    Lab assignment problems

    Project – Feedback (next week)


    What’s a data structure ?
    Why Data ?
    Q: Data is important?

    Ans: Its our memory, and the need for evolution!


    Why Structure ?
    Q: Data is important so how do we keep it ?

    Ans: We find a way in which we can store data and find it


    when required!
    Why Structure ?
    What is a data Structure ?
    We have a numerous types of data and we can define storage of data in several ways.

    We can perform numerous types of operations based on how we store it.

    Interfaces (WHAT) Implementation (HOW)


    - ADT - Data Structure
    What is a data Structure ?
    ADT (Abstract Data Types)

    A sequence of elements to which we can

    1. add elements anywhere


    2. remove element from anywhere
    3. get an element in sequence / iterate the sequence
    4. Find the length
    What is a data Structure ?
    ADT (Abstract Data Types) Data Structures

    A sequence of elements to which we can arrays

    1. add elements anywhere


    2. remove element from anywhere
    3. get an element in sequence / iterate the sequence
    4. Find the length
    What is a data Structure ?
    ADT (Abstract Data Types) Data Structures

    SETS or SEQUENCES arrays


    pointer based lists
    .
    .
    .
    .
    .
    Arrays
    Arrays
    STATIC ARRAYS
    Arrays
    STATIC ARRAYS
    Arrays
    STATIC ARRAYS
    Arrays

    Word RAM
    Think 1 mins – (NO TALKING)

    You create an array of integers (assume each integer is exactly 4 bytes) in


    memory, and the beginning of the array (i.e., the start of the very first cell of
    the array) happens to be at memory address 1000 (in decimal, not binary).

    What is the memory address of the start of cell 6 of the array, assuming 0-
    based indexing (i.e., cell 0 is the first cell of the array)?
    Take a vote

    1. 1004

    2. 1023

    3. 1024

    4. None
    Answer

    1. 1004

    2. 1023

    3. 1024

    4. None
    Arrays as static sequences
    STATIC ARRAYS

    A sequence of elements to which we can

    1. add elements

    2. remove element

    3. get an element in sequence / iterate the sequence

    4. Find the length


    Arrays as static sequences
    STATIC ARRAYS

    A sequence of elements to which we can

    1. add elements

    2. remove element

    3. get an element in sequence / iterate the sequence

    4. Find the length


    Arrays as static sequences
    STATIC ARRAYS

    A sequence of elements to which we can

    1. add elements

    2. remove element

    3. get an element in sequence / iterate the sequence

    4. Find the length


    Arrays as dynamic sequences
    A sequence of elements to which we can
    1. add elements anywhere
    2. remove element from any anywhere
    Arrays as dynamic
    sequences
    A sequence of elements to which we can
    1. add elements anywhere
    Arrays as dynamic
    sequences
    A sequence of elements to which we can
    1. add elements anywhere
    Think 2 mins – (NO TALKING)

    What is the worst-case time complexity for an "insert" operation in an


    arbitrary Array List (i.e., we know nothing about the elements it contains)?

    What is the worst-case time complexity for a "find" operation in an


    arbitrary Array List (i.e., we are searching for a given element and we know
    nothing about the elements the Array List already contains)?
    Take a vote

    1. O(1), O(n)

    2. O(1), O(1)

    3. O(n ),
    2 O(n)

    4. O(n), O(n)
    Solution

    1. O(1), O(n)

    2. O(1), O(1)

    3. O(n ),
    2 O(n)

    4. O(n), O(n)
    Arrays as dynamic
    sequences
    A sequence of elements to which we can
    1. add elements anywhere
    2. remove element from any anywhere
    Think 2 mins – (NO TALKING)

    You are given an Array List with 100 elements, and you want to remove the
    element at index 7 (0-based indexing). How many "left-shift" operations will
    you have to perform on the backing array?
    Take a vote

    1. 372

    2. 92

    3. 93

    4. 368
    Dynamic Sequence
    ADT (Abstract Data Types)

    A sequence of elements to which we can

    1. add elements anywhere


    2. remove element from anywhere
    3. get an element in sequence / iterate the sequence
    4. Find the length
    Dynamic Sequence
    ADT (Abstract Data Types)

    A sequence of elements to which we can

    1. add elements anywhere


    2. remove element from anywhere
    3. get an element in sequence / iterate the sequence
    4. Find the length
    Linked Lists
    Linked Lists
    Linked List, which was developed in 1955 by Allen Newell, Cliff Shaw, and Herbert A. Simon at RAND
    Corporation. The Linked List is a dynamically-allocated data structures, meaning it grows dynamically in
    memory on its own very time-efficiently (as opposed to an Array List, for which we needed to explicitly
    reallocate memory as the backing array fills, which is a very time-costly operation).

    Allen Newell (right) and Herbert Simon (left) (courtesy of Carnegie Mellon University)
    Linked Lists
    Linked Lists
    Think 2 mins – (NO TALKING)

    If I only have direct access to the head or tail pointer in a Linked List, and I
    can only access the other elements by following the nodes' pointers, what is
    worst-case time complexity of finding an element in a Linked
    List with n elements?
    Take a vote

    1. O (n)

    2. O (1)

    3. O (n )
    2

    4. Do not know
    Solution

    1. O (n)

    2. O (1)

    3. O (n )
    2

    4. Do not know
    Linked Lists
    Think 3 mins – (No TALKING)
    Write a function that starts at the
    given node and returns true if the
    element exists somewhere in
    the Linked List, otherwise false if the
    element does not exist in the Linked
    List.

    You may choose to implement it


    either iteratively or recursively: we will
    pass in the head node when we call
    your find function, so both
    approaches have equally valid
    solutions.
    Pair 2 mins – (TALKING)
    Write a function that starts at the
    given node and returns true if the
    element exists somewhere in
    the Linked List, otherwise false if the
    element does not exist in the Linked
    List.

    You may choose to implement it


    either iteratively or recursively: we will
    pass in the head node when we call
    your find function, so both
    approaches have equally valid
    solutions.
    Share 2 mins – (TALKING)
    Write a function that starts at the
    given node and returns true if the
    element exists somewhere in
    the Linked List, otherwise false if the
    element does not exist in the Linked
    List.

    You may choose to implement it


    either iteratively or recursively: we will
    pass in the head node when we call
    your find function, so both
    approaches have equally valid
    solutions.
    Solution
    Linked Lists
    Think 3 mins – (No TALKING)
    Write a function that
    inserts newnode into index index of
    the Linked List. We guarantee that we
    will not have you insert at the very
    beginning nor the very end of the
    Linked List (so you won't need to
    worry about updating the head or tail
    pointers of the Linked List).
    Pair 2 mins – (TALKING)
    Write a function that
    inserts newnode into index index of
    the Linked List. We guarantee that we
    will not have you insert at the very
    beginning nor the very end of the
    Linked List (so you won't need to
    worry about updating the head or tail
    pointers of the Linked List).
    Share 2 mins – (TALKING)
    Write a function that
    inserts newnode into index index of
    the Linked List. We guarantee that we
    will not have you insert at the very
    beginning nor the very end of the
    Linked List (so you won't need to
    worry about updating the head or tail
    pointers of the Linked List).
    Solution
    Summary Operation O( )
    Static Dynamic Dynamic Dynamic

    Get At() Insert First () Insert last () Insert at ()


    Set At() Delete First () Delete last () Delete at ()

    Array

    Linked List
    Summary Operation O( )
    Static Dynamic Dynamic Dynamic

    Get At() Insert First () Insert last () Insert at ()


    Set At() Delete First () Delete last () Delete at ()

    Array
    1 n n n

    Linked List
    n 1 n n
    Thank you.

    You might also like