i was exercising with circularly lists and reading about doubly linked lists, now i decided to implement circularly doubly linked list. If someone is interested you may just take a slight look, i finished code right now, probably there is something to optimize... here it goes:
Code:
/* Circularly-Doubly Linked List (CDLL) */
#include <stdio.h>
#include <stdlib.h>
#define snapd(expr) printf(#expr " = %d\n", expr);
#define snapf(expr) printf(#expr " = %f\n", expr);
struct cell
{
int data;
struct cell *prev;
struct cell *next;
};
struct cell *insert(struct cell *list, int value)
{
struct cell *newnode, *current = list;
if (list == NULL)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->prev = NULL;
newnode->next = NULL;
newnode->data = value;
return newnode;
}
//if CDLL has only one element
if (list->next == NULL && list->prev == NULL)
{
if(value != list->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->prev = list;
newnode->next = list;
newnode->data = value;
list->prev = newnode;
list->next = newnode;
if (value > list->data)
return current;
else
if (value < list->data)
return newnode;
}
if (value == list->data)
{
printf("The value %d already exists in CDLL!\n", value);
return current;
}
}
//handle two elements situation
if (list->next->next == list)
{
//value is less than first element
if (value < list->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->next = current;
newnode->prev = current->next;
newnode->data = value;
list->prev = newnode;
list->next->next = newnode;
return newnode;
}
//value is more than first element but less than second element
if (value > list->data && value < list->next->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->next = current->next;
newnode->prev = current;
newnode->data = value;
list->next = newnode;
list->next->prev = newnode;
return current;
}
//value is more than second element
if (value > list->next->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->next = current;
newnode->prev = list->next;
newnode->data = value;
list->prev = newnode;
list->next->next = newnode;
return current;
}
if (value == list->data || value == list->next->data)
{
printf("The value %d already exists in CDLL!\n", value);
return current;
}
}
if (value < list->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->data = value;
newnode->next = list;
newnode->prev = list->prev;
//modify last
list->prev->next = newnode;
//modify second
list->prev = newnode;
return newnode;
}
if (value == list->data)
{
printf("The value %d already exists in CDLL!\n", value);
return current;
}
while (list->next != current)
{
if (value > list->data && value < list->next->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->data = value;
newnode->prev = list;
newnode->next = list->next;
list->next->prev = newnode;
list->next = newnode;
return current;
}
if (value == list->data)
{
printf("The value %d already exists in CDLL!\n", value);
return current;
}
list = list->next;
}
//handle adding at the end
if (value > list->data)
{
newnode = (struct cell *)malloc(sizeof(struct cell));
newnode->data = value;
newnode->next = current;
newnode->prev = list;
list->next = newnode;
current->prev = newnode;
return current;
}
if (value == list->data)
{
printf("The value %d already exists in CDLL!\n", value);
return current;
}
}
struct cell *removecell(struct cell *list, int value)
{
struct cell *current = list, *second = list->next;
if (list == NULL)
{
printf("The CDLL is already empty!\n");
return NULL;
}
//if CDLL has only one element
if (list->next == NULL && list->prev == NULL && value == list->data)
{
free(list);
return NULL;
}
else
if (list->next == NULL && list->prev == NULL && value != list->data)
{
printf("there is no value %d to delete!\n", value);
return current;
}
//handle first element in case of just two elements
if (value == list->data && list->next->next == list)
{
current = list->next;
current->next = NULL;
current->prev = NULL;
free(list);
return current;
}
//delete first element
if (value == list->data)
{
list->next->prev = list->prev;
list->prev->next = list->next;
free(list);
return second;
}
while (list->next != current)
{
if (value == list->data)
{
list->next->prev = list->prev;
list->prev->next = list->next;
free(list);
return current;
}
list = list->next;
}
//handle last element in case of just two elements
if (value == list->data && list->next->next == list)
{
printf("yea\n");
//list->next->prev = list->prev;
//list->prev->next = list->next;
current->next = NULL;
current->prev = NULL;
free(list);
return current;
}
//handle last element
if (value == list->data)
{
list->next->prev = list->prev;
list->prev->next = list->next;
free(list);
return current;
}
printf("there is no value %d to delete!\n", value);
return current;
}
void printlist(struct cell *list)
{
struct cell *current = list;
if (list == NULL)
{
printf("The CDLL is empty!\n");
return;
}
if (list->next == NULL && list->prev == NULL)
{
printf("%d\n", list->data);
return;
}
do
{
printf("%d\n", list->data);
list = list->next;
}
while ( list != current);
}
void find(struct cell *list, int value)
{
struct cell *current = list;
if (list->next == NULL && list->prev == NULL && value = list->data)
{
printf("%d is found in CDLL which has only one element\n", value);
return;
}
if (value == list->data)
{
printf("The value %d is found at the beginning of CDLL before %d\n", value, list->next->data);
return;
}
while (list->next != current)
{
if (list->data == value)
{
printf("The value %d is found between %d and %d\n", value, list->prev->data, list->next->data);
return;
}
list = list->next;
}
if (list->data == value)
{
printf("The value %d is found at the end of CDLL after %d\n", value, list->prev->data);
return;
}
printf("the value %d is not found in CDLL!\n", value);
return;
}
void main (int argc, char *argv[])
{
struct cell *mylist = NULL;
int command, val;
printf("CIRCULARLY-DOUBLY LINKED LIST (CDLL)\n");
printf("Control commands:\n");
printf("1 - insert cell\n");
printf("2 - delete cell\n");
printf("3 - print list\n");
printf("4 - find value in the list\n");
printf("0 - exit program\n");
printf("Enter your command: ");
for (;;)
{
scanf("%d", &command);
switch (command)
{
case 1:
printf("Enter the value to be inserted: ");
scanf("%d", &val);
mylist = insert(mylist, val);
printf("Enter the next command: ");
break;
case 2:
printf("Enter the value to be deleted: ");
scanf("%d", &val);
mylist = removecell(mylist, val);
printf("Enter the next command: ");
break;
case 3:
printf("Contents of CDLL: \n");
printf("=======================================\n");
printlist(mylist);
printf("=======================================\n");
printf("Enter the next command: ");
break;
case 4:
printf("Enter the value to be searched for: ");
scanf("%d", &val);
find(mylist, val);
printf("Enter the next command: ");
break;
case 0:
//exit program
break;
default:
printf("Wrong command!\n");
printf("Control commands:\n");
printf("1 - insert cell\n");
printf("2 - delete cell\n");
printf("3 - print list\n");
printf("4 - find value in the list\n");
printf("0 - exit program\n");
printf("Enter your command: ");
break;
}
}
}