linked.cpp

#include <iostream>

#include "LinkedList.h"

using namespace std;

template <class T>
LinkedList<T>::LinkedList(T value) {
    appendNode(value);
}

template <class T>
LinkedList<T>::LinkedList(const LinkedList<T> &copyObj) {
    Node *nodePtr = nullptr;
    head = nullptr;

    nodePtr = copyObj.head;

    while (nodePtr) {
        appendNode(nodePtr->value);
        nodePtr = nodePtr->next;
    }
}

template <class T>
void LinkedList<T>::destroy() {
    Node *nodePtr, *nextNode = nullptr;
    nodePtr = head;
    while (nodePtr != nullptr) {
        nextNode = nodePtr->next;
        delete nodePtr;
        nodePtr = nextNode;
    }
    head = nullptr;
}

template <class T>
LinkedList<T>::~LinkedList() {
    destroy();
}

template <class T>
void LinkedList<T>::appendNode(T newValue) {
    Node *newNode;
    Node *nodePtr = nullptr;

    newNode = new Node;
    newNode->value = newValue;
    newNode->next = nullptr;

    if (!head) {
        head = newNode;
    } else {
        nodePtr = head;
        while (nodePtr->next) {
            nodePtr = nodePtr->next;
        }
        nodePtr->next = newNode;
    }
}

template <class T>
void LinkedList<T>::insertNode(T newValue) {
    Node *newNode;
    Node *nodePtr;
    Node *previousNode = nullptr;

    newNode = new Node;
    newNode->value = newValue;

    if (!head) {
        newNode->next = nullptr;
        head = newNode;
    } else {
        nodePtr = head;
        previousNode = nullptr;
        while (nodePtr != nullptr && nodePtr->value < newValue) {
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
        }
        if (previousNode == nullptr) {
            newNode->next = nullptr;
            head = newNode;
        } else {
            previousNode->next = newNode;
            newNode->next = nodePtr;
        }
    }
}

template <class T>
void LinkedList<T>::displayList() {
    Node *nodePtr = head;

    while (nodePtr) {
        cout << nodePtr->value << ", ";
        nodePtr = nodePtr->next;
    }
    cout << endl;
}

template <class T>
void LinkedList<T>::deleteNode(T value) {
    Node *nodePtr;
    Node *previousNode;

    if (!head) return;
    if (head->value == value) {
        nodePtr = head->next;
        delete head;
        head = nodePtr;
    } else {
        nodePtr = head;

        while (nodePtr != nullptr && nodePtr->value != value) {
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
        }

        if (nodePtr) {
            previousNode->next = nodePtr->next;
            delete nodePtr;
        }
    }
}

template <class T>
void LinkedList<T>::reverse() {
    Node *nextNode = nullptr;
    Node *prevNode = nullptr;
    Node *nodePtr = head;

    while (nodePtr != nullptr) {
        // Save the next node
        nextNode = nodePtr->next;
        // Point the current node to the previous node
        nodePtr->next = prevNode;
        // Set the previous node to current node (as we're traversing to the next)
        prevNode = nodePtr;
        // Go to the next node
        nodePtr = nextNode;
    }
    head = prevNode;
}

template <class T>
int LinkedList<T>::search(T value) {
    Node *nodePtr = head;
    int counter = 0;
    
    while (nodePtr != nullptr && nodePtr->value != value) {
        nodePtr = nodePtr->next;
        counter += 1;
    }

    if (nodePtr != nullptr) {
        return counter;
    } else {
        return -1;
    }
}

template <class T>
void LinkedList<T>::insertNode(T value, int pos) {
    Node *nodePtr = head;
    Node *newNode, *prevNode = nullptr;
    int currPos = 0;
    
    while (nodePtr != nullptr) {
        if (currPos == pos) {
            newNode = new Node;
            newNode->value = pos;
            newNode->next = nodePtr;
            if (prevNode != nullptr) prevNode->next = newNode;
            else head = newNode;
            return;
        }
        prevNode = nodePtr;
        nodePtr = nodePtr->next;
        currPos += 1;
    }

    appendNode(value);
}



int main() {
    LinkedList<int> list;
    list.appendNode(4);
    list.appendNode(8);
    list.appendNode(12);

    list.displayList();

    list.insertNode(9);
    list.displayList();

    list.deleteNode(8);
    list.displayList();

    list.reverse();
    list.displayList();

    cout << list.search(5) << endl;
    cout << list.search(12) << endl;
    cout << list.search(4) << endl;

    list.insertNode(2,5);
    list.displayList();

    list.insertNode(7,1);
    list.displayList();

    list.insertNode(0,0);
    list.displayList();


    return 0;
}

// Queue
#include <iostream>

using namespace std;


class QueueNode {
    public:
    int value;
    QueueNode *next;
    
    QueueNode(int val) {
        value = val;
        next = nullptr;
    }
};

class DynamicQueue {
    private:
    QueueNode *rear; // added pos
    QueueNode *front; // removed pos
    int numItems;
    
    public:
    DynamicQueue();
    ~DynamicQueue();

    void enqueue(int); // insert to reaer
    int dequeue(); // remove from front and return
    bool isEmpty() const;
    bool isFull() const;
    void clear();
};

DynamicQueue::DynamicQueue() {
    front = nullptr;
    rear = nullptr;
    numItems = 0;
}

DynamicQueue::~DynamicQueue() {
    clear();
}

void DynamicQueue::enqueue(int num) {
    QueueNode *newNode = nullptr;
    newNode = new QueueNode(num);

    if (isEmpty()) {
        front = newNode;
        rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    numItems++;
}

int DynamicQueue::dequeue() {
    QueueNode *temp = nullptr;
    int returnNum = -1;

    if (isEmpty()) {
        cout << "Queue is empty\n";
    } else {
        returnNum = front->value;
        temp = front;
        front = front->next;
        delete temp;

        numItems--;
    }
    return returnNum;
}

void DynamicQueue::clear() {
    while (!isEmpty()) {
        dequeue();
    }
}

bool DynamicQueue::isEmpty() const {
    if (numItems > 0) return false;
    else return true;
}

int main() {
    DynamicQueue dq;
    cout << "Inserting 5 6 7 8 9\n";
    for (int i=5; i<10; i++) dq.enqueue(i);

    cout << "Removing first: ";
    cout << dq.dequeue() << "\n";

    cout << "Removing second: ";
    cout << dq.dequeue() << "\n";

    cout << "Clear everything\n";
    dq.clear();

    dq.dequeue();


    return 0;
}

// Stack
#include <iostream>

using namespace std;

class IntStack {
   private:
    struct IntNode {
        int value;
        IntNode *next;
    };
    IntNode *stackTop;
    int totalElement;

   public:
    IntStack();
    ~IntStack();

    IntStack(const IntStack&);

    void push(int);
    int pop();
    bool isEmpty();

    void add();
    void sub();
    void mult();
    void div();
};

IntStack::IntStack() {
    stackTop = nullptr;
    totalElement = 0;
}

IntStack::~IntStack() {
    IntNode *nodePtr = stackTop;

    while (stackTop != nullptr) {
        nodePtr = stackTop;
        stackTop = stackTop->next;
        delete nodePtr;
    }
    totalElement = 0;
}

IntStack::IntStack(const IntStack &obj) {
    // Copy constructor
    IntNode *nodePtr = obj.stackTop;
    while (nodePtr != nullptr) {
        push(nodePtr->value);
        nodePtr = nodePtr->next;
    }

    totalElement = obj.totalElement;
}

void IntStack::push(int num) {
    IntNode *newNode = nullptr;
    newNode = new IntNode;
    newNode->value = num;

    if (isEmpty()) {
        stackTop = newNode;
        newNode->next = nullptr;
    } else {
        newNode->next = stackTop;
        stackTop = newNode;
    }
    totalElement++;
}

int IntStack::pop() {
    IntNode *nodePtr = nullptr;
    int retValue = 0;

    if (stackTop != nullptr) {
        nodePtr = stackTop;
        stackTop = nodePtr->next;
        retValue = nodePtr->value;
        delete nodePtr;
    }
    totalElement--;
    return retValue;
}

bool IntStack::isEmpty() {
    return totalElement <= 0;
}

void IntStack::add() {
    int num1, num2;
    num1 = pop();
    num2 = pop();

    push(num1 + num2);
}

void IntStack::sub() {
    int num1, num2;
    num1 = pop();
    num2 = pop();

    push(num1 - num2);
}

void IntStack::mult() {
    int num1, num2;
    num1 = pop();
    num2 = pop();

    push(num1 * num2);
}

void IntStack::div() {
    int num1, num2;
    num1 = pop();
    num2 = pop();

    push(num1 / num2);
}


int main() {    
    IntStack stack;
    stack.push(5);
    stack.push(6);
    stack.add();
    stack.push(7);
    stack.sub();
    stack.push(8);
    stack.push(9);

    while (!stack.isEmpty()) {
        cout << stack.pop() << endl;
    }


    return 0;
}