# Data Structures & Algorithms Fall 2023

#### Instructor:
Dr. Umar Suleman ([e-mail])
#### TAs:
- Saad Ahmed ([e-mail])
- Muhammad Zain Faraz ([e-mail])

## Assignment 6

### Submission Format:
A single .zip file labelled `BSCSXXXXX-Assignment-4.zip` which should contain ONLY the `.cpp`, `.h` and `.doc` files.

<span style="color: red">Note: Late submissions would not be entertained and any kind of plagiarism would not be tolerated!</span>

### Task 1:

### Task 2:
Implement the `CircularList` class. A normal linked list and a circular linked list differ primarily in how they handle the termination of the list. In a normal linked list, the last node points to `nullptr` indicating the end of the list and traversal stops upon encountering this null pointer. In contrast, a circular linked list connects the last node's next pointer back to the first node, forming a loop. This means that in a circular linked list, traversal continues until we revisit the `head`, as there is no explicit end marked by `nullptr`

template <class T>
class CircularList 
{
    Node<T>* head;
    Node<T>* tail;
public:
    CircularList(); //initialize both pointers with nullptr
    void insert(T _data); //add node with data at the end of list
    Node<T>* find(T _data); //return node with matching data
    void erase(Node<T>* it); //remove the matching node from list
    T& operator[](int i); //return the data at ith node
    void print() // print the circular list
    ~CircularList(); //deallocate all nodes
};

### Task 3:
Implement the `DoublyNode` and `DoublyList` class. Each node in a doubly linked list contains two pointers: one pointing to the next node in the sequence and another pointing to the previous node. This bidirectional linkage allows for more flexible traversal and manipulation of the list compared to a singly linked list.

template <class T>
struct DoublyNode
{
    T data;
    DoublyNode<T>* prev; // This points to nullptr for head
    DoublyNode<T>* next; // This points to nullptr for tail
    
    DoublyNode(); //initialize next with nullptr
    DoublyNode(T _data); 
    //initialize data with _data and next with nullptr
    DoublyNode(T _data, DoublyNode<T>* _prev, DoublyNode<T>* _next);
    //You know what to do-
};

template <class T>
class DoublyList 
{
    DoublyNode<T>* head;
    DoublyNode<T>* tail;
public:
    DoublyList(); //initialize both pointers with nullptr
    void insert(T _data); //add node with data at the end of list
    void insert(T _data, int pos); //add node with data at pos-th index
    DoublyNode<T>* find(T_data); //return node with matching data
    void erase(DoublyNode<T>* it); //remove the matching node from list
    T& operator[](int i); //return the data at ith node
    void print_next() // print the list from head to tail
    void print_prev() // print the list from tail to head
    // Both print functions are of O(n) time complexity!
    ~DoublyList(); //deallocate all nodes
};

### Task 4:
Implement the `Stack` and `Queue` class using linked list:

template <class T>
class Stack
{
    LinkedList<T> list;
    int _size;
public:
    Stack(); //initialize your attributes
    int size(); //return current size of your stack
    bool empty(); //tell whether the stack is empty or not
    T top() //return the top element of stack
    void push(T _data) //push the data into stack
    void pop() //remove the top element of stack
    void print() //print your stack from top to bottom
};

template <class T>
class Queue
{
    LinkedList<T> list;
    int _size;
public:
    Queue(); //initialize your attributes
    int size(); //return current size of your queue
    bool empty(); //tell whether the queue is empty or not
    T front() //return element at front of queue
    T back() //return element at back of queue
    void push_back(T _data) //pushe the data at the back
    void pop_front() //remove the data at front
    void print() //print your queue from front to back
};

**Note:** Write a brief report discussing the suitability of implementing stacks and queues using either linked lists or arrays. Submit the report along with the `.cpp` and `.h` files.

### Task 5:
Implement a linked list of arrays:-

template <class T>
struct ArrNode
{
    T* arr;
    int size;
    int capacity;
    ArrNode<T>* next;
    //You can add whatever attribute/method you like here.
};

template <class T>
class ArrList
{
private:
    ArrNode<T>* head;
    ArrNode<T>* tail;
    //You are free to add any additional method/attribute.
public:
    ArrList(); //initialize both attributes
    void insert(T _data); //add data at the end of list/array
    void insert(T _data, int i); //add data at the overall i-th index
    pair<ArrNode<T>*,int> find(T _data); //return a pointer to the node-
    //and the index at which the data exist
    void erase(ArrNode<T>* it, int i); //remove the data from the node-
    //if the array becomes empty, delete the node
    void erase(ArrNode<T>* it) //remove the node
    T& operator[](int i); //return the data at overall i-th index
    void print() //print the list of arrays
    ~ArrList(); //deallocate all nodes
};

**Note:** You must implement two versions of this list:-
- For the first one, the size of the array must double for each created node from head to tail. So the first node would be an array of size n, the second would be of size 2n, third one would be of size 4n and so on.
- For the second one, the user would tell the size of the array each time a new node is created.