Sorted Linked List in C++
Syntax of the Sorted Linked List
Creating a struct or class for each node in the list which includes a data element and a reference to the next node is the fundamental syntax for a sorted linked list in C++. We must provide a comparison function or operator overload that compares the nodes according to a certain key value in order to preserve the sorted order. We may insert additional nodes using a variety of techniques that keep the list ordered. To understand clearly the working of the sorted linked list, let’s do some examples.
Implementation of the Sorted Linked List in C++
Let us start implementing the very first and simple example of the sorted linked list so that we can easily understand the basic structure of sorted linked lists in C++ programming language. To start writing the code, we always first include the necessary libraries in the code so that the program executes without generating any type of error. We write the preprocessor directive #include <iostream> which instructs the compiler to include the iostream library.
In C++ programming, the iostream library offers capabilities for the input and output operations. The next line, which defines the use of the std namespace in the code, is the use of the namespace std line. The std namespace contains objects and methods from the common C++ library. We may avoid writing the namespace prefix of std:: each time we utilize a function or object from the standard library by utilizing the keyword in the program.
After including the necessary libraries, we then create a struct that describes the structure of each node in a linked list, each of which has a reference to the following node and an int data element. Then, we create a class called SortedLinkedList. The head pointer, which is a pointer to the top node of the linked list, is a private member variable of this class. The constructor sets the head pointer to nullptr which indicates that the list is initially empty.
The class member SortedLinkedList() method initializes the head pointer to the nullptr as part of the constructor process. When an object that belongs to the class is created, the default constructor for the class is automatically invoked. The head pointer may only be accessible from within the class and not from outside of it according to the class definition’s private access specifier. The user is kept in the dark regarding the implementation of the linked list due to this encapsulation and may only interact with it through the public member functions of the class.
Next, we define a member function called “insert” in the SortedLinkedList class, which is responsible to insert a new node in the linked list in the sorted order. This function takes an integer value as a parameter which is the value to be stored in the new node. Then, the function first creates a new node object dynamically using the new operator and assigns the value to the data member of the node. Nullptr is the value set for the node’s next pointer.
After that, the function determines if the list is empty or if the value is smaller than the data for the first node. If either of the conditions is true, the new node is inserted at the beginning of the list by setting its next pointer to the current head and making it the new head of the list. If the value is greater than the data of the first node, the function iterates through the list until it finds the appropriate position to insert the new node in sorted order.
This is done using a while loop that continues until the next pointer of the current node is nullptr or the data of the next node is greater than the value.
Next, we define another function which is the remove() function that removes a node with the given “value” from the SortedLinkedList. The function starts by initializing two pointer variables, “temp” and “prev”, which point to the head node and null, respectively. It then iterates through the linked list using a while loop, comparing the value of the current node (temp->data) with the given value until it reaches the end of the list or finds a node with the matching value.
The method returns after printing “Value not found” if the value cannot be located. If the value is discovered, it determines if the head node is the node that has to be deleted. If not, it changes the preceding node’s “next” reference (prev->next) to point to the node that is deleted next (temp->next). To release the allotted memory, it deletes the node that is deleted using the “delete” keyword.
Next, we define another member function which is the display() function in the SortedLinkedList class which is responsible to display the contents of the linked list. The function first declares a temporary node pointer called “temp” and initializes it to point to the head of the linked list. The function then enters a while loop that continues until the “temp” pointer reaches the end of the linked list, i.e. the next pointer of the last node is nullptr.
Inside the loop, the function outputs the value of the data member of the current node using the cout statement. The function then sets the temporary pointer equal to the current node’s next pointer to update it to point to the subsequent node. Once the loop exits, the function outputs a newline character to move the output to the next line.
using namespace std;
struct Node {
int data;
Node* next;
};
class SortedLinkedList {
private:
Node* head;
public:
SortedLinkedList() {
head = nullptr;
}
void insert(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
if (head == nullptr || value < head->data) {
newNode->next = head;
head = newNode;
}
else {
Node* temp = head;
while (temp->next != nullptr && temp->next->data < value) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
void remove(int value) {
Node* temp = head;
Node* prev = nullptr;
while (temp != nullptr && temp->data != value) {
prev = temp;
temp = temp->next;
}
if (temp == nullptr) {
cout << "Value not found." << endl;
return;
}
if (temp == head) {
head = head->next;
}
else {
prev->next = temp->next;
}
delete temp;
}
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
}
int main()
{
SortedLinkedList list;
list.insert(145);
list.insert(0);
list.insert(34);
list.insert(144);
cout << "New Created Sorted Linked List: ";
list.display();
list.remove(0);
cout << "After Removing an Element, the Updated Linked List: ";
list.display();
list.insert(123);
cout < "After Inserting an Element, the Updated Linked List: ";
list.display();
return 0;
}
Now, we start the main() function, and we start writing the code so that we can easily access the functions which we previously created. After defining the main() function, we create an instance of the SortedLinkedList class called “list” and insert some values in it using the “insert member” function.
After that, it removes an element with the value of 0 using the “remove” method and displays the updated list. Then, it inserts a new value of 123 into the list using the “insert” method again and displays the updated list. The main() method then returns 0 at the end to show that the program ran successfully. Here is the sorted output:
Conclusion
We learned one of the important methods of C++ which is on how to sort the linked list in C++ programming language. We implemented an example so that we can easily understand the structure and method of sorting the linked lists in C++ with detailed explanations.
Source: linuxhint.com