Skip to content

Instantly share code, notes, and snippets.

@J16N

J16N/doublyLinkedCircularLL.c

Created January 12, 2022 16:53
Show Gist options
  • Save J16N/7cc56418c92bec2a861a4f1963a27ada to your computer and use it in GitHub Desktop.
Save J16N/7cc56418c92bec2a861a4f1963a27ada to your computer and use it in GitHub Desktop.
Download ZIP
This is my implementation of Doubly Linked Circular Linked List
Raw
doublyLinkedCircularLL.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node {
int data;
struct node *next;
struct node *prev;
} NODE;
typedef struct list {
NODE *start;
NODE *end;
int length;
} CircList;
void menu(void);
int len(CircList *);
int normalize(int, int);
CircList *initCL(void);
void destroyCL(CircList *);
void insert(CircList *, int, int);
void insert_at_beginning(CircList *, int);
void insert_at_end(CircList *, int);
void delete(CircList *, int);
void delete_start(CircList *);
void delete_end(CircList *);
void displayCL(CircList *);
void flush(FILE *);
int main(void)
{
menu();
bool quit = false;
CircList *myList = initCL();
int data, choice, pos;
while (!quit) {
printf("\nChoice: ");
scanf("%d", &choice);
switch (choice) {
case 0:
quit = true;
break;
case 1:
displayCL(myList);
break;
case 2:
printf("Data: ");
scanf("%d", &data);
insert_at_beginning(myList, data);
break;
case 3:
printf("Data: ");
scanf("%d", &data);
insert_at_end(myList, data);
break;
case 4:
printf("Data: ");
scanf("%d", &data);
printf("Pos: ");
scanf("%d", &pos);
pos = normalize(pos, len(myList));
if (pos == 1)
insert_at_beginning(myList, data);
else
insert(myList, data, pos - 1);
break;
case 5:
delete_start(myList);
break;
case 6:
delete_end(myList);
break;
case 7:
printf("Pos: ");
scanf("%d", &pos);
delete(myList, pos);
break;
case 8:
printf("\n");
menu();
break;
default:
printf("Invalid Choice. Try again.\n");
break;
}
flush(stdin);
choice = -1;
}
destroyCL(myList);
return 0;
}
void menu(void)
{
printf("*****************************************************************\n");
printf("********** DOUBLY CIRCULAR LINKED LIST OPERATIONS *********\n");
printf("*****************************************************************\n");
printf("* <1> DISPLAY the List. *\n");
printf("* <2> INSERT data at BEGINNING. *\n");
printf("* <3> INSERT data at END. *\n");
printf("* <4> INSERT data at ANY position. *\n");
printf("* <5> DELETE data from BEGINNING. *\n");
printf("* <6> DELETE data from END. *\n");
printf("* <7> DELETE data from ANY position. *\n");
printf("* <8> DISPLAY this MENU. *\n");
printf("* <0> EXIT! *\n");
printf("*****************************************************************\n");
}
int len(CircList *cl)
{
return cl->length;
}
int normalize(int pos, int length)
{
int idx = pos > 0 ?
(pos - 1) % length :
(length - abs(pos) % length) % length;
return idx + 1;
}
CircList *initCL(void)
{
CircList *cl = malloc(sizeof(CircList));
cl->start = NULL;
cl->end = NULL;
cl->length = 0;
return cl;
}
void insert(CircList *cl, int data, int pos)
{
NODE *temp = malloc(sizeof(NODE));
temp->data = data;
temp->next = temp;
temp->prev = temp;
if (!cl->length) {
cl->start = temp;
cl->end = temp;
cl->length++;
return;
}
pos = normalize(pos, cl->length);
bool front = true;
NODE *node = NULL;
if (pos > cl->length / 2) {
node = cl->end;
front = false;
}
else {
node = cl->start;
}
for (int i = front ? 1 : cl->length; i != pos; front ? ++i : --i)
node = front ? node->next : node->prev;
temp->next = node->next;
node->next->prev = temp;
temp->prev = node;
node->next = temp;
cl->length++;
}
void insert_at_beginning(CircList *cl, int data)
{
insert(cl, data, -1);
if (cl->length > 1)
cl->start = cl->start->prev;
}
void insert_at_end(CircList *cl, int data)
{
insert(cl, data, -1);
if (cl->length > 1)
cl->end = cl->end->next;
}
void displayCL(CircList *cl)
{
printf("List: ");
NODE *node = cl->start;
int i = cl->length;
while (i--) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
void delete(CircList *cl, int pos)
{
if (!cl->length) return;
pos = normalize(pos, cl->length);
bool front = true;
NODE *node = NULL;
if (pos > cl->length / 2) {
node = cl->end;
front = false;
}
else {
node = cl->start;
}
if (pos == 1)
cl->start = cl->start->next;
if (pos == cl->length)
cl->end = cl->end->prev;
if (cl->length == 1) {
free(cl->start);
cl->start = NULL;
cl->end = NULL;
cl->length = 0;
return;
}
for (int i = front ? 1 : cl->length; i != pos; front ? ++i : --i)
node = front ? node->next : node->prev;
node->prev->next = node->next;
node->next->prev = node->prev;
cl->length--;
free(node);
}
void delete_start(CircList *cl)
{
delete(cl, 1);
}
void delete_end(CircList *cl)
{
delete(cl, -1);
}
void destroyCL(CircList *cl)
{
while (cl->start)
delete_start(cl);
free(cl);
}
void flush(FILE *in)
{
int ch;
clearerr(in);
do ch = getc(in);
while (ch != '\n' && ch != EOF);
clearerr(in);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment