A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. The last node in the sequence has a reference to null, indicating the end of the list.
Linked lists are useful when the size of the data is not known in advance or when the data needs to be dynamically added or removed. They are also used in many applications, such as implementing stacks and queues.
Here is an example of a simple linked list in C++:
#include <iostream>
using namespace std;
class LinkedList {
public:
int data;
LinkedList *next;
// constructor
LinkedList(int data, LinkedList *next = nullptr) : data(data), next(next) {}
};
int main() {
// Step 1: Create nodes in a forward-chained manner
LinkedList* third = new LinkedList(3);
LinkedList* second = new LinkedList(2, third);
LinkedList* head = new LinkedList(1, second);
// Print the linked list starting from the head
LinkedList* current = head; // Start from head
while (current != nullptr) {
cout << current->data << " ";
current= current->next;
}
cout << endl;
return 0;
}Output:
1 2 3Linked list vs Array (in terms of memory allocation):
- An array of size 7:
int arr[7] = {50, 51, 52, 53, 54, 55, 56};
Elements are stored in contiguous memory, with addresses accessible using indices.
- Memory alocation in a LinkedList:
Each node is stored in a separate memory location, with references pointing to the next node.
Couple of methods associated with Singly Linked List:
- Convert the vector into a linkedlist
// convert the vector into a linkedlist
LinkedList *arrayToLinkedList(vector<int> &arr)
{
if (arr.size() == 0)
return nullptr;
LinkedList *head = new LinkedList(arr[0]);
LinkedList *mover = head;
for (int i = 1; i < arr.size(); i++)
{
LinkedList *temp= new LinkedList(arr[i]);
mover->next = temp;
mover = temp;
}
return head;
}
- Display the elements in the linkedlist
// display the elements in the linkedlist
void printLinkedList(LinkedList *head)
{
if (head == nullptr)
{
cout << "The linkedlist is empty!" << endl;
return;
}
else
{
LinkedList *temp = head;
while (temp)
{
cout << temp->data << "->";
temp = temp->next;
}
cout << "null" << endl;
}
}- Display the elements in the circular linkedlist
void printCircularLinkedList(LinkedList *head)
{
if (head == nullptr)
{
cout << "The linkedlist is empty!" << endl;
return;
}
else
{
LinkedList *temp = head;
do
{
cout << temp->data << "->";
temp = temp->next;
} while (temp != head);
cout << head->data << endl;
}
}- Check if the linkedlist is empty
// check if the linkedlist is empty
bool isNull(LinkedList *head)
{
if (head == nullptr)
{
cout << "The linkedlist is empty!" << endl;
return true;
}
return false;
}- Length of the linkedlist
// length of the linkedlist
int length(LinkedList *head)
{
if (head == nullptr)
return 0;
int count = 0;
LinkedList *temp = head;
while (temp != nullptr)
{
temp = temp->next;
count++;
}
return count;
}- Check if there is a loop in the linkedlist using tortise and hare method
bool isLoop(LinkedList *head)
{
if (isNull(head))
return false;
else if (head->next == nullptr)
return false;
else
{
LinkedList *slow = head;
LinkedList *fast = head;
while (fast != nullptr && fast->next != nullptr)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
return true;
}
}
}
return false;
}- Check if the linkedlist is circular
bool isCircular(LinkedList *head)
{
if (isNull(head))
return false;
else if (head->next == nullptr)
return false;
LinkedList *temp = head;
while (temp != nullptr && temp != head)
{
temp = temp->next;
}
return (temp == head);
}- Delete the linkedlist
void deleteLinkedList(LinkedList *head)
{
LinkedList *temp;
while (head != nullptr)
{
temp = head;
head = head->next;
delete temp;
}
}- Delete the circular linkedlist
void deleteCircularLinkedList(LinkedList *list)
{
LinkedList *temp = list->next;
list->next = nullptr;
deleteLinkedList(temp);
delete list;
}- Add elements at the start of the linkedlist
// adding elements
LinkedList *addElementAtStart(LinkedList *head, int ele)
{
if (head == nullptr)
{
head = new LinkedList(ele);
return head;
}
LinkedList *temp = new LinkedList(ele);
temp->next = head;
head = temp;
return head;
}- Add elements at the end of the linkedlist
LinkedList *addElementAtEnd(LinkedList *head, int ele)
{
if (head == nullptr)
{
head = new LinkedList(ele);
return head;
}
LinkedList *tail = new LinkedList(ele);
LinkedList *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = tail;
return head;
}- Add elements at a specific position in the linkedlist
LinkedList *addElementAtPos(LinkedList *head, int ele, int pos)
{
if (pos < 1)
{
cout << "Invalid position, must be >= 1." << endl;
return head; // Invalid position
}
if (pos == 1)
{ // Insert at head
return addElementAtStart(head, ele);
}
int len = length(head);
if (pos > len + 1)
{ // Allow insertion at the end
cout << "Position " << pos << " is out of bounds" << endl;
return head;
}
LinkedList *temp = head;
int count = 1; // Start counting from 1
while (temp && count < pos - 1)
{
temp = temp->next; // Move to the node before the position
count++;
}
LinkedList *newNode = new LinkedList(ele);
newNode->next = temp->next; // Insert new node at the position
temp->next = newNode;
return head; // Return the head of the linked list
}- Delete the head of the linkedlist
// delete nodes in the linked list
void deleteHead(LinkedList *head)
{
if (isNull(head))
return;
LinkedList *temp = head;
head = head->next;
delete temp;
}- Delete the tail of the linkedlist
LinkedList *deleteTail(LinkedList *head)
{
if (isNull(head))
return nullptr;
if (head->next == nullptr)
{ // Only one element
delete head;
return nullptr;
}
LinkedList *temp = head;
while (temp->next->next != nullptr)
{ // Stop at the second last node
temp = temp->next;
}
delete temp->next; // Delete the last node
temp->next = nullptr; // Set the second last node's next to nullptr
return head; // Return the updated head
}- Delete a node in the linkedlist
LinkedList *deleteNode(LinkedList *head, int data)
{
if (isNull(head))
return nullptr;
if (head->data == data)
{
LinkedList *newHead = head->next;
delete head;
return newHead;
}
LinkedList *temp = head;
while (temp->next != nullptr)
{
if (temp->next->data == data)
{
LinkedList *nodeToDelete = temp->next;
temp->next = temp->next->next;
delete nodeToDelete;
return head;
}
temp = temp->next;
}
return head;
}- Delete a node at a specific position in the linkedlist
LinkedList *deleteNodeAtPos(LinkedList *head, int pos)
{
if (isNull(head))
{
cout << "Invalid position value, the linked list is empty." << endl;
return nullptr;
}
if (pos == 1)
{
LinkedList *newHead = head->next;
delete head; // Free the old head
return newHead; // Return the new head
}
int len = length(head);
if (pos > len || pos < 1)
{
cout << "Invalid position value, the position " << pos << " exceeds the length of the linked list provided." << endl;
return head; // Return the unchanged head
}
// Handle case for deleting the tail node
if (pos == len)
{
return deleteTail(head); // Use your existing deleteTail function
}
// Find the node before the one we want to delete
LinkedList *temp = head;
int count = 1; // Start counting from 1
while (temp != nullptr && count < pos - 1)
{
temp = temp->next; // Move to the next node
count++;
}
if (temp != nullptr && temp->next != nullptr)
{
LinkedList *nodeToDelete = temp->next; // The node to delete
temp->next = nodeToDelete->next; // Bypass the node to delete
delete nodeToDelete; // Delete the node
}
return head; // Return the head of the linked list
}- Reverse a singly linked list
// reverse a singly linked list
LinkedList *reverse(LinkedList *head)
{ // TC: O(2N), SC: O(1)
if (head == NULL || head->next == NULL)
return head;
LinkedList *temp = head;
LinkedList *prevNode = NULL;
while (temp)
{
LinkedList *nextNode = temp->next;
temp->next = prevNode;
prevNode = temp;
temp = nextNode;
}
return prevNode;
}- Sort a singly linked list using merge sort
// sort a singly linked list
LinkedList *helper_findMiddle(LinkedList *head)
{
LinkedList *slow = head;
LinkedList *fast = head->next;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
LinkedList *helper_merge(LinkedList *list1, LinkedList *list2)
{
LinkedList *dummyNode = new LinkedList(-1);
LinkedList *temp = dummyNode;
while (list1 != NULL && list2 != NULL)
{
if (list1->data < list2->data)
{
temp->next = list1;
temp = list1;
list1 = list1->next;
}
else
{
temp->next = list2;
temp = list2;
list2 = list2->next;
}
}
if (list1)
temp->next = list1;
else
temp->next = list2;
return dummyNode->next;
}
LinkedList *sort(LinkedList *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
LinkedList *middle = helper_findMiddle(head);
LinkedList *rightHead = middle->next;
LinkedList *leftHead = head;
middle->next = NULL;
leftHead = sort(leftHead);
rightHead = sort(rightHead);
return helper_merge(leftHead, rightHead);
}- Remove duplicates from a singly linkedlist
// remove duplicates from a singly linkedlist
LinkedList *removeDuplicates(LinkedList *head)
{
if (head == nullptr)
return nullptr; // Return nullptr for an empty list
LinkedList *temp = head;
while (temp != nullptr)
{
LinkedList *curr = temp;
while (curr->next != nullptr && curr->data == curr->next->data)
{
curr->next = curr->next->next; // Skip duplicates
}
temp = temp->next; // Move to the next unique element
}
return head; // Return the modified list
}