Node

class Node{
    private:
        int data;
        Node* next;
    public:
        Node(){data = 0; next = NULL;}
        Node(int d){data =d; next = NULL;}
        Node(int d, Node* n){data = d; next=n;}
        ~Node(){delete next;}
        int getData(){return data;}
        Node* getNext(){return next;}
        void setData(int d){data = d;}
        void setNext(Node* n){next = n;}
};

Stacks

Putting a node or removing a node happens with LIFO (Last-In First-Out)

• pop() Remove the node that was most recently inserted

• push() Insert a node at the head only as pop() would remove a node from head

  

class Stack{
    private:
        Node* head;
    public:
        Stack(){head = NULL;}
        ~Stack(){delete head;}
        void push(int d){
            Node* p = new Node(d, head);
            head = p;
        }

    int pop(){
        if(head == NULL)
            return -1;
        Node* p = head;
        int d = p -> getData();
        head p -> getNext();
        p -> setNext(NULL);
        delete p;
        return d;
    }
};

Considerations:

1. What happens if the stack is empty?
2. Does it work if the stack has one node?

Queues

• Putting a node or removing a node happens with FIFO (First In First Out)
• dequeue() removes the node that was first put in the list
• enqueue() puts a node at the end of the list

class Queue{
    private:
        Node* head;
        Node* tail;
    public:
        Queue(){
            head = NULL;
            tail = NULL;
        }

        ~Queue(){
            delete head;
        }

        void enqueue(int d){
            Node* p = new Node(d, NULL);
            tail -> setNext(p);
            tail = p;
            if(head == NULL) head = p;
        }

        int dequeue(){
            if(head == NULL) return -1;
            Node* p = head;
            head = p -> getNext();
            int d = p -> getData();
            p -> setNext(NULL);
            delete p;
            return d;
        }
};

///////
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);

cout << q.dequeue() << q.dequeue() << endl;
//output 1 2 3

Ordered Linked Lists

#include "Node.h"

class List{
    private:
        Node* head;
    public:
        List() {head = NULL;}
        ~List(){double head;}
        void insertData(int d);
        bool dataExists(int d);
        bool deleteData(int d);
        List(const List&); //copy consutrctor
        List& operator=(const List&);
};

Search

bool dataExists(int d){
    Node* p = head;
    while(p != NULL && p-> getData() < d){
        if(p->getData == d){
            return true;
        }
        else{
            p = p -> getNext();
        }
    }

    return false;
}