Like Tree2Likes
  • 1 Post By anduril462
  • 1 Post By anduril462

inserting into a linked list

This is a discussion on inserting into a linked list within the C Programming forums, part of the General Programming Boards category; I have taken a data structures class which focused primarily on implementing in java but I am trying to apply ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    35

    inserting into a linked list

    I have taken a data structures class which focused primarily on implementing in java but I am trying to apply my knowledge by implementing a few structures in a different language.

    currently I am trying to implement a linked list. I have managed to get it working fine so far, but am having trouble with the insert function. I can only insert at the top of the list, after the header. To insert after any given node I must set my current node to current->next after the insertion is completed. How can I accomplish this within the function itself? Thanks for your help. I've posted my code below.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void printList(struct node* list);
    int isEmpty(struct node* list);
    void makeEmpty(struct node* list);
    struct node* find(struct node* list, int item);
    void insert(struct node* p, int item);
    void removeNode(struct node *list, int item);
    
    struct node
    {
    	int data;
    	struct node* next;
    };
    
    
    int main()
    {
    	struct node *root;
    	struct node *current;
    	struct node **ptr_to_head = &root;
    	int k;
    
    	root = (struct node*)malloc(sizeof(struct node));
    	root->next = NULL;
    	root->data = NULL;
    	current = root;
    
    	for(k = 1; k < 10; k++)
    	{
    		insert(current, k * 5);
    		current = current->next;
    	}
    
    	printList(root);
    
    	return 0;
    }
    
    int isEmpty(struct node* list)
    {
    	if(list->next == NULL)
    		return 1;
    	return 0;
    }
    
    void makeEmpty(struct node* list)
    {
    	list->next = NULL;
    }
    
    void printList(struct node *list)
    {
    	struct node* current;
    
    	if(isEmpty(list))
    		printf("List is empty.\n");
    	else
    	{
    		current = list->next;
    		while(current->next != NULL)
    		{
    			printf("%d\n", current->data);
    			current = current->next;
    		}
    		printf("%d\n", current->data);
    	}
    
    }
    
    /*returns a node containing the item in the list. If item is
     *not found then a null value is returned
     */
    
    struct node* find(struct node *list, int item)
    {
    	struct node *p = list->next;
    	if(p != NULL)
    	{
    		while(p->next != NULL)
    		{
    			if(p->data == item)
    				return p;
    			p = p->next;
    		}
    	}
    
    	return NULL;
    }
    
    //inserts item at the front of the list
    
    void insert(struct node *list, int item)
    {
    	if(list != NULL)
    	{
    		struct node* p = (struct node*)malloc(sizeof(struct node));
    		p->data = item;
    		p->next = list->next;
    		list->next = p;
    	}
    }
    
    void removeNode(struct node *list, int item)
    {
    	struct node *current = list->next;
    	struct node *previous = list;
    
    	if(isEmpty(list))
    		printf("List is empty.");
    	else
    	{
    		while(current->next != NULL && current->data != item)
    		{
    			previous = current;
    			current = current->next;
    		}
    		if(current->data == item)
    		{
    			previous->next = current->next;
    			free(current);
    		}
    		else
    			printf("Value not in list.\n");
    	}
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Compile with warnings turned all the way up. In GCC, use the -Wall flag. If you have another compiler, you will have to check it's documentation.
    Code:
    $ make list
    gcc -Wall -g -std=c99  -lssl -lm -lpthread -lcurses -lefence  list.c   -o list
    list.c:4: warning: ‘struct node’ declared inside parameter list
    list.c:4: warning: its scope is only this definition or declaration, which is probably not what you want
    list.c:5: warning: ‘struct node’ declared inside parameter list
    list.c:6: warning: ‘struct node’ declared inside parameter list
    list.c: In function ‘main’:
    list.c:27: warning: assignment makes integer from pointer without a cast
    list.c:36: warning: passing argument 1 of ‘printList’ from incompatible pointer type
    list.c:4: note: expected ‘struct node *’ but argument is of type ‘struct node *’
    list.c:22: warning: unused variable ‘ptr_to_head’
    list.c: At top level:
    list.c:41: error: conflicting types for ‘isEmpty’
    list.c:5: note: previous declaration of ‘isEmpty’ was here
    list.c:48: error: conflicting types for ‘makeEmpty’
    list.c:6: note: previous declaration of ‘makeEmpty’ was here
    list.c:53: error: conflicting types for ‘printList’
    list.c:4: note: previous declaration of ‘printList’ was here
    make: *** 
    [list] Error 1
    Most of those can be fixed by simply moving the struct definition above your function prototypes. After doing that, all that is left is:
    Code:
    $ make list
    gcc -Wall -g -std=c99  -lssl -lm -lpthread -lcurses -lefence  list.c   -o list
    list.c: In function ‘main’:
    list.c:27: warning: assignment makes integer from pointer without a cast
    list.c:22: warning: unused variable ‘ptr_to_head’
    Line 27, you do root->data = NULL. NULL is a pointer type, data is an int. Set it equal to 0.

    To do what you want, you need to pass in a pointer to current, i.e. a struct node **, to insert. Something like this (which is untested):
    Code:
    void insert(struct node **list, int item)  // note the double * there
    {
        // exact same code as your existing insert function, but using *list everywhere instead of list
        // list now points to current, so to actually access current, you must use *list
    
        // at the end of the function, update *list, or current in your main function
        *list = (*list)->next;
    }
    
    // when you call insert, pass in a pointer to current (i.e. the address of current)
    insert(&current, k * 5);
    EDIT: I should tell you, you have a somewhat unconventional way of implementing a linked list in C. Having a current node outside your insert function, basically just to track the end of the list is not ideal. Using a "dead" node at the beginning to signify an empty list is also not ideal. I would either just set the root pointer to NULL, or create a special node that perhaps contains other useful stuff. A typical list header node would contain a pointer to the start of the list, perhaps a pointer to the end, and a count of elements in it.
    Last edited by anduril462; 06-06-2012 at 01:07 PM.
    stahta01 likes this.

  3. #3
    Registered User
    Join Date
    Jul 2011
    Posts
    35
    ok. I will try and make some improvements. Do you know of a good reference, be it book or website, for implementing linked lists and binary trees in C? My implementation is pretty much based off of my C text book. It is "Engineering Problem Solving with C" by Delores M. Etter. Thanks for your help.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    A quick Google search brought up several tutorials of varying quality. This one seemed to be pretty good: http://en.literateprograms.org/Categoryata_structures.
    stahta01 likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Inserting at end of a linked list error
    By swifferclean in forum C Programming
    Replies: 8
    Last Post: 06-29-2011, 11:12 AM
  2. Replies: 7
    Last Post: 11-04-2010, 02:18 PM
  3. Inserting into linked list
    By mikeman in forum C++ Programming
    Replies: 3
    Last Post: 01-22-2010, 07:46 PM
  4. inserting into linked list
    By MiroMage in forum C Programming
    Replies: 4
    Last Post: 09-16-2008, 08:55 PM
  5. linked list inserting
    By comar in forum C++ Programming
    Replies: 3
    Last Post: 07-26-2007, 08:01 AM

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