Write a c program to remove duplicate elements from a circular doubly linked list ?
Answers
#include <stdio.h>
//Represent a node of the doubly linked list
struct node{
int data;
struct node *previous;
struct node *next;
};
//Represent the head and tail of the doubly linked list
struct node *head, *tail = NULL;
//addNode() will add a node to the list
void addNode(int data) {
//Create a new node
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
//If list is empty
if(head == NULL) {
//Both head and tail will point to newNode
head = tail = newNode;
//head's previous will point to NULL
head->previous = NULL;
//tail's next will point to NULL, as it is the last node of the list
tail->next = NULL;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail->next = newNode;
//newNode's previous will point to tail
newNode->previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to NULL
tail->next = NULL;
}
}
//removeDuplicateNode() will remove duplicate nodes from the list
void removeDuplicateNode() {
//Node current will point to head
struct node *current, *index, *temp;
//Checks whether list is empty
if(head == NULL) {
return;
}
else {
//Initially, current will point to head node
for(current = head; current != NULL; current = current->next) {
//index will point to node next to current
for(index = current->next; index != NULL; index = index->next) {
if(current->data == index->data) {
//Store the duplicate node in temp
temp = index;
//index's previous node will point to node next to index thus, removes the duplicate node
index->previous->next = index->next;
if(index->next != NULL)
index->next->previous = index->previous;
//Delete duplicate node by making temp to NULL
temp = NULL;
}
}
}
}
}
//display() will print out the nodes of the list
void display() {
//Node current will point to head
struct node *current = head;
if(head == NULL) {
printf("List is empty\n");
return;
}
while(current != NULL) {
//Prints each node by incrementing pointer.
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main()
{
//Add nodes to the list
addNode(1);
addNode(2);
addNode(3);
addNode(2);
addNode(2);
addNode(4);
addNode(5);
addNode(3);
printf("Originals list: \n");
display();
//Removes duplicate nodes
removeDuplicateNode();
printf("List after removing duplicates: \n");
display();
return 0;
}
REMOVE DUPLICATE ELEMENT FROM A CIRCULAR ELEMENT FROM A CIRCULAR DOUBLY LINKED LIST
Explanation:
In this program, we will create a doubly linked list and remove the duplicate, if present, by traversing through the list.
PROGRAM:-
// Include header file
#include <stdio.h>
#include <stdlib.h>
// C program for
// Linked list node
typedef struct LinkNode
{
// Define useful field of LinkNode
int data;
struct LinkNode * next;
struct LinkNode * prev;
}LinkNode;
LinkNode * getLinkNode(int data)
{
// Create dynamic memory of LinkNode
LinkNode * ref = (LinkNode * ) malloc(sizeof(LinkNode));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->data = data;
ref->next = NULL;
ref->prev = NULL;
return ref;
}
typedef struct DoublyLinkedList
{
// Define useful field of DoublyLinkedList
struct LinkNode * head;
struct LinkNode * tail;
}DoublyLinkedList;
DoublyLinkedList * getDoublyLinkedList()
{
// Create dynamic memory of DoublyLinkedList
DoublyLinkedList * ref = (DoublyLinkedList * ) malloc(sizeof(DoublyLinkedList));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
// Set head and tail value
ref->head = NULL;
ref->tail = NULL;
return ref;
}
// Insert new node at end position
void insert(DoublyLinkedList * ref, int value)
{
// Create a node
LinkNode * node = getLinkNode(value);
if (ref->head == NULL)
{
// Add first node
ref->head = node;
ref->tail = node;
return;
}
// Add node at last position
ref->tail->next = node;
node->prev = ref->tail;
// Get new last node
ref->tail = node;
}
// Display node element of doubly linked list
void display(DoublyLinkedList * ref)
{
if (ref->head == NULL)
{
printf("Empty Linked List");
}
else
{
printf("Linked List Head to Tail :");
// Get first node of linked list
LinkNode * temp = ref->head;
// iterate linked list
while (temp != NULL)
{
// Display node value
printf(" %d ", temp->data);
// Visit to next node
temp = temp->next;
}
printf("\nLinked List Tail to Head :");
// Get last node of linked list
temp = ref->tail;
// iterate linked list
while (temp != NULL)
{
// Display node value
printf(" %d ", temp->data);
// Visit to prev node
temp = temp->prev;
}
}
}
// Delete duplicates from doubly linked list
void removeNode(DoublyLinkedList * ref)
{
if (ref->head != NULL)
{
LinkNode * current = ref->head;
LinkNode * temp = NULL;
LinkNode * find = NULL;
while (current != NULL)
{
// Visit to next node
temp = current->next;
while (temp != NULL)
{
// Check node is duplicate or not
if (temp->data == current->data)
{
find = temp;
}
// Visit to next node
temp = temp->next;
if (find != NULL)
{
// When find deleted node
if (find->prev != NULL)
{
find->prev->next = temp;
}
if (temp != NULL)
{
temp->prev = find->prev;
}
if (find == ref->tail)
{
// When remove last node
ref->tail = find->prev;
}
find->prev = NULL;
find->next = NULL;
find = NULL;
}
}
// Visit to next node
current = current->next;
}
}
}
int main()
{
DoublyLinkedList * dll = getDoublyLinkedList();
// Insert following linked list nodes
insert(dll, 1);
insert(dll, 1);
insert(dll, 4);
insert(dll, 6);
insert(dll, 6);
insert(dll, 6);
insert(dll, 7);
insert(dll, 8);
insert(dll, 1);
printf("Before delete duplicates \n");
// Display all node
display(dll);
removeNode(dll);
printf("\nAfter delete duplicates \n");
display(dll);
}