Thread: One more linked list implementation

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

    One more linked list implementation

    Hello, i am now learning the linked lists, i read about them, and saw some example codes, but most of them had functions which needed a pointer to head as an argument, then i decided to implement linked list myself.

    Most of my functions require just pointer to list, and specific value to operate. If someone would like to take a look at my code, just say me what you think...and especially i want you to pay more attention to the removenode function... i implemented such operation using shifting of values... what do you think?

    The linked list is just simple order of data in ascending format.. here is the full working code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define snapd(expr) printf(#expr " = %d\n", expr);
    #define snapd(expr) printf(#expr " = %d\n", expr);
    
    /* Function prototypes */
    struct node *createlist(int value);
    void printlist(struct node *list);
    void find(struct node *list, int value);
    void removenode(struct node *list, int value);
    void insert(struct node *list, int value);
    
    /* Node definition */
    struct node
    {
        int data;
        struct node *ptr;
    };
    
    
    /* This function creates the linked list with the first element equal to its argument */
    
    struct node *createlist(int value)
    {
        struct node *first;
    
        first = (struct node*)malloc(sizeof(struct node));
    
        first->data = value;
        first->ptr = NULL;
    
        return first;
    }
    
    
    
    
    
    /* This function prints out the contents of the linked list */
    void printlist(struct node *list)
    {
    
    
        if (list->ptr == (struct node *)-1)
            {
            printf("The list is empty!\n");
            return;
            }
    
    
        while (list->ptr != NULL)
            {
            printf("%d\n", list->data);
    
            list = list->ptr;
            }
    
        if (list->ptr == NULL)
            {
            printf("%d\n", list->data);
            }
    
        
    }
    
    void find(struct node *list, int value)
    {
        struct node *previous = list;
    
                if (list->data == value)
                {
                printf("The element %d have been at the beginning of the list before %d\n", value, list->ptr->data);
                return;
                }
    
        while (list->ptr != NULL)
            {
    
    
            if (list->data == value && list->ptr != NULL)
                {
                printf("The element %d have been found between %d and %d\n", value, previous->data, list->ptr->data);
                return;
                }
             
                     
                previous = list;
                list = list->ptr; 
    
            }
    
    
                if (list->data == value)
                {
               printf("The element %d have been found at the end of the list after %d\n", value, previous->data);
                return;
                }
                
                
             printf("The element %d is not found in the list...\n");
    
    
    }
    
    
    /* This function removes the node with specified value from the linked list */
    void removenode(struct node *list, int value)
    {
    
     
        struct node *previous, *next, *first = list;
        int i;
    
        if (list->ptr == (struct node *)-1)
            {
            printf("The list is already empty!\n");
            return;
            }
    
    
        //if the list contains only one element, free the list and exit function
        //then set a flag that this element is not a member of the linked list anymore
        if (list->data == value && list->ptr == NULL)
            {
            list->ptr = (struct node*)-1; //set the flag
            free(list);
            return;
            }
    
            for (i = 0; list->data != value; i++)
            {
                 previous = list;      
                 list = list->ptr;
            }
    
        if (i != 0)
            {
            next = list->ptr;
        
            previous->ptr = next;
            free(list);
            }
        else
            {
                //shift all the elements to the left
                for (;;)
                    {
                    
                        list->data = list->ptr->data;
                        list = list->ptr;
        
                        if (list->ptr == NULL)
                            break;
                            
                    }
        
                //remove the last element
                list = first;
                while (list->ptr != NULL)
                {
                previous = list;
                list = list->ptr;
                }
                previous->ptr = NULL;
                free(list);
    
            }
    
    }
    
    
    /* This function inserts the value in the appropriate position in the linked list */
    void insert(struct node *list, int value)
    {
        struct node *newnode;
        struct node *previous = list;
    
        //create an empty new node
        newnode = (struct node*)malloc(sizeof(struct node));
    
    
        //scan until the end of the list
        while (list->ptr != NULL)
            {
    
                if (value > list->data)
                    {
                    previous  = list;
                    }   
    
    
                //if it is less than current, and more than previous, insert value between them
                 if ( (value < list->data) && (value > previous->data) )
                    {
                        previous->ptr = newnode;
                        newnode->ptr = list;
                        newnode->data = value;
                        printf("%d is inserted between %d and %d!\n", value, previous->data, list->data);
                        break;
                    }   
    
                if (value == list->data)
                    {
                    printf("There is already value %d in the list!\n", value);
                    break;
                    }
    
                if (value < list->data)
                    {
                    printf("%d is added before %d...\n", value, list->data);
                    newnode->data = list->data;
                    newnode->ptr = list->ptr;
    
                    list->data = value;
                    list->ptr = newnode;
                    break;
                    }
    
                    list = list->ptr;
    
            }
    
        
    
            if (list->ptr == NULL)
            {
                //if the value is more than the last element add the last element with new value
                if (value > list->data)
                    {
                    newnode->data = value;
                    newnode->ptr = NULL;
                    list->ptr = newnode;
                    printf("%d  is added after %d...\n", value, list->data);
                    }
    
                if (value == list->data)
                    {
                    printf("There is already value %d in the list!\n", value);
                    }
    
    
                if (value < list->data)
                    {
                    printf("%d is added before %d...\n", value, list->data);
                    newnode->data = list->data;
                    newnode->ptr = list->ptr;
    
                    list->data = value;
                    list->ptr = newnode;
                    }
    
    
    
            }
    
    }
    
    
    
    
    void main (int argc, char *argv[])
    {
        struct node *mylist;
        int value;
        int command;
    
    
    
    
    
    
            printf("Enter the first element of the linked list to be created: ");
            scanf("%d", &value);
    
            mylist = createlist(value);
    
                printf("Available commands:\n");
                printf("1 - add new element:\n");
                printf("2 - remove element:\n");
                printf("3 - print the list:\n");
                printf("4 - find a value in a list:\n");
                printf("0 - quit program:\n");
                printf("Enter command: ");
    
                for(;;)
                {
                scanf("%d", &command);
    
               
               switch (command)
                   {
                   case 1:
                       printf("Enter the value to be added: ");
                       scanf("%d", &value);
    
                       //if the list is empty, create the new list again
                       if (mylist->ptr == (struct node *)-1)
                           {
                           mylist = createlist(value);
                           }
                       else
                       //otherwise, insert new value in the current list
                       insert(mylist, value);
    
                       printf("Enter the next command ");
                       break;
    
                   case 2:
                       printf("Enter the value to be removed: ");
                       scanf("%d", &value);
                       removenode(mylist, value);
                       printf("Enter the next command ");
                       break;
    
                   case 3:
                       printf("Linked list values:\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", &value);
                       find(mylist, value);
                       printf("Enter the next command ");
                       break;
    
                   case 0:
                       return;
                       break;
    
                   default:
                       printf("wrong command!\n");
                       printf("Available commands:\n");
                       printf("1 - add new element:\n");
                       printf("2 - remove element:\n");
                       printf("3 - print the list:\n");
                       printf("4 - find a value in a list:\n");
                       printf("0 - quit program:\n");
                       printf("Enter command: ");
                       break;
                   }
    
                }
    
    
    }
    And also please pay attention on how i identify the empty list...that casting like (struct node *)-1.. waht do you think about this method?
    Last edited by BlackOps; 07-15-2009 at 02:02 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You should just check to see if the node being passed is NULL. If it is, they passed you the pointer to the list, but it doesn't actually point to anything. Consider:
    Code:
    struct node *ourlist = NULL;
    ...
    foo( ourlist );
    ...
    foo( struct node *somelist )
    {
        if( somelist == NULL )
        {
            printf( "Recieved an empty list.\n" );
        }
        else
        {
            ...do stuff with the list...
        }
    }
    Also, your remove node funtion won't work if you want to remove the first node. I can tell that just by looking at the function prototype. (Unless you happen to have a dummy node to start your list that never changes--which doesn't appear to be the case.)


    Quzah.
    Last edited by quzah; 07-15-2009 at 02:20 PM.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    ok...thank you for the reply, so..about a code which u have showed, i know about this! but it just doesnt work dont know why...strange...thats why i decided to implement it like i did

    about removal...my function successfully removes the first node. there is a special operation of shifting all elements to the left and then remove the last.
    Last edited by BlackOps; 07-15-2009 at 02:34 PM.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by BlackOps View Post
    And also please pay attention on how i identify the empty list...that casting like (struct node *)-1.. waht do you think about this method?
    Why not just "if (list == NULL)"? Presuming that after the the last pointer is free/removed you also set it to NULL (which is a good habit with freed ptrs).

    I suspect that condition, (struct node*)-1, will never ever be true, since what you are saying is, regard "-1" as a struct node*. It is very unlikely that any of those pointers will end up with a value of -1. What was your intent with this?

    Generally you seem to have the right idea. However, in your remove function, you do not need to flag a node for removal and then shift everything as if it were a contiguous array (or whatever that is supposed to do)! A big advantage of a linked list is you do not have to do that! All you do is eliminate the node and swap the pointers around:
    Code:
    node *ptr=head, *prev=NULL;
    while (ptr) {
            if (ptr->data == value) {
                  if (prev) {
                       prev->next = ptr->next;
                       free(ptr);
                  } else {  // eg. the head is to be removed
                       head = ptr->next;
                       free(ptr);
                  }
                  return head;
            } else {
                  prev = ptr;
                  ptr = ptr->next;
            }
    }
    Can you understand how that works?
    Last edited by MK27; 07-15-2009 at 02:36 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    yes i can of cuz...but that doesnt work ..i mean if i do this...and then i execute my printlist function, it again prints that head! just with the value of zero... u know what i mean?

    that NULL thingy doesnt work..so good

  6. #6
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    ah...one more thing is... when i did it i wanted my remove function not to return anything... and take just value to be removed and pointer to list as an argument.... these constraints didnt let me to do as u say...

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by BlackOps View Post
    that NULL thingy doesnt work..so good
    Hmmm. It should, maybe you should get more specific.

    At least it should as long as you ensure that if the head is being removed and there are no more nodes after that, removeNode should return NULL. For example, in that last code I posted:
    Code:
                  } else {  // eg. the head is to be removed
                       head = ptr->next;
                       free(ptr);
                  }
                  return head;
    Usually linked list functions return the head pointer in case the order of the list has changed. So in this case, no matter what, we return head. The only way head would have changed in removeNode is if it is removed, meaning head becomes ptr->next, when ptr == head. If head was the only node in the list, ptr->next should be NULL, so by returning head, we are returning NULL.

    That means the next time you submit the head to a function, all you have to do is check if it is NULL. If head is NULL, the list is empty.

    That is pretty much "the algorithm" for managing linked lists. It is essential that you properly assign and check for NULL pointers, this is fundamental to the algorithm.

    If you are initializing an empty list, make sure head == NULL to start with.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by BlackOps View Post
    ah...one more thing is... when i did it i wanted my remove function not to return anything... and take just value to be removed and pointer to list as an argument.... these constraints didnt let me to do as u say...
    If you can't return anything, you will have to make the head ptr a global variable.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Those constraints won't work regardless of how you compare pointers, unless you do as I said, and use a dummy node for your first element, that you never actually use.
    Code:
    void foo( struct node *n, int value )
    {
        struct node *p = n, *t = n->next;
        
        while( t && t->data != value )
        {
            p = t;
            t = t->next;
        }
    
        if( t )
        {
            p->next = t->next;
            free( t );
        }
    }
    That looks about right.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    well in my code i dont return anything and head is not global variable, and it works though... i will work at other methods of implementation... i just wanted to hear opinion about this one, thanks a lot.

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by BlackOps View Post
    well in my code i dont return anything and head is not global variable, and it works though... lot.
    If head is not a global and you can't return anything then you cannot change the head, unless you use a dummy head like quzah says.

    So, if you are not doing one of those three things, your code cannot work to remove or insert a new head, you just think it does -- that is elementary logic.

    The absolute worst attitude you could possibly take programming is to say "well, it works, just I don't know why and can't explain it". Seriously. That is like carrying a bomb you don't understand around and saying, "well, it hasn't gone off yet, I guess everything is okay..."
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    well i'll remake my code to return values...and the easily do as u said.. right now, my code works because i shift all the elements...like copy each of the to the left side, and then remove the last node it may seem little messy but it works..to be more precise...it does not remove head...it just recopies all elements and removes last... yeah thats not so good solution. ok.

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by BlackOps View Post
    well i'll remake my code to return values...and the easily do as u said.. right now, my code works because i shift all the elements...like copy each of the to the left side, and then remove the last node it may seem little messy but it works..to be more precise...it does not remove head...it just recopies all elements and removes last... yeah thats not so good solution. ok.
    As long as you understand what you're doing that's fine -- I won't have to order any punishments
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    @OP
    Casting to malloc is also not required. It returns void *.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  15. #15
    Registered User BlackOps's Avatar
    Join Date
    Jul 2009
    Location
    AZERBAIJAN
    Posts
    78
    BEN10, i explicitly let know that actually it returns pointer to my struct type.

    Okay, i have worked a little on my code, and decided to implement this linked listed in a better way, and more natural as it should be.

    So if u would like just take a quick look, say if something is wrong. Thank you.

    Below is the working code of linked list implementation:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define snapd(expr) printf(#expr " = %d\n", expr);
    #define snapd(expr) printf(#expr " = %d\n", expr);
    
    /* Function prototypes */
    void printlist(struct node *list);
    void find(struct node *list, int value);
    struct node *removenode(struct node *list, int value);
    struct node *insert(struct node *list, int value);
    
    /* Node definition */
    struct node
    {
        int data;
        struct node *ptr;
    };
    
    
    /* This function prints out the contents of the linked list */
    void printlist(struct node *list)
    {
    
    
        if (list == NULL)
            {
            printf("The list is empty!\n");
            return;
            }
    
    
        while (list->ptr != NULL)
            {
            printf("%d\n", list->data);
    
            list = list->ptr;
            }
    
        if (list->ptr == NULL)
            {
            printf("%d\n", list->data);
            }
    
        
    }
    
    void find(struct node *list, int value)
    {
        struct node *previous = list;
    
                if (list->data == value)
                {
                printf("The element %d have been at the beginning of the list before %d\n", value, list->ptr->data);
                return;
                }
    
        while (list->ptr != NULL)
            {
    
    
            if (list->data == value && list->ptr != NULL)
                {
                printf("The element %d have been found between %d and %d\n", value, previous->data, list->ptr->data);
                return;
                }
             
                     
                previous = list;
                list = list->ptr; 
    
            }
    
    
                if (list->data == value)
                {
               printf("The element %d have been found at the end of the list after %d\n", value, previous->data);
                return;
                }
                
                
             printf("The element %d is not found in the list...\n");
    
    
    }
    
    
    
    
    
    /* This function inserts the value in the appropriate position in the linked list */
    struct node *insert(struct node *list, int value)
    {
        struct node *newnode, *previous = list, *first = list;
    
    
        //if the list is empty, add the first element
        if (list == NULL)
            {
            newnode  = (struct node *)malloc(sizeof(struct node));
            newnode->data = value;
            newnode->ptr = NULL;
            return newnode;
            }
    
    
        // Add value before the first element
        if (value < list->data)
            {
            snapd(list->data);
            newnode  = (struct node *)malloc(sizeof(struct node));
            newnode->data = value;
            newnode->ptr = list;
            return newnode;
            }
    
        if (value == list->data)
            {
            printf("There is already element %d in the list!\n", value);
            return first;
            }
    
    
        // Add the value in the middle of the list
        while (list->ptr != NULL)
            {
            if (value < list->data)
                {
                newnode  = (struct node *)malloc(sizeof(struct node));
                newnode->data = value;
                newnode->ptr = list;
                previous->ptr = newnode;
                return first;
                }
    
            if (value == list->data)
            {
            printf("There is already element %d in the list!\n", value);
            return first;
            }
    
            previous = list;
            list = list->ptr;
    
            }
    
    
            if (list->ptr == NULL && value == list->data)
            {
            printf("There is already element %d in the list!\n", value);
            return first;
            }
    
        // Add after the last element of the list
        if (list->ptr == NULL && value > list->data)
            {
            newnode  = (struct node *)malloc(sizeof(struct node));
            newnode->data = value;
            newnode->ptr = NULL;
            list->ptr = newnode;
            return first;
            }
    
        // Add before the last element of the list
        if (list->ptr == NULL && value < list->data)
            {
            newnode  = (struct node *)malloc(sizeof(struct node));
            newnode->data = value;
            newnode->ptr = list;
            previous->ptr = newnode;
            return first;
            }
    
        
    
    }
    
    /* This function deletes the specified node */
    struct node *removenode(struct node *list, int value)
    {
        struct node *first = list, *previous = list;
    
        //handle the empty list
        if (list == NULL)
            {
            printf("The list is already empty!\n");
            return first;
            }
    
        //handle the deletion of single element in the list
        if (list->ptr == NULL && list->data == value)
            {
            free(list);
            return NULL;
            }
    
        //handle the deletion of first element
        if (list->ptr != NULL && list->data == value)
            {
            first = list->ptr;
            list->ptr = NULL;
            free(list);
            return first;
            }
    
    
        while (list->ptr != NULL)
            {
            if (list->data == value)
                {
                previous->ptr = list->ptr;
                free(list);
                return first;
                }
    
            previous = list;
            list = list->ptr;
            }
    
    
            // handle the deletion of the last element in the list
            if (list->ptr == NULL && list->data == value)
            {
            previous->ptr = NULL;
            free(list);
            return first;
            }
    
            //the value to be removed havent been found in the list
            printf("There is no %d in the list!\n", value);
            return first;
    }
    
    
    void main (int argc, char *argv[])
    {
        struct node *mylist = NULL;
        int value;
        int command;
    
    
                printf("Available commands:\n");
                printf("1 - add new element:\n");
                printf("2 - remove element:\n");
                printf("3 - print the list:\n");
                printf("4 - find a value in a list:\n");
                printf("0 - quit program:\n");
                printf("Enter command: ");
    
                for(;;)
                {
                scanf("%d", &command);
    
               
               switch (command)
                   {
                   case 1:
                       printf("Enter the value to be added in the list: ");
                       scanf("%d", &value);
                       mylist = insert(mylist,value);
                       printf("Enter the next command ");
                       break;
    
                   case 2:
                       printf("Enter the value to be removed: ");
                       scanf("%d", &value);
                       mylist = removenode(mylist, value);
                       printf("Enter the next command ");
                       break;
    
                   case 3:
                       printf("Linked list values:\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", &value);
                       find(mylist, value);
                       printf("Enter the next command ");
                       break;
    
                   case 0:
                       return;
                       break;
    
                   default:
                       printf("wrong command!\n");
                       printf("Available commands:\n");
                       printf("1 - add new element:\n");
                       printf("2 - remove element:\n");
                       printf("3 - print the list:\n");
                       printf("4 - find a value in a list:\n");
                       printf("0 - quit program:\n");
                       printf("Enter command: ");
                       break;
                   }
    
                }
    
    
    }

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. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM