Circular Linked List as an Abstract Data Type
User defined data type struct Node
Circular linked list is similar to simple linked list, the main difference is that the last node points to the first node and not to null.
struct Node{
int data;
struct Node *next;
}*Head;
Initialising the circular linked list using array
void create(int A[],int n){
int i;
struct Node *t,*last;
Head=(struct Node*)malloc(sizeof(struct Node));
Head->data=A[0];
Head->next=Head;
last=Head;
for(i=1;i<n;i++){
t=(struct Node*)malloc(sizeof(struct Node));
t->data=A[i];
t->next=last->next;
last->next=t;
last=t;
}
}
Displaying the circular linked list
void display(struct Node *h){
do{
printf("%d",h->data);
h=h->next;
}
while(h!=Head);
printf("\n");
}
Recursively displaying the circular linked list
void Rdisplay(struct Node *h){
static int flag=0;
if(h!=Head || flag==0){
flag=1;
printf("%d",h->data);
Rdisplay(h->next);
}
flag=0;
}
Length of the circular linked list
int Length(struct Node *p){
int l=0;
do{
l++;
p=p->next;
}
while (p!=Head);
return l;
}
Inserting a node in the circular linked list
void insert(struct Node *h, int key, int pos){
int i;
struct Node *t = (struct Node*)malloc(sizeof(struct Node));
if(pos>=0 && pos<=Length(h)){
if(pos == 0){
t->data=key;
if(Head==NULL){
Head = t;
Head->next = Head;
}
else{
while(h->next!=Head){
h=h->next;
}
t->next = Head;
h->next=t;
Head=t;
}
}
else{
for(i=0;i<pos-1;i++){
h=h->next;
}
t->data=key;
t->next=h->next;
h->next=t;
}
}
}
Deleting a node from the circular linked list
int delete(struct Node* p, int pos){
int x=-1,i;
struct Node *q;
if(pos<0 || pos>Length(p)){
return -1;
}
else{
if(pos==1){
x=Head->data;
while(p->next!=Head){
p=p->next;
}
if(Head==p){
free(Head);
Head=NULL;
}
else{
p->next=Head->next;
free(Head);
Head=p->next;
}
}
else{
for(i=0;i<pos-2;i++){
p=p->next;
}
q=p->next;
x=q->data;
p->next=q->next;
free(q);
}
return x;
}
}