Monday, 5 December 2016

Linked List

#include <bits/stdc++.h>
using namespace std;

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;
    }

    void setData(int x) {
        data = x;
    }

    int getData() {
        return data;
    }

    void setNext(Node* x) {
        next = x;
    }

    Node* getNext() {
        return next;
    }
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = NULL;
    }

    void insertAtFront(int data) {
        Node* n = new Node(data, head);
        head = n;
    }

    void insertAtBack(int data) {
        Node* n = new Node(data);
        if (head == NULL) {
            head = n;
        } else {
            Node* i;
            for (i = head; i->getNext() != NULL; i=i->getNext())
                ;
            i->setNext(n);
        }
    }

    void insertAfter(int key, int data) {
        // inserts a new node containing data
        // after the node containing key
        // assuming that a node containing key exists

        Node* n = new Node(data);
        Node* i;
        for (i = head; i->getData() != key; i=i->getNext())
            ;
        n->setNext(i->getNext());
        i->setNext(n);
    }

    int removeFromFront() {
        Node* n = head;
        int x = n->getData();
        head = head->getNext();
        delete n;
        return x;
    }

    int removeFromBack() {
        Node* n;
        Node* i;
        int x;
        for (i = head; i->getNext()->getNext() != NULL; i = i->getNext())
            ;
        n = i->getNext();
        x = n->getData();
        delete n;
        i->setNext(NULL);
        return x;
    }

    void print() {
        for (Node* i = head; i != NULL; i = i->getNext())
            cout << i->getData() << endl;
    }

    int size() {
        int total = 0;
        for (Node* i = head; i != NULL; i = i->getNext())
            total++;
        return total;
    }

    bool isEmpty() {
        if (head == NULL)
            return true;
        else return false;
    }

    bool isPresent(int x) {
        for (Node* i = head; i != NULL; i = i->getNext())
            if (i->getData() == x)
                return true;
        return false;
    }
};

int main() {
    LinkedList list;
    list.insertAtFront(50);
    list.insertAtFront(4);
    list.insertAtFront(14);
    list.insertAtFront(40);
    list.insertAtBack(1);
    list.insertAtBack(2);
    list.insertAfter(40, 5);

    if (list.isPresent(5))
        cout << "5 is present" << endl;
    else cout << "5 is not present" << endl;

    list.print();
    cout << "Total number of elements " << list.size() << endl;

    while (!list.isEmpty())
    {
        cout << "Removing from front " << list.removeFromFront() << endl;
        if(!list.isEmpty())
         cout << "Removing from back " << list.removeFromBack() << endl;
    }

    list.print();
    cout << "Total number of elements " << list.size() << endl;

    return 0;
}

No comments:

Post a Comment