// C++ program to illustrate inserting a Node in Show // a Circular Doubly Linked list in begging, end // and middle #include <bits/stdc++.h> using namespace std; // Structure of a Node struct Node { int data; struct Node *next; struct Node *prev; }; // Function to insert at the end void insertEnd[struct Node** start, int value] { // If the list is empty, create a single node // circular and doubly list if [*start == NULL] { struct Node* new_node = new Node; new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } // If list is not empty /* Find last node */ Node *last = [*start]->prev; // Create Node dynamically struct Node* new_node = new Node; new_node->data = value; // Start is going to be next of new_node new_node->next = *start; // Make new node previous of start [*start]->prev = new_node; // Make last previous of new node new_node->prev = last; // Make new node next of old last last->next = new_node; } // Function to insert Node at the beginning // of the List, void insertBegin[struct Node** start, int value] { // Pointer points to last Node struct Node *last = [*start]->prev; struct Node* new_node = new Node; new_node->data = value; // Inserting the data // setting up previous and next of new node new_node->next = *start; new_node->prev = last; // Update next and previous pointers of start // and last. last->next = [*start]->prev = new_node; // Update start pointer *start = new_node; } // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 void insertAfter[struct Node** start, int value1, int value2] { struct Node* new_node = new Node; new_node->data = value1; // Inserting the data // Find node having value2 and next node of it struct Node *temp = *start; while [temp->data != value2] temp = temp->next; struct Node *next = temp->next; // insert new_node between temp and next. temp->next = new_node; new_node->prev = temp; new_node->next = next; next->prev = new_node; } void display[struct Node* start] { struct Node *temp = start; printf["\nTraversal in forward direction \n"]; while [temp->next != start] { printf["%d ", temp->data]; temp = temp->next; } printf["%d ", temp->data]; printf["\nTraversal in reverse direction \n"]; Node *last = start->prev; temp = last; while [temp->prev != last] { printf["%d ", temp->data]; temp = temp->prev; } printf["%d ", temp->data]; } /* Driver program to test above functions*/ int main[] { /* Start with the empty list */ struct Node* start = NULL; // Insert 5. So linked list becomes 5->NULL insertEnd[&start, 5]; // Insert 4 at the beginning. So linked // list becomes 4->5 insertBegin[&start, 4]; // Insert 7 at the end. So linked list // becomes 4->5->7 insertEnd[&start, 7]; // Insert 8 at the end. So linked list // becomes 4->5->7->8 insertEnd[&start, 8]; // Insert 6, after 5. So linked list // becomes 4->5->6->7->8 insertAfter[&start, 6, 5]; printf["Created circular doubly linked list is: "]; display[start]; return 0; }
Before you learn about the type of the linked list, make sure you know about the LinkedList Data Structure. There are three common types of Linked List.
Singly Linked ListIt is the most common. Each node has data and a pointer to the next node. Singly linked listNode is represented as: struct node { int data; struct node *next; }A three-member singly linked list can be created as: /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;Doubly Linked ListWe add a pointer to the previous node in a doubly-linked list. Thus, we can go in either direction: forward or backward. Doubly linked listA node is represented as struct node { int data; struct node *next; struct node *prev; }A three-member doubly linked list can be created as /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;If you want to learn more about it, please visit doubly linked list and operations on it. Circular Linked ListA circular linked list is a variation of a linked list in which the last element is linked to the first element. This forms a circular loop. Circular linked listA circular linked list can be either singly linked or doubly linked.
A three-member circular singly linked list can be created as: /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;If you want to learn more about it, please visit circular linked list and operations on it.
The doubly circular linked list has the features of both the circular linked list and doubly linked list. The main difference between the doubly linked list and doubly circular linked list is that the doubly circular linked list does not contain the NULL value in the previous field of the node. What is circular singly linked list?In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes. What do you mean by circular linked list?Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. 1) Any node can be a starting point. We can traverse the whole list by starting from any point. Which is better doubly linked list or circular linked list? Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient. Why do we need circular linked list? Circular linked lists (singly or doubly) are useful for applications that need to visit each node equally and the lists could grow. If the size of the list if fixed, it is much more efficient (speed and memory) to use circular queue. What is the real life example of circular linked list?The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. What are the disadvantages of circular linked list?Disadvantages of a circular linked list
What is the advantage of circular linked list?Some of the advantages of circular linked lists are: No requirement for a NULL assignment in the code. The circular list never points to a NULL pointer unless fully deallocated. Circular linked lists are advantageous for end operations since beginning and end coincide.
|