In: Computer Science
The following is a code to delete the first occurence of the key in a singly linked list. The language is c++.
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
// A linked list node
class Node{
public:
int data;
Node* next;
};
// push a new node to the linked list
void push(Node** head, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head);
(*head) = new_node;
}
//function to delete the first occurence of the linked list
void deleteNode(Node** head, int key)
{
// Store head node
Node* temp = *head;
Node* prev = NULL;
// If head node itself is the key
if (temp != NULL && temp->data == key)
{
*head = temp->next; // Changed head
delete temp; // free old head
return;
}
// Else Search for the key to be deleted,
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL)
return;
// Unlink the node from linked list
prev->next = temp->next;
delete temp;
}
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
int size(Node* head)
{
int size = 0; // Initialize size
Node* current = head; // Initialize current
while (current != NULL)
{
size++;
current = current->next;
}
return size;
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
//push the elements to the linked list
push(&head, 4);
push(&head, 2);
push(&head, 3);
push(&head, 8);
push(&head, 3);
puts("The linked list ");
printList(head);
deleteNode(&head, 3);
puts("\nLinked List after Deletion: "); //after deletion of first occurence of number 3
printList(head);
cout<<"\nsize of the list is "<< size(head); //print the size of the linked list
return 0;
}
Output :
* Doubly Linked List:
Code :
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
/* Function to push a node at beginning */
void push(struct Node** head, int data)
{
struct Node* curr = new Node;
curr->data = data;
curr->next = NULL;
if(*head == NULL)
*head=curr; //If this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
}
//display linked list
void print(struct Node**head)
{
struct Node *temp= *head;
while(temp!=NULL)
{
if(temp->next!=NULL)
{
cout<<temp->data<<"->";
}
else
{
cout<<temp->data;
}
temp=temp->next; //move to next node
}
cout<<endl;
}
void deleteFirstOccurence(struct Node** head, int key)
{
// Initialize previous of Node to be deleted
struct Node* x = NULL;
struct Node* temp = *head;
while(temp!=NULL && temp->data != key)
{
x = temp;
temp = temp->next;
}
//key occurs atleast once except head node
if(x)
{
//delete x by copying of next to it.
//delete next
temp = x->next;
x->next = x->next->next;
delete temp;
}
//key occurs at head
else
{
if (*head && (*head)->data == key )
{
struct Node * temp = *head;
*head = (*head)->next;
delete temp;
}
}
}
//Main function
int main()
{
struct Node* head = NULL;//Initial empty List
push(&head, 14);
push(&head, 11);
push(&head, 3);
push(&head, 10);
push(&head, 4);
push(&head, 1);
push(&head, 3);
push(&head, 2);
push(&head, 7);
cout<<"Doubly linked list ";
print(&head);
deleteFirstOccurence(&head, 3);
cout<<"\nAfter deleting first occurence of 3 \n";
print(&head);
return 0;
}
Output: