Circularly-Doubly Linked List implementation

**BlackOps** · 07-18-2009

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;
            }
        }

 



}

**iMalc** · 07-18-2009

Holy smokes that is long!
Hint: Neither having only one element, nor having only one element in the list need to be treated as special cases. In fact, if you use a sentinel node rather than NULL, then even inserting when the list is logically empty isn't a special case!

Start by deleting this from your printList function, for a simple demonstration of some of the unnecessary code

Code:

    if (list->next == NULL && list->prev == NULL)
        {
        printf("%d\n", list->data);
        return;
        }

Not bad for a first attempt!

**iMalc** · 07-18-2009

Sorry, I mean neither having one, nor two elements need be a special case.

Would you mind correcting some of your indentation and perhaps removing all those newlines at the end, and some of those big gaps in the middle?

**quzah** · 07-18-2009

Code:

void find( struct node *list, int value )
{
    struct node *n = list;

    if( n )
    {
        do
        {
            n = n->next;
        }
        while( n != list && n->value != value );

        if( n->value != value )
        {
            printf( "value not found\n" );
        }
        else
        if( n == list )
        {
            printf( "value is the first in the list\n" );
        }
        else
        if( n->value == list->prev->value )
        {
            printf( "value is the last in the list\n" );
        }
        else
        {
            printf( "value is between %d and %d\n", n->prev->value, n->next->value );
        }
    }
}

Something like that could work. You could also move that else on the end out so that as long as the value is found it prints what it's between, regardless if it's at either end.

Quzah.

**BlackOps** · 07-19-2009

yeah ok, thanks

Thread: Circularly-Doubly Linked List implementation

Thread Tools

Search Thread

Display

Circularly-Doubly Linked List implementation

Similar Threads

C++ Linked list program need help !!!

Unknown memory leak with linked lists...

Making a doubly linked list

Linked list with two class types within template.

singly linked list