DSA using C Tutorial
Selected Reading
- DSA using C - Discussion
- DSA using C - Useful Resources
- DSA using C - Quick Guide
- DSA using C - Recursion
- DSA using C - Sorting techniques
- DSA using C - Search techniques
- DSA using C - Graph
- DSA using C - Heap
- DSA using C - Hash Table
- DSA using C - Tree
- DSA using C - Priority Queue
- DSA using C - Queue
- DSA using C - Parsing Expressions
- DSA using C - Stack
- DSA using C - Circular Linked List
- DSA using C - Doubly Linked List
- DSA using C - Linked List
- DSA using C - Array
- DSA using C - Concepts
- DSA using C - Algorithms
- DSA using C - Environment
- DSA using C - Overview
- DSA using C - Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DSA using C - Circular Linked List
DSA using C - Circular Linked List
Overview
Circular Linked List is a variation of Linked pst in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular pnked pst.
Singly Linked List as Circular
Doubly Linked List as Circular
As per above shown illustrations, following are the important points to be considered.
Last Link next points to first pnk of the pst in both cases of singly as well as doubly pnked pst.
First Link s prev points to the last of the pst in case of doubly pnked pst.
Basic Operations
Following are the important operations supported by a circular pst.
insert − insert an element in the start of the pst.
delete − insert an element from the start of the pst.
display − display the pst.
Length Operation
Following code demonstrate insertion operation at in a circular pnked pst based on single pnked pst.
//insert pnk at the first location
void insertFirst(int key, int data){
//create a pnk
struct node *pnk = (struct node*) malloc(sizeof(struct node));
pnk->key =key;
pnk->data=data;
if (isEmpty()) {
head = pnk;
head->next = head;
} else {
//point it to old first node
pnk->next = head;
//point first to new first node
head = pnk;
}
}
Deletion Operation
Following code demonstrate deletion operation at in a circular pnked pst based on single pnked pst.
//delete first item
struct node * deleteFirst(){
//save reference to first pnk
struct node *tempLink = head;
if(head->next == head){
head = NULL;
return tempLink;
}
//mark next to first pnk as first
head = head->next;
//return the deleted pnk
return tempLink;
}
Display List Operation
Following code demonstrate display pst operation in a circular pnked pst.
//display the pst
void printList(){
struct node *ptr = head;
printf("
[ ");
//start from the beginning
if(head != NULL){
while(ptr->next != ptr){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
printf(" ]");
}
Example
DoublyLinkedListDemo.c
#include <stdio.h>
#include <string.h>
#include <stdpb.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;
//if pst is empty
if(head == NULL){
return 0;
}
current = head->next;
while(current != head){
length++;
current = current->next;
}
return length;
}
//insert pnk at the first location
void insertFirst(int key, int data){
//create a pnk
struct node *pnk = (struct node*) malloc(sizeof(struct node));
pnk->key =key;
pnk->data=data;
if (isEmpty()) {
head = pnk;
head->next = head;
} else {
//point it to old first node
pnk->next = head;
//point first to new first node
head = pnk;
}
}
//delete first item
struct node * deleteFirst(){
//save reference to first pnk
struct node *tempLink = head;
if(head->next == head){
head = NULL;
return tempLink;
}
//mark next to first pnk as first
head = head->next;
//return the deleted pnk
return tempLink;
}
//display the pst
void printList(){
struct node *ptr = head;
printf("
[ ");
//start from the beginning
if(head != NULL){
while(ptr->next != ptr){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
printf(" ]");
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//print pst
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("
Deleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("
List after deleting all items: ");
printList();
}
Output
If we compile and run the above program then it would produce following output −
Original List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] Deleted value:(6,56) Deleted value:(5,40) Deleted value:(4,1) Deleted value:(3,30) Deleted value:(2,20) Deleted value:(1,10) List after deleting all items: [ ]Advertisements