linked_list.cpp

#include <iostream>
using namespace std;
//generic implementation of Singly Linked List using templates
template <class T>
struct node
{
    T data;
    struct node *next;
};
template <class T>
class LinkedList
{
  private:
    int size;
    struct node<T> *start;

  public:
    LinkedList()
    {
        size = 0;
        start = NULL;
    }
    struct node<T> *create_node(const T value)
    {
        struct node<T> *temp = new (struct node<T>);
        temp->next = NULL;
        temp->data = value;
        return temp;
    }
    // functions to insert values
    void insert_begin(const T value)
    {
        struct node<T> *temp = create_node(value);
        temp->next = start;
        start = temp;
        size++;
    }
    void insert(const T value)
    {
        struct node<T> *temp = start;
        if (temp != NULL)
        {
            while (temp->next != NULL)
                temp = temp->next;
            temp->next = create_node(value);
            size++;
        }
        else
        {
            insert_begin(value);
        }
    }
    void insert_pos(const T value, int pos)
    {
        if (pos == 1)
        {
            insert_begin(value);
        }
        else if (pos == size + 1)
        {
            insert(value);
        }
        else if (pos <= size)
        {
            struct node<T> *curr = create_node(value), *temp = start;
            for (int i = 1; i < pos - 1; i++)
            {
                temp = temp->next;
            }
            curr->next = temp->next;
            temp->next = curr;
            size++;
        }
        else
        {
            cout << "\nInsertion at position " << pos << " is not possible\n";
        }
    }
    // search the list
    int search(const T value)
    {
        struct node<T> *temp = start;
        for (int pos = 1; temp != NULL; pos++)
        {
            if (temp->data == value)
            {
                return pos;
            }
            temp = temp->next;
        }
        return -1;
    }
    // delete from list
    void remove_pos(const int pos)
    {
        if (pos > 1 && pos <= size)
        {
            struct node<T> *curr = NULL, *temp = start;
            for (int i = 1; i < pos - 1; i++)
            {
                temp = temp->next;
            }
            curr = temp->next;
            temp->next = curr->next;
            delete curr;
            size--;
        }
        else if (pos == 1 && size >= pos)
        {
            struct node<T> *temp = start->next;
            delete start;
            start = temp;
            size--;
        }
        else
        {
            cout << "\nNo such entry in list\n";
        }
    }
    void remove(const T value)
    {
        remove_pos(search(value));
    }
    void reverse()
    {
        if (start != NULL && start->next != NULL)
        {
            struct node<T> *p1 = NULL, *curr = start, *p2 = start->next;
            while (p2 != NULL)
            {
                curr->next = p1;
                p1 = curr;
                curr = p2;
                p2 = p2->next;
            }
            curr->next=p1;
            start = curr;
        }
    }
    void sort()
    {
        T x;
        struct node<T>* p1=NULL,*p2=NULL,*last=NULL;
        if(start!=NULL && start->next!=NULL)
        {
            for(p1=start;p1!=NULL;p1=p1->next)
            {
                for(p2=start;p2->next!=last;p2=p2->next)
                {
                    if(p2->data > p1->data)
                    {
                        x=p1->data;
                        p1->data=p2->data;
                        p2->data=x;
                    }
                    if(p2->next==last)
                    {   last=p2;
                    }
                }
            }

        }
    }
    // getters
    int getSize()
    {
        return size;
    }
    struct node<T> *getStart()
    {
        return start;
    }
};

int main()
{
    LinkedList<int> ll;
    ll.insert_begin(5);
    ll.insert_begin(6);
    ll.insert(78);
    ll.insert_pos(54, 4);
    ll.insert_pos(8, 4);
    ll.insert_pos(7, 1);
    ll.insert_pos(8888, 12);
    //7 6 5 78 8 54
    struct node<int> *temp = ll.getStart();
    for (; temp != NULL; temp = temp->next)
        cout << temp->data << "\n";
    cout << "\nsize=" << ll.getSize() << "\n";
    cout << "\n78 found at position: " << ll.search(78) << "\n";
    ll.remove(78);
    ll.remove_pos(5);
    ll.remove_pos(1);
    ll.remove_pos(10);
    //6 5 8
    temp = ll.getStart();
    for (; temp != NULL; temp = temp->next)
        cout << temp->data << "\n";
    cout << "\nsize=" << ll.getSize() << "\n";
    ll.reverse();
    temp = ll.getStart();
    for (; temp != NULL; temp = temp->next)
        cout << temp->data << "\n";
    cout << "\nsize=" << ll.getSize() << "\n";
    ll.insert(-1);
    ll.insert(34);
    ll.sort();
    //-1 5 6 8 34
    temp = ll.getStart();
    for (; temp != NULL; temp = temp->next)
        cout << temp->data << "\n";
    cout << "\nsize=" << ll.getSize() << "\n";
    return 0;
}