[DSA] - Basic ADT (Arrays, Linked List, Stack)

Abstract Data Type (ADT)

• Human - Interface - ADT
• List

1. With Order
2. List ADT Operations:
   (1) Check if the list is empty
   (2) Insert the element front/back or any other position
   (3) Remove element from any position
   (4) Read and Modify an element at a position
   (5) Search list for an element

Core Data Structure

• Primitive
• Structures
• Arrays
• Linked List
• Trees
• Graphs

ADT

• To create an "ADT", you have to have a clear interface and a good implementation
• A clear interface means that the clients know exactly what they can do with it.
• ADT is implemented with Core Data Structures

Core Data Structures

• Primitives, Structures, Arrays, Linked Lists, Trees, Graphs
• Integers, Node

List ADT

Core DS - Arrays

• Contains fixed elements that have the same type.

    int my_array[4] = {2, 5, 7, 8};

• Cannot extend the length/positon if you want:
  As you cannot guarantee your program is not using those bytes of memory for something else.
• The solution is to apply for another block of memory that can fit your new data.
• Then, copy what you have from the old array into the new array. And, telling your program that you don't need that old block for data anymore.
• A.K.A: Freeing the memory.

Dynamic Arrays

• With Array Doubling, Time Complexity could be reduced to O(1)
• Original Time Complexity: O(n)

Using Huge Array

• We have enough space for any future elements inserted.

    int my_arrray[10000];

• Run the ADT Operation

1. Insert element: Insert Back
2. If insert-front is needed, you need to move the inserted elements, then insert the new element.

Linked List Implementation

• Composed of multiple nodes, each node contains a value.
• Pointer is an Address that point to the block of memory.
• The block of memory containing an entity.
• An entity is a node.

Node (Entity)

    struct Node {
        int value;
        struct Node* next;
        }

Linked List = (Nodes(Value+Pointer))

• Struct: Build a Data Structure called Node, that contains two attributes
• Think of Struct as a kind of container of multiple attributes
• Attribute also called as Member Variable or Member Fields
• Our Node Structure contains attributes which are Value and Pointer
• The Node structure could be used to make Trees and Graphs

Linked List

• C code

    struct LinkedList {
        struct Node* head;
        }
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();
    
    head -> value = 1;
    second -> value = 2;
    third -> value = 3;

    head -> next = second;
    second -> next = third;

• Python code

    class Node:
        def __init__(self, value=0, next=None):
            self.value = value
            self.next = next

Unlike arrays, we don't reserve multiple slots of contiguous memory for our linked lists.
So, the nodes are not arranged sequentially in memory.
Since we implemented Nodes to point memory address, we could save lots of time.

• Arrays:

1. In the array, the size of data format is fixed, we could access specific index quickly.
2. Thus, the Time Complexity is O(1).

• Linked List:

1. In Linked List, there is no way knowing what the address of the third node is,
   all we got is the information of the Head Node.
2. To get the third element of Linked List, you must traverse form the head of the list.
3. We have to follow up the nodes, one-by-one all the way to the third element.
4. Thus, the Time Complexity is O(n) (In Search/Get).
5. In Insert/Remove process, the time complexity is O(1).

Advantages of Linked Lists

• The Length can easily change, and does not need to know in advanced
• The linked lists could Dynamically allocate each node.
• On the other hand, Arrays need to be allocated with some fixed amount of memory
• When Remove/Add element at front is needed, the operation can be done in constant time O(1) and constant space O(1).
• When find an element in Linked Lists, if there is a variable pointed to the tail of list, the time comlexity is O(1). Otherwise, the time complexity is O(n).
• However, when Remove/Add element at front in Arrays, the time complexity is O(n).

pseudo code

• Get Item in Linked List: O(n)

    function getItem (head, n) {
        count = 0
        current = head
        while current is not NULL:
            if current == n
                return value  // return value of nth element
             current = current.next
        handle errors
        }

• Search Item in Linked List: O(n)

    function Search (head, x) {
        current = head
        while current is not NULL
            if current == x
                return true
            current = current.next
        return false 
        }

• Inset an element at the front: O(1)

   function insertFront (head, x) {
        Make newNode with x as the value
        newNode.next = head
        Assign the new node as the head
       } 

• Remove an element by value: O(n)

    function remove (head, x) {
        current = head
        if current.value == x
            head = current.next
            free current
            return

        while current is not NULL
            if current.value == x
                break
            previous = current
            current = current.next

        if current is NULL
            return
        previous.next = curent.next
        free current
        }

• Focus on Length

1. Return Length: O(n)

    struct LinkedList {
        Node* head;
        }

2. Return Length: O(1), get the help with Node* tail

    struct LinkedList {
        Node* head;
        Node* tail;
        int length;
        }

Stack ADT (LIFO)

Push/Pop

• Two ways to implement Stack ADT: Array and Linked List
• Pros & Cons of implementing the Stack ADT

1. Stack is a list of elements, just like the List ADT

• Initializing a Stack
  stack = new Stack
• Push/Pop
• Function: push(), pop(), top(), isempty()

• It's not possible to pop the First Element.
  If you want to pop off the first element, you have to pop off All elements which on top of it

Stacks' different Implementations and its pros and cons

• Fixed Array
  C code

    struct stack {
        int items[];
        int top;
        int maxsize = 10;
        }

psudo code: Pushing new element

• Check if the Stack is full

    stack = new Stack
    function push (stk, x) {
        if stk.top == stk.maxsize 
           overflow error handling
        else
            stk.items[top] = x
            stk.top = stk.top + 1
        }

psudo code: Pop off elements

• Check if the stack is empty

    function pop(stk) {
       if stk.top == 0
           underflow error handling
       else
           pop element
           stk.top = stk.top - 1
           return stk.items[stk.top] // return popped value
        }

pseudo code: Peak

    function peak (stk) {
        return stk.items[stk.top-1]
        }

    function is_empty (stk) {
        return stk.top == 0
        }

• Dynamic Array
• Linked List Tail

    struct stack {
        Node* head
        Node* tail // Allow us to push elements in O of one time,
                   // But, we still need to traverse through the whole linked list to remove the 
                      last element. Thus, that's not a great solution.
        int count
        }

The solution is actually to add a new node, and assign it as the New Head
Unlike the implementation of a fixed size array, we don't need to check if the stack is full or not,
there is no limit to the size of stack.

• Linked List Head
  pseudo code: Pushing new element

    function push (stk.x) {
        newNode = new Node
        newNode.value = x
        newNode.next = stk.head
        stk.head = newNode
        stk.cout = stk.count + 1
        }

C code

    struct Node {
        int value;
        Node* next;
        }

pesudo code: Pop off the element at the Front

    function pop (stk, x) {
        if stk.head == NULL
            underflow error handling        
        else
            r = stk.head.value
            stk.head = stk.head.next
            stk.cout = stk.count - 1
            return r
        }