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

Abstract Data Type (ADT)

Human - Interface - ADTListWith OrderList 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

PrimitiveStructuresArraysLinked ListTreesGraphs

ADT

To create an "ADT", you have to have a clear interface and a good implementationA 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, GraphsIntegers, 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 OperationInsert element: Insert BackIf 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 attributesThink of Struct as a kind of container of multiple attributesAttribute also called as Member Variable or Member FieldsOur Node Structure contains attributes which are Value and PointerThe 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:In the array, the size of data format is fixed, we could access specific index quickly.Thus, the Time Complexity is O(1).Linked List: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.To get the third element of Linked List, you must traverse form the head of the list.We have to follow up the nodes, one-by-one all the way to the third element.Thus, the Time Complexity is O(n) (In Search/Get).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 advancedThe linked lists could Dynamically allocate each node.On the other hand, Arrays need to be allocated with some fixed amount of memoryWhen 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 LengthReturn Length: O(n)

    struct LinkedList {        Node* head;        }

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 ListPros & Cons of implementing the Stack ADTStack is a list of elements, just like the List ADTInitializing a Stack
stack = new StackPush/PopFunction: 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 ArrayLinked 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        }