Singly LinkedList

Node Class
class Node {
public:
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};

1. class Node {: This line defines a class named Node.

2. public:: This keyword makes the following members accessible
from outside the class.
3. int data;: This declares an integer variable data to store the value
of the node.
4. Node next;*: This declares a pointer next to point to the next node in
the list.
5. Node(int data) : data(data), next(nullptr) {}: This is a
constructor that initializes the data with the given value and
sets next to nullptr (indicating the end of the list).

LinkedList Class
class LinkedList {
Node* head;
public:
LinkedList() : head(nullptr) {}
void insertAtHead(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
}
void print() {
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

1. class LinkedList {: This line defines a class named LinkedList.

2. Node head;*: This declares a pointer head to point to the first node in
the list.
3. public:: This keyword makes the following members accessible
from outside the class.
4. LinkedList() : head(nullptr) {}: This is a constructor that
initializes head to nullptr, indicating an empty list.
 5. void insertAtHead(int data) {: This function inserts a new node
at the beginning of the list.
o Node newNode = new Node(data);*: Creates a new node with
the given data.
o newNode->next = head;: Sets the next of the new node to
the current head.
o head = newNode;: Updates head to point to the new node.
6. void print() {: This function prints all the elements in the list.
o Node temp = head;*: Initializes a temporary
pointer temp to head.
o while (temp) {: Loops through the list until temp is nullptr.
 cout << temp->data << " ";: Prints the data of the
current node.
 temp = temp->next;: Moves to the next node.
o cout << endl;: Prints a newline after printing all the
elements.

Main Function
int main() {
LinkedList list;
list.insertAtHead(4);
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.print();
return 0;
}

1. int main() {: This is the main function where the program

execution begins.
2. LinkedList list;: Creates an instance of LinkedList.
3. list.insertAtHead(4);: Inserts 4 at the head of the list.
4. list.insertAtHead(3);: Inserts 3 at the head of the list.
5. list.insertAtHead(2);: Inserts 2 at the head of the list.
6. list.insertAtHead(1);: Inserts 1 at the head of the list.
7. list.print();: Prints the elements of the list, which will be 1 2 3 4.
Singly Linked List operations

Class Definition
class node {
public:
int data;
node* next;

node(int val) {
data = val;
next = NULL;
}
};

 class node {: Defines a class named node that will be used to create nodes in a
linked list.
 public:: Access specifier that makes the following members accessible from outside
the class.
 int data;: A variable to store the data of the node.
 node* next;: A pointer to the next node in the linked list.
 node(int val) {: A constructor for the node class that initializes a new node with a
given value.
 data = val;: Sets the data of the node to the passed value val.
 next = NULL;: Initializes the next pointer to NULL, indicating the end of the list or
that the node does not point to another node yet.
 }: End of the constructor definition.
 };: End of the node class definition.

Insert Functions

Insert at Head

void insertAtHead(node* &head, int val) {

node* n = new node(val);
n->next = head;
head = n;
}

 void insertAtHead(node* &head, int val) {: Defines a function to insert a new

node with value val at the head of the list.
 node* n = new node(val);: Creates a new node n with the value val.
 n->next = head;: Sets the next pointer of the new node to the current head, so it
will point to the rest of the list.
 head = n;: Updates the head of the list to the new node, making it the new head.
 }: End of the function.
Insert at Tail

void insertAtTail(node* &head, int val) {

node* n = new node(val);
if (head == NULL) {
head = n;
return;
}
node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
}

 void insertAtTail(node* &head, int val) {: Defines a function to insert a new

node with value val at the end of the list.
 node* n = new node(val);: Creates a new node n with the value val.
 if (head == NULL) {: Checks if the list is empty.
 head = n;: If the list is empty, sets the new node as the head of the list.
 return;: Exits the function since the new node is now the head.
 node* temp = head;: Creates a temporary pointer temp to traverse the list.
 while (temp->next != NULL) {: Traverses the list to find the last node.
 temp = temp->next;: Moves to the next node.
 temp->next = n;: Sets the next pointer of the last node to the new node.
 }: End of the function.

Insert at Position

void insertAtPosition(node* &head, int position, int val) {

if (position < 0) {
cout << "Invalid position!" << endl;
return;
}

if (position == 0) {
insertAtHead(head, val);
return;
}

node* n = new node(val);

node* temp = head;

for (int i = 0; i < position - 1; i++) {

if (temp == NULL) {
cout << "Position out of bounds!" << endl;
delete n;
return;
}
temp = temp->next;
}

if (temp == NULL) {
cout << "Position out of bounds!" << endl;
 delete n;
return;
}

n->next = temp->next;
temp->next = n;
}

 void insertAtPosition(node* &head, int position, int val) {: Defines a

function to insert a new node with value val at a specified position.
 if (position < 0) {: Checks if the position is negative.
 cout << "Invalid position!" << endl;: Prints an error message if the position is
invalid.
 return;: Exits the function.
 if (position == 0) {: Checks if the position is 0 (i.e., inserting at the head).
 insertAtHead(head, val);: Calls the insertAtHead function to insert the node at
the head.
 return;: Exits the function.
 node* n = new node(val);: Creates a new node n with the value val.
 node* temp = head;: Creates a temporary pointer temp to traverse the list.
 for (int i = 0; i < position - 1; i++) {: Loops to find the node just before
the specified position.
 if (temp == NULL) {: Checks if temp is NULL (i.e., position is out of bounds).
 cout << "Position out of bounds!" << endl;: Prints an error message if the
position is out of bounds.
 delete n;: Deletes the newly created node.
 return;: Exits the function.
 temp = temp->next;: Moves to the next node.
 if (temp == NULL) {: Checks if temp is NULL (i.e., position is out of bounds).
 n->next = temp->next;: Sets the next pointer of the new node to the node after
temp.
 temp->next = n;: Sets the next pointer of temp to the new node.
 }: End of the function.

Display Function
void display(node* head) {
node* temp = head;
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}

 void display(node* head) {: Defines a function to print all nodes in the list.
 node* temp = head;: Creates a temporary pointer temp to traverse the list.
 while (temp != NULL) {: Loops through each node in the list.
 cout << temp->data << " -> ";: Prints the data of the current node followed by
an arrow.
 temp = temp->next;: Moves to the next node.
 cout << "NULL" << endl;: Prints "NULL" to indicate the end of the list.
  }: End of the function.

Search Function
bool search(node* head, int key) {
node* temp = head;
while (temp != NULL) {
if (temp->data == key) {
return true;
}
temp = temp->next;
}
return false;
}

 bool search(node* head, int key) {: Defines a function to search for a node
with a specific key.
 node* temp = head;: Creates a temporary pointer temp to traverse the list.
 while (temp != NULL) {: Loops through each node in the list.
 if (temp->data == key) {: Checks if the current node's data matches the key.
 return true;: Returns true if the key is found.
 temp = temp->next;: Moves to the next node.
 return false;: Returns false if the key is not found in the list.
 }: End of the function.

Main Function
int main() {
node* head = NULL;
insertAtTail(head, 1);
insertAtTail(head, 2);
insertAtTail(head, 3);
insertAtTail(head, 4);
insertAtTail(head, 5);
display(head);

insertAtHead(head, 4);
display(head);

insertAtPosition(head, 3, 10); // Insert 10 at position 3

display(head);

insertAtPosition(head, 0, 20); // Insert 20 at position 0

display(head);

insertAtPosition(head, 10, 30); // Try to insert 30 at an out-of-bounds

position
display(head);

cout << (search(head, 5) ? "Found" : "Not Found") << endl;

return 0;
}

 int main() {: Defines the main function, the entry point of the program.
 node* head = NULL;: Initializes the head of the linked list to NULL (empty list).
 insertAtTail(head, 1);: Inserts 1 at the end of the list.
 insertAtTail(head, 2);: Inserts 2 at the end of the list.
 insertAtTail(head, 3);: Inserts 3 at the end of the list.
 insertAtTail(head, 4);: Inserts 4 at the end of the list.
 insertAtTail(head, 5);: Inserts 5 at the end of the list.
 display(head);: Displays the current state of the list.
 insertAtHead(head, 4);: Inserts 4 at the head of the list.
 display(head);: Displays the updated list.
 insertAtPosition(head, 3, 10);: Inserts 10 at position 3 in the list.
 display(head);: Displays the updated list.
 insertAtPosition(head, 0, 20);: Inserts 20 at position 0 (head) in the list.
 display(head);: Displays the updated list.
 insertAtPosition(head, 10, 30);: Attempts to insert 30 at position 10, which is
out of bounds.
 display(head);: Displays the list (unchanged after the out-of-bounds attempt).
 cout << (search(head, 5) ? "Found" : "Not Found") << endl;: Searches for
the value 5 in the list and prints "Found" or "Not Found".
 return 0;: Exits the program with a status code of 0, indicating successful
execution.
 }: End of the main function.
Doubly LinkedList(all basic operation):

#include <iostream>
using namespace std;

class node {
public:
int data;
node* next;
node* prev;

node(int val) {
data = val;
next = NULL;
prev = NULL;
}
};

1. #include <iostream>: Includes the input/output stream library necessary for

printing to the console.
2. using namespace std;: Allows us to use standard C++ library names without the
std:: prefix.
3. class node: Defines a doubly linked list node class.
o int data;: Stores the value of the node.
o node* next;: Pointer to the next node in the list.
o node* prev;: Pointer to the previous node in the list.
o node(int val): Constructor to initialize a node with a value and set next and
prev to NULL.

Insertions
void insertAtHead(node* &head, int val) {
node* n = new node(val);
n->next = head;
if (head != NULL) {
 head->prev = n;
}
head = n;
cout << "Inserted " << val << " at head." << endl;
}

1. node* n = new node(val);: Creates a new node with the value val.
2. n->next = head;: Sets the new node's next pointer to the current head of the list.
3. if (head != NULL) { head->prev = n; }: Updates the previous head node's
prev pointer to the new node if the list is not empty.
4. head = n;: Updates the head pointer to the new node.
5. cout << "Inserted " << val << " at head." << endl;: Prints a message
indicating the insertion.

void insertAtTail(node* &head, int val) {

if (head == NULL) {
insertAtHead(head, val);
cout << "Inserted " << val << " at tail (which was also the head)."
<< endl;
return;
}
node* n = new node(val);
node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
n->prev = temp;
cout << "Inserted " << val << " at tail." << endl;
}

1. if (head == NULL) { insertAtHead(head, val); ... return; }: If the list is

empty, calls insertAtHead to handle insertion.
2. node* n = new node(val);: Creates a new node for the tail insertion.
3. node* temp = head;: Initializes a temporary pointer to traverse the list.
4. while (temp->next != NULL) { temp = temp->next; }: Moves the temp pointer
to the last node.
5. temp->next = n;: Sets the last node's next to the new node.
6. n->prev = temp;: Sets the new node's prev to the last node.
7. cout << "Inserted " << val << " at tail." << endl;: Prints a message
indicating the insertion.

void insertAtPosition(node* &head, int pos, int val) {

if (pos == 1) {
insertAtHead(head, val);
cout << "Inserted " << val << " at position " << pos << " (head)."
<< endl;
return;
}

node* temp = head;

int count = 1;
while (temp != NULL && count < pos - 1) {
temp = temp->next;
count++;
}
 if (temp == NULL) {
cout << "Position " << pos << " is out of bounds." << endl;
return;
}

node* n = new node(val);

n->next = temp->next;
if (temp->next != NULL) {
temp->next->prev = n;
}
temp->next = n;
n->prev = temp;
cout << "Inserted " << val << " at position " << pos << "." << endl;
}

1. if (pos == 1) { insertAtHead(head, val); ... return; }: If inserting at

position 1, calls insertAtHead.
2. node* temp = head; int count = 1;: Initializes temp for traversal and count to
keep track of the position.
3. while (temp != NULL && count < pos - 1) { temp = temp->next; count++;
}: Traverses to the node before the desired position.
4. if (temp == NULL) { cout << "Position " << pos << " is out of
bounds." << endl; return; }: Checks if the position is valid.
5. node* n = new node(val);: Creates a new node for insertion.
6. n->next = temp->next; if (temp->next != NULL) { temp->next->prev = n;
}: Updates pointers to insert the new node in the list.
7. temp->next = n; n->prev = temp;: Updates the previous and next pointers to
insert the new node.
8. cout << "Inserted " << val << " at position " << pos << "." << endl;:
Prints a message indicating the insertion.

Display Function
void display(node* head) {
if (head == NULL) {
cout << "The list is empty." << endl;
return;
}

node* temp = head;

cout << "List: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

1. if (head == NULL) { cout << "The list is empty." << endl; return; }:
Checks if the list is empty and prints a message if it is.
2. node* temp = head;: Initializes temp to traverse the list.
3. cout << "List: ";: Prints a prefix message for the list contents.
4. while (temp != NULL) { cout << temp->data << " "; temp = temp-
>next; }: Prints each node's data and moves to the next node.
 5. cout << endl;: Moves to the next line after displaying the list.

Deletion Functions
void deleteAtHead(node* &head) {
if (head == NULL) {
cout << "Nothing to delete at head (the list is empty)." << endl;
return;
}

node* toDelete = head;

head = head->next;
if (head != NULL) {
head->prev = NULL;
}
delete toDelete;
cout << "Deleted node at head." << endl;
}

1. if (head == NULL) { cout << "Nothing to delete at head (the list is

empty)." << endl; return; }: Checks if the list is empty and prints a message if
it is.
2. node* toDelete = head;: Points to the head node for deletion.
3. head = head->next;: Moves the head pointer to the next node.
4. if (head != NULL) { head->prev = NULL; }: Updates the new head's prev
pointer to NULL.
5. delete toDelete;: Deletes the old head node.
6. cout << "Deleted node at head." << endl;: Prints a message indicating the
deletion.

void deleteAtTail(node* &head) {

if (head == NULL) {
cout << "Nothing to delete at tail (the list is empty)." << endl;
return;
}

if (head->next == NULL) {
deleteAtHead(head);
cout << "Deleted node at tail (which was also the head)." << endl;
return;
}

node* temp = head;

while (temp->next->next != NULL) {
temp = temp->next;
}

node* toDelete = temp->next;

temp->next = NULL;
delete toDelete;
cout << "Deleted node at tail." << endl;
}

1. if (head == NULL) { cout << "Nothing to delete at tail (the list is

empty)." << endl; return; }: Checks if the list is empty and prints a message if
it is.
 2. if (head->next == NULL) { deleteAtHead(head); ... return; }: If there is
only one node, calls deleteAtHead.
3. node* temp = head;: Initializes temp for traversal.
4. while (temp->next->next != NULL) { temp = temp->next; }: Traverses to the
second-to-last node.
5. node* toDelete = temp->next;: Points to the last node for deletion.
6. temp->next = NULL;: Updates the second-to-last node’s next to NULL.
7. delete toDelete;: Deletes the last node.
8. cout << "Deleted node at tail." << endl;: Prints a message indicating the
deletion.

void deleteAtPosition(node* &head, int pos) {

if (head == NULL) {
cout << "Nothing to delete at position " << pos << " (the list is
empty)." << endl;
return;
}

if (pos == 1) {
deleteAtHead(head);
cout << "Deleted node at position " << pos << " (head)." << endl;
return;
}

node* temp = head;

int count = 1;
while (temp != NULL && count != pos) {
temp = temp->next;
count++;
}

if (temp == NULL) {
cout << "Position " << pos << " is out of bounds." << endl;
return;
}

if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}

delete temp;
cout << "Deleted node at position " << pos << "." << endl;
}

1. if (head == NULL) { cout << "Nothing to delete at position " << pos
<< " (the list is empty)." << endl; return; }: Checks if the list is empty
and prints a message if it is.
2. if (pos == 1) { deleteAtHead(head); ... return; }: If deleting at position
1, calls deleteAtHead.
3. node* temp = head; int count = 1;: Initializes temp for traversal and count for
position tracking.
4. while (temp != NULL && count != pos) { temp = temp->next; count++; }:
Traverses to the node at the specified position.
 5. if (temp == NULL) { cout << "Position " << pos << " is out of
bounds." << endl; return; }: Checks if the position is valid.
6. if (temp->prev != NULL) { temp->prev->next = temp->next; }: Updates the
previous node’s next pointer.
7. if (temp->next != NULL) { temp->next->prev = temp->prev; }: Updates the
next node’s prev pointer.
8. delete temp;: Deletes the node at the specified position.
9. cout << "Deleted node at position " << pos << "." << endl;: Prints a
message indicating the deletion.

Main Function
int main() {
node* head = NULL;

insertAtTail(head, 1);
insertAtTail(head, 2);
insertAtTail(head, 3);
insertAtTail(head, 4);
display(head);

insertAtHead(head, 5);
display(head);

insertAtPosition(head, 3, 6); // Insert 6 at position 3

display(head);

deleteAtTail(head); // Delete last node

display(head);

deleteAtPosition(head, 5); // Delete node at position 5

deleteAtPosition(head, 2); // Delete node at position 2
display(head);

return 0;
}

1. node* head = NULL;: Initializes the head of the list as NULL (empty list).
2. insertAtTail(head, 1); ...: Inserts nodes into the list and displays the list after
each operation.
3. insertAtHead(head, 5); ...: Inserts a node at the head and displays the list.
4. insertAtPosition(head, 3, 6);: Inserts a node at position 3 and displays the list.
5. deleteAtTail(head);: Deletes the last node and displays the list.
6. deleteAtPosition(head, 5); deleteAtPosition(head, 2);: Deletes nodes at
specific positions and displays the list.
7. return 0;: Ends the main function and returns 0 to indicate successful completion.