Single Link List C++

 

Singly Link List C++

Overview

The link list is basically a dynamic array. We can store data as per demand. In a static array, we define an array for a specific number. Like array size 10. When our data cross this limit.

Then our program stops or not proceed. Another problem is when we define an array for a specific number and our data is less then we waste memory to declare the greater size of the array.

Introduction:

First of all, we need a model of the list or node class. Which contain node properties like data property and a pointer to store the next node address.

Let see the Node or Model class 

#pragma once

typedef int itemType;

#include <iostream>

using namespace std;

class Node

{

public:

     itemType data;

     Node* next;

};

Itemtype is int.

Note: Node class properties or method should public. If we declare as a private then we can’t access in list class.

Let see the basic List class Method

void insertFirst(itemType data)

this method used to add a new node in the first position of list. We assign a new node pointer to the existing list first node. After this, we assign the head of the list to the new node.

Condition:

·         If the list is empty then simple head of the list assign new Node.

·         If the list is not empty then-new the node pointer assign head. After this new node assign to the head.

void insertLast(itemType data);

This method uses to add a new node at the end of the list. A pointer moves from head to last. When the pointer reaches the last position then we assign this pointer to the new Node.

Condition:

If the list is empty then we can call here Insert First method here.   

If the list is not empty then we declare a Node pointer then we assign it to head. Trace list from start to end of the list and set condition if node pointer not equal to null. When the pointer reaches this stage.

Loop will stop. We assign the new node to the last node pointer.

void insertAfter(itemType oldV,itemType newV);

This method uses to add a new node after provided value. If the value exists then add node otherwise not.

Conditions:

If the list is empty then show message list is empty.

If list is not empty then find value. If value not found then show message value not found. If the value found then assign a new node pointer to the value found node pointer. After this assign a new node to value found node pointer.

Note: if you assign a new node pointer to value found node pointer then you will note lose other node address otherwise, you will lose address of after coming node.

void concat(Node* node1, Node* node2);

This method uses for to join two lists.

Condition:

If node1 and node2 are empty then simply then show message lists are empty.

If node1 is empty and node2 is not empty then show node2 data.

If node1 is not empty and node2 is empty then show node1 data.

If both nodes are not empty then declare node pointer. Assign pointer to node1. Start loop till end node of the list. When the pointer reaches at end of the list. Then assign the last node pointer to node 2.

void deleteAfter(itemType data);

This method uses to delete node after value provided node.

Condition:

Check if the list is not empty. If the list is empty then the show message list is empty.

If the list is not empty then find provided value. If the value found then assign its pointer to the dummy node pointer. Assign dummy pointer to value found node pointer. Then delete the dummy pointer.

void show(Node* h1);

this method uses to show the data of the list. We need to provide a list.

Condition:

Check if list is not empty. If the list is empty then show The message list is empty.

If list is not empty. Then create a dummy node. Assign this dummy node to head of list. Trace list till dummy pointer becomes null. 

void deleteLast();

This method uses to delete the last node of the list.

Condition:

Check if list is not empty. If the list is empty then the show message list is empty.

If list is not empty then create a dummy pointer of node. Assign it head of list. Start loop with this condition dummy node pointer not equal to null. By using this condition loop will stop at the second last position of list. Then we create another dummy2 pointer and assign it (dummy pointer2) to dummy1 pointer. After this we delete dummy pointer 2.

void display();

this method also uses to show data. It has the same condition as the show method.

void split();

This use to break down a list into two parts.

void deleteNode(itemType data);

This method use to delete nodes by user-provided value.

Condition:

Check list is not empty. If list is empty then show The message list is empty.

If list is not empty. Then find value. If the value found then delete node.

A extra pointer use like the previous pointer. Which store previous pointer address. With the help of it we delete the node.

void deleteFirst();

This method use to delete the first position node.

Condition:

Check if list is empty. Then show message list is empty.

If list is not empty. Then create a dummy node. Assig it head pointer. Then assign head to dummy pointer. And delete dummy pointer. 

Node Class

#pragma once

typedef int itemType;

#include <iostream>

using namespace std;

class Node

{

public:

     itemType data;

     Node* next;

};

List.h

#pragma once

#include "Node.h"

class List

{

     Node *head;

public:

     List();

     bool isEmpty();

     Node* newNode(itemType data);

            void insertFirst(itemType data);

     void insertAfter(itemType oldV,itemType newV);

     void insertLast(itemType data);

     void deleteNode(itemType data);

     void deleteFirst();

     void deleteAfter(itemType data);

     void deleteLast();

     void display();

     void split();//Break in two parts.

     void subSplit(Node* node);

     void show(Node* h1);

     void concat(Node* node1, Node* node2);

};

List.cpp

#include "List.h"

List::List()//Constructor.

{

     head = NULL;

}

bool List::isEmpty()

{

     if (head == NULL)

           return true;

     else

           return false;

}

Node* List::newNode(itemType data)//Create New Node.

{

     Node* n = new Node;

     n->data = data;

     return n;

}

void List::insertFirst(itemType data)//Add Node at first postion of List.

{

     Node* endPtr = head;

     Node* n = newNode(data);

     if (isEmpty())//if List has no Node.

     {

           head = n;

           n->next = n;

     }

     else//if Node has Multiple Node.

     {

           while (endPtr->next != head)

                endPtr = endPtr->next;

           n->next = head;

           endPtr->next = n;

           head = n;

     }

}

void List::insertAfter(itemType oldV, itemType newV)//Add Node after Existing Node.

{

     Node* n = newNode(newV),*ptr=head;

     bool Found = true;

     if (isEmpty())//if list has no node.

     {

           cerr << "List is Empty\n";

           return;

     }

     else// if list has multiple node.

     {

           while (ptr->next != head)

           {

                if (ptr->data == oldV)

                {

                     ptr->next = n;

                     n->next = ptr->next->next;

                }

                ptr = ptr->next;

                Found = false;

           }

           if (ptr->data == oldV && ptr->next == head)//if given node data at end of list.

           {

                Found = true;

                this->insertLast(newV);//last insert function call.

           }

           if (Found == false)

                cerr << "Your value not Found\n";

     }

}

void List::insertLast(itemType data)//add node at the end of list.

{

     Node* n = newNode(data), * endPtr = head;

     if (isEmpty())//if list has no node.

           this->insertFirst(data);//first insert function call.

     else

     {

           while (endPtr->next != head)

                endPtr = endPtr->next;

           endPtr->next = n;

           n->next = head;

     }

}

void List::deleteNode(itemType data)

{

     Node* dataPtr = head, * temp = NULL,*endPtr = head;

     bool Found = false;

     if (isEmpty())//if List is Empty.

           cerr << "\nList is Empty You Can't Delete Data\n";

     else if (head->data == data && head->next==head)//if Node has only one Node.

     {

           Found = true;

           temp = head;

           head = NULL;

           delete temp;

           return;

     }

     else if (head->data == data)//if given node data at first position.

     {

           Found = true;

           while (endPtr->next != head)

                endPtr = endPtr->next;

           temp = head;

           head = temp->next;

           endPtr->next = head;

           delete temp;

           return;

     }

     else

     {

           while (dataPtr->next!= head)

           {

                if (dataPtr->data == data)

                {

                     Found = true;

                     while (endPtr->next->data != data)//endPtr stop at bact position of dataPtr.

                     {

                           endPtr = endPtr->next;

                     }

                     temp = dataPtr;

                     endPtr->next = temp->next;

                     delete temp;

                      return;

                }

                dataPtr = dataPtr->next;

           }

           if (dataPtr->data == data)//Given node data at last position

           {

                Found = true;

                temp = dataPtr;

                while (endPtr->next->next != head)//endPtr stop at second Last Node.

                     endPtr = endPtr->next;

                endPtr->next = head;

                delete temp;

                return;

           }

           if (Found == false)

                cerr << "\nYour Data not Found\n";

     }

}

void List::deleteFirst()//delete first Node from list.

{

     this->deleteNode(head->data);//deleteNode function call which accept first node data.

     return;

}

void List::deleteAfter(itemType data)

{

     Node* dataPtr = head;

     /*

           There Two case

           1->Case:

           if List is Empty.

           2->Case:

           List has only one node.

           */

     if (isEmpty()&&head->data==data)

     {

           cerr << "\nYou can't Delete Data\n";

     }

     else

     {

           while (dataPtr->next != head)//delete Node from center of List.

           {

                if (dataPtr->data == data)

                {

                     this->deleteNode(dataPtr->next->data);//deletenode Function call which accept next data of given data node.

                     return;

                }

                dataPtr = dataPtr->next;

           }

           if (dataPtr->data == data)

           {

                cerr << "\nYou Can't Delete Data\n";

                return;

           }

     }

}

void List::deleteLast()//delete Node from last.

{

     Node* dataPtr = head;

     while (dataPtr->next != head)//dataptr stop at last node.

           dataPtr = dataPtr->next;

     this->deleteNode(dataPtr->data);//accept last node data.

     return;

}

void List::display()

{

     Node* dataPtr = head;

     if (isEmpty())//if list has no node.

           cerr << "\nList is Empty\n";

     else

     {

           do

           {

                cout << dataPtr->data << "-->";

                dataPtr = dataPtr->next;

           } while (dataPtr != head);

           cout << "\n";

     }

}

void List::split()

{

     Node* node1 =NULL;//Node1 declare.

     Node* node2 = NULL;//Node2 declare.

     Node* endPtr = head;

     int count = 1;//count total node in list.

     while (endPtr->next != head)

     {

           endPtr = endPtr->next;

           count++;

     }

     int totaln = count;

     if (count % 2 == 0)//check if list has even node.

           count = count / 2;//even divide with 2.

     else

           count = ((count - 1) / 2) + 1;//odd node

     cout << "\nTotal Node = " << totaln << "\n";

     cout << "\nFirst Node = " << count << "\n";

     cout << "\nSecond Node = " << totaln-count << "\n";

     Node* ptr2 = head;

     node1 = ptr2;//node1 equal to list.

     int y = 1;

     while (ptr2->next != head && y!=count)

     {

           ptr2 = ptr2->next;

           y++;

     }

     Node* secNode = ptr2->next;

     node2 = ptr2->next;

     ptr2->next = node1;

     cout << "\nFirst Siplit Node\n";

     this->show(node1);

     Node* nptr = head;

     while (secNode->next != head)

     {

           secNode = secNode->next;

     }

     secNode->next = node2;

     cout << "\nSecond Siplit Node\n";//Display Second part of List.

     this->show(node2);

     cout << "\nConcate Node\n";//Join Node1 and Node2.

     this->concat(node1, node2);

     cout << "\nSub Separation\n";//Again Divid Join Node.

     this->subSplit(node2);

}

void List::show(Node*h1)

{

     Node* ptr = h1;

     do

     {

           cout << ptr->data << "-->";

           ptr = ptr->next;

     } while (ptr != h1);

     cout << "\n";

}

void List::subSplit(Node* node)

{

     Node* node1 = NULL;

     Node* node2 = NULL;

     Node* ptr = node;

     int count = 1,totaln=0;

     while (ptr->next != node)

     {

           ptr = ptr->next;

           count++;

     }

     totaln = count;

     if (count % 2 == 0)

           count = count / 2;

     else

           count = ((count - 1) / 2) + 1;

     cout << "\nTotal Node = " << totaln <<"\n";

     cout << "\nFirst Node = " << count << "\n";

     cout << "\nSecond Node = " << totaln - count << "\n";

     Node * ptr2 = node;

     node1 = ptr2;

     int y = 1;

     while (ptr2->next != node && y != count)

     {

           ptr2 = ptr2->next;

           y++;

     }

     Node* secNode = ptr2->next;

     node2 = ptr2->next;

     ptr2->next = node1;

     cout << "\nFirst Siplit Node\n";

     this->show(node1);

     Node* nptr = head;

     while (secNode->next != node)

     {

           secNode = secNode->next;

     }

     secNode->next = node2;

     cout << "\nSecond Siplit Node\n";

     this->show(node2);

}

void List::concat(Node* node1, Node* node2)

{

     Node* endPtr1 = node1, * endPtr2 = node2;

     if (node1 == NULL)

           this->show(node2);

     if (node2 == NULL)

           this->show(node1);

     while (endPtr1->next != node1)

           endPtr1 = endPtr1->next;

     while (endPtr2->next != node2)

           endPtr2 = endPtr2->next;

     endPtr1->next = node2;

     endPtr2->next = node1;

     this->show(node1);

}

Main.cpp

#include "List.h"

int main()

{

     List l;

     l.insertFirst(8);

     l.insertFirst(7);

     l.insertFirst(6);

     l.insertFirst(5);

     l.insertFirst(4);

     l.insertFirst(3);

     l.insertFirst(2);

     l.insertFirst(1);

     l.insertLast(9);

     l.insertAfter(9, 10);

     cout << "\nList Data:\n";

     l.display();

     l.deleteNode(10);

     l.deleteFirst();

     l.deleteAfter(7);

     l.deleteLast();

     cout << "\nDelete Node:\n";

     l.display();

     cout << "\nTwo Part of Orignal List\n";

     l.split();

}

 

Singly Link List C++ example