Circularly-Doubly Linked List implementation

This is a discussion on Circularly-Doubly Linked List implementation within the C Programming forums, part of the General Programming Boards category; i was exercising with circularly lists and reading about doubly linked lists, now i decided to implement circularly doubly linked ...

  1. #1
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78

    Post Circularly-Doubly Linked List implementation

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

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    yeah ok, thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. Making a doubly linked list
    By mlupo in forum C Programming
    Replies: 1
    Last Post: 10-16-2002, 09:05 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21