Thread: Linked List, Please Help!

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    2

    Linked List, Please Help!

    This is probably just a pointer issue or some stupid thing I'm doing, I'm doing a linked list program for a data structures class and unfortunately they want us to use C, when I could do this in Java in about 15 minutes. I've fixed bug after bug after bug and finally the instructor helped me look and we found one bug after about an hour but after that, nothing, still having issues.

    Here's my mainline:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char * argv [])
    {
    
    	 typedef struct node * link;
    	struct node
    	{
    		int data;
    		int hasNext;
    		link next;
    	};
     
    
    	//Variables
    	link head = NULL;
    	link tail = NULL;
    	int exists = 0;
    	char * input;
    	int ninput;
    	
    	//Main program "Infinite" Loop
    	while(1)
    	{
    		//Get command from user
    		printf("Enter command (Insert, Delete, Print, Done):");
    		scanf("%s", &input);
    		
    		//INSERT
    		if(strcmp(&input, "Insert") == 0)
    		{
    			//Get data to be stored
    			printf("Enter an integer: ");
    			scanf("%d", &ninput);
    			
    			//If empty
    			if(!exists)
    			{	
    				head = createNode();
    				initNodes(ninput,head);
    				tail = head;
    				exists = 1;
    				printf("Head created\nData: %i\n", head->data);
    			}
    			
    			//If list has at least 1 element
    			else
    			{	
    				link curr = createNode();
    				initNodes(ninput, curr);
    				insertNext(tail, curr);
    				tail = curr;
    
    			}
    		}
    		//END OF INSERT
    		
    		//DELETE (Most complex due to many cases to take into account)
    		else if(strcmp(&input, "Delete") == 0)
    		{
    			printf("Enter an integer: ");
    			scanf("%i", &ninput);
    			
    			//If list is empty
    			if(!exists)
    			{
    				printf("List is empty\n");
    			}
    			
    			//If list has at least 1 element
    			else
    			{
    				int found = 0;
    				link curr = head;
    				
    				//If the first element is to be deleted
    				if(head->data == ninput)
    				{
    					//If there is only one element
    					if(head == tail) 
    					{
    						free(head);
    						head = NULL;
    						tail = NULL;
    						exists = 0;
    					}
    					
    					//If there are multiple elements
    					else
    					{
    						curr = (link)head->next;
    						deleteNext(&head);
    						head = curr;
    					}
    				}
    				//end of if
    				
    				//If it's not the first element
    				else
    				{
    					link temp;
    					//Search list for element
    					while(curr != NULL)
    					{
    						if(curr->next == NULL) break;
    						temp = (link)curr->next;
    						if(temp->data == ninput)
    						{
    							found = 1;
    							break;
    						}
    						curr = (link)curr->next;
    					}
    					
    					//If the element is found
    					if(found == 1)
    					{
    						if((link)curr->next == tail) tail = curr;
    						deleteNext(&curr);
    					}
    					
    					//If it doesn't exist, print an error
    					else printf("Number couldn't be found.\n");
    				}
    				//end else
    			}
    			//end outer else
    		}
    		//END OF DELETE
    		
    		//PRINT (simply calls printList)
    		else if(strcmp(&input, "Print") == 0) 
    		{	
    			if(!exists) printf("List is empty\n");
    			else 
    			{
    				link curr = (link)head;
    				while(curr->hasNext)
    				{
    					printf("%i\n", curr->data);
    					curr = curr->next;
    				}
    				printf("%d\n", curr->data);
    			}
    			
    		}
    		
    		//DONE (exits loop)
    		else if(strcmp(&input, "Done") == 0) break;
    		
    		//Invalid Input
    		else printf("Invalid input, try again.\n");
    		
    	}
    	
    	//Clean-Up + Exit
    	if(exists) deleteList(head);
    	return 0;
    }
    I'm using the int exists thing because for some reason I found out that forcing head to NULL then trying if(head == NULL) wasn't working, so I know I'm doing that wrong but I'm having issues with the print statement but before I talk about that let me paste my actual linked list code.
    Code:
     #include <stdio.h>
     #include <stdlib.h>
    
     typedef struct node * link;
     struct node
     {
    	int data;
    	int hasNext;
    	link next;
     };
     
    
    //Declarations
    link createNode(void);
    void initNodes(int num, link newNode);
    void insertNext(link prevNode, link newNode);
    link deleteNext(link prevNode);
    void freeNode(link oldNode);
    void printList(link head);
    void deleteList(link head);
    
    //Allocates memory for link
     link createNode(void)
     {
    		link temp = (link)malloc(sizeof(struct node));
    		return temp;
     }
    
    //Initializes node
    void initNodes(int num, link newNode)
    {
    	newNode->next = NULL;
    	newNode->data = num;
    	newNode->hasNext = 0;
    }
    	
    //Inserts element into node
    void insertNext(link prevNode, link newNode)
    {
    	prevNode->next = newNode;
    	prevNode->hasNext = 1;
    }
    
    //Deletes the next node
    link deleteNext(link prevNode)
    {
    	link temp = prevNode->next;
    	if(temp->next != NULL)
    	{
    		prevNode->next = temp->next;
    	}
    	free(temp);
    	prevNode->next == NULL;
    }
    
    //Frees a node
    void freeNode(link oldNode)
    {
    	free(oldNode);
    }
    
    
    //Prints the list
    void printList(link head)
    {
    	//if(head == NULL) return; NOT NEEDED
    	link curr = head;
    	while(curr->hasNext)
    	{
    		printf("%i\n", curr->data);
    		curr = curr->next;
    	}
    	printf("%i\n", curr->data);
    }
    
    //Deletes the list 
    void deleteList(link head)
    {
    	link curr = head;
    	while(curr->hasNext)
    	{
    		curr = curr->next;
    		free(head);
    		head = curr;
    	}
    	free(head);
    }
    The declarations are in there because they were specified to be for the assignment.

    Here's an example of output:

    Enter command (Insert, Delete, Print, Done):Insert 4
    Enter an integer: Head created
    Data: 4
    Enter command (Insert, Delete, Print, Done):Print
    36
    Enter command (Insert, Delete, Print, Done)one
    Segmentation fault

    It always prints 36, and I put the printList code into the mainline to test if that was an issue but it's still doing it. Very odd. I'm using gcc compiler on OS X and linking the two files together correctly, I just know that whatever's going on likely has something to do with pointers and memory.

    Sorry if this post is really long, if anyone can help that would be really appreciated, thanks!
    Last edited by CodeMonkeyZ; 02-16-2009 at 06:15 PM.

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Your code would be easier to read if you put code tags around it. It could also looks overcomplicated. IE: longer than necessary. For example, theres no need for a has_next field. The head node it set to NULL at the start, so when you iterate over you list you can just do it until the current node is NULL.

    Here:
    Code:
    char * input;
    int ninput;
    
    //Main program "Infinite" Loop
    while(1)
    {
    //Get command from user
    printf("Enter command (Insert, Delete, Print, Done):");
    scanf("%s", &input);
    
    //INSERT
    if(strcmp(&input, "Insert") == 0)
    {
    You never allocate any space to hold your input. You need to allocate space for with malloc, or declare input as a character array. Also, you dont to pass the array by reference to strcmp with the & symbol.

    Some suggestions around this part of your code:
    Code:
    //If empty
    if(!exists)
    {
      head = createNode();
      initNodes(ninput,head); 
      tail = head;
      exists = 1;
      printf("Head created\nData: %i\n", head->data);
    }
    else
    It should be possible to have a function that creates, initalises then returns the new head of the list. This would be cleaner. There should be no need for an 'exists' variable as you only need to pass the head in. I think you can get rid of the 'tail' variable too.

    Its surprising your teacher wouldent have mentioned any of this.

    Anyways, I cant be bothered to look any further through this unindented mess. Add code tags and I'm sure you will get more help

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    2
    I forgot about tags, it's been a while since I've been on a programming forum. As for all the stuff that seems overcomplicated, it's only in there because the simpler stuff I put it wasn't working so I put in more complicated ways I was more sure on the syntax of to make it work.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You are totally crazy to have proceeded to this point when:
    I'm using the int exists thing because for some reason I found out that forcing head to NULL then trying if(head == NULL) wasn't working, so I know I'm doing that wrong but I'm having issues with the print statement but before I talk about that let me paste my actual linked list code.
    and even better:
    As for all the stuff that seems overcomplicated, it's only in there because the simpler stuff I put it wasn't working so I put in more complicated ways I was more sure on the syntax of to make it work.
    Somebody needs a mirror on this one. Why would you add like five functions at once when evidently, you know you have been unable to make even one work properly. I am I wrong to say there are no pointers in java? You must at least use some kind of referencing -- anyway, linked-lists are all about pointers. You need to find a simple linked list tutorial and write something exactly out, or something, because
    Code:
     trying if(head == NULL) wasn't working
    is too much -- there is no point proceeding with inventing your own work around

    You might as well start again. Honestly. What you've done isn't wasted, but there's no point trying to adapt as is. Use what works.
    Last edited by MK27; 02-16-2009 at 06:35 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
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I agree with MK27. When you don't understand what's happening with the code you already have, then adding more code is not the answer.
    You should either spend time figuring it out, or if you can see how to write it simpler from scratch, ditch it and start over.
    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"

  6. #6
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    insertNext() assumes that the list pointed to by prevNode has exactly a size of 1.
    deleteNext() assumes that the list pointed to by prevNode as at least a size of 1.

    Now in most cases, your list is neither infinitely large nor has it a size of exactly 1.

    When writing your functions, make sure you think about the following cases:
    - the current list is empty
    - the current list has exactly size 1
    - the current element is in the middle of a list
    - the current element is the first of the list
    - the current element is the last of the list

    It seems to me that you didn't expect any of these cases. You might want to have a look at my schoolbook implementation of single linked lists to see how it could be done. Maybe you can find some inspiration there.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

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. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM