Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Linked list (sorted)
#include <iostream>
using namespace std;
// For a single node.
struct Node
{
int data;
Node * next;
};
// Sorted in non-decreasing order.
// Allows multiple entries with same data.
class SortedLinkedList
{
Node * head;
public:
void insert(int newData) // Inserts the new data at the appropiate location
{
Node * newNode = new Node;
newNode->data = newData;
if (this->head == NULL) // Handle case when no data has been inserted till now.
{
newNode->next = NULL;
this->head = newNode;
}
else if (this->head->data > newData) // Case for input data being lesser than the first element itself.
{
newNode->next = this->head;
this->head = newNode;
}
else
{
Node * previous = this->head;
while (previous->next != NULL)
{
if (previous->next-> data > newData)
{
newNode->next = previous->next;
previous->next = newNode;
break;
}
previous = previous->next;
}
if (previous->next == NULL)
{
newNode->next = NULL;
previous->next = newNode;
}
}
return;
}
void printLinkedList() // Print the elements.
{
Node * traversingPointr = this->head;
if (traversingPointr == NULL)
{
cout<<"Linked List is empty\n";
return;
}
while (traversingPointr != NULL)
{
cout<<traversingPointr->data;
if(traversingPointr->next != NULL) // Don't print "->" for last element.
cout<<" -> ";
traversingPointr = traversingPointr -> next;
}
cout<<"\n";
return;
}
// Initialize head to NULL;
SortedLinkedList()
{
head = NULL;
}
~SortedLinkedList()
{/* Destructr */}
};
int main()
{
int newData, choice;
SortedLinkedList list1;
while(true)
{
cout<<"\n----------------------------------------------\n";
cout<<"Enter 1, if you want to add a number to linked list\n"<<"Enter 2, if you want to print\n"<<"Enter 3, if you want to exit";
cout<<"\n----------------------------------------------\n";
cin>>choice;
if (choice == 3)
break;
switch (choice)
{
case 1: // Adding a number
cout<<"\nEnter a number: ";
cin>>newData;
list1.insert(newData);
// Let this fall through to print the changed linked list.
case 2:
cout<<"Linked list has data: ";
list1.printLinkedList();
break;
case 3:
break;
default:
cout<<"\nInvalid choice, enter 1 or 2 or 3\n";
break;
}
}
cout<<"\nFinal linked list is \n";
list1.printLinkedList();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.