Thread: Linked List Pointer Seg Faults

  1. #1
    Registered User
    Join Date
    Mar 2011
    Location
    USA
    Posts
    17

    Linked List Pointer Seg Faults

    Hey Guys,

    So I'm working on a bigger project but trying to implement some Linked List functionality into it and I keep getting this segmentation fault at the same spot and I've checked examples and such and my code (I think) is in line with theirs but mine's not working. I'm a little rusty on C and just getting back into it so maybe it's something simple. I thought I had pointers down pat but maybe I don't. If someone see's what's causing this I'd appreciate it!

    I'm trying to implement a doubly-linked list:

    listtest.c
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stddef.h>
    #include <unistd.h>
    
    #include "list.h"
    
    int main(void)
    {
    	//Vars
    	List *list;
    	Node *head;
    	Node *node;
    	
    	int r;
    	
    	//Setup
    	if((list = (List *)malloc(sizeof(struct List))) == NULL)
    	{
    		printf("List: Memory Allocation Failed...\n");
    		return 0;
    	}
    	if((head = (Node *)malloc(sizeof(struct Node))) == NULL)
    	{
    		printf("Head: Memory Allocation Failed...\n");
    		return 0;
    	}
    	
    	head->value = 5;
    	
    	r = init(&list, &head);
    	if(r == -1)
    	{
    		printf("Linked List: init() Failed...\n");
    		return 0;
    	}
    	
    	//Setup Additional Node
    	if((node = (Node *)malloc(sizeof(struct Node))) == NULL)
    	{
    		printf("Linked List: add() Failed...\n");
    		return 0;
    	}
    	
    	r = add(&list, &node);
    	if(r == -1)
    	{
    		printf("Linked List: add() Failed...\n");
    		return 0;
    	}
    	
    	//Print
    	printList(list);
    	
    	//return
    	return 1;
    }
    list.h
    Code:
    #ifndef _LIST_H_
    #define _LIST_H_
    
    #ifndef _STDDEF_H
    #include <stddef.h>
    #endif
    
    typedef struct Node
    {
    	unsigned index;
    	unsigned value;
    	
    	struct Node *next;
    	struct Node *prev;
    }Node;
    
    typedef struct List
    {
    	unsigned size;
    	
    	struct Node *head;
    	struct Node *tail;
    }List;
    
    int init(List *list, Node *head);
    
    int add(List *list, Node *node);
    
    void printList(List *list);
    	
    
    #endif
    list.c
    Code:
    //Includes
    #include "list.h"
    
    //Pre-Processors
    #ifndef _STDIO_H
    #include <stdio.h>
    #endif
    
    #ifndef _STDLIB_H
    #include <stdlib.h>
    #endif
    
    //Function Definitions
    
    int init(List *list, Node *head)
    {
    	if(list == NULL)
    	{
    		return -1;
    	}
    	if(head == NULL)
    	{
    		return -1;
    	}
    	
    	list->head = head;
    	list->size = 1;
    	
    	head->index = 0;
    	head->prev = NULL;
    	head->next = NULL;
    	
    	return 1;
    }
    
    int add(List *list, Node *node)
    {
    	//Vars
    	Node *temp;
    	
    	//Checks
    	if(list == NULL)
    	{
    		return -1;
    	}
    	if(node == NULL)
    	{
    		return -1;
    	}
    	
    	//Move to the end of the list
    	temp = list->head;
    	while(temp->next != NULL)
    	{
    		temp = temp->next;
    	}
    	
    	//Set the links
    	temp->next = node;
    	node->prev = temp;
    	node->index = list->size;
    	
    	//Increment the size
    	list->size++;
    	
    	//Update the tail nodes
    	list->tail = node;
    	
    	return 1;
    }
    
    void printList(List *list)
    {
    	Node *temp;
    	
    	temp = list->head;
    	
    	while(temp->next != NULL)
    	{
    		printf("Index: %d\tValue: %d\n", temp->index, temp->value);
    		temp = temp->next;
    	}
    }
    The error's occurring in the list.c (above) on line 53, where the add() function is traversing to the end of the list:
    Code:
    ...
    while(temp->next != NULL)
    ...
    If it matters (but I don't think it does) I'm on 32-bit *nix. The program's just crashing with a Seg Fault and gdb is pointing me to that line.

    Thanks!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    It should be

    while ( temp != NULL )
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Location
    USA
    Posts
    17
    Thanks Salem, I'll give that a try when I get home to my Linux machine.

    The only concern I have with that though, which may be a simple fix, is that I want to traverse the list until I get to the last valid element (thus why I was using temp->next != NULL). If I do what you suggested wont this traverse the list until it hits a NULL which will set temp as a NULL structure/pointer. I need to get to the last valid node on the list so that I can add it to the List structure and link it with the other nodes. See what I'm saying? I suppose I could also setup a lastNode pointer kind of thing, and store the previous node on each iteration, but it seems extraneous to add another pointer to the mix when I would think just the one temp pointer would do. Maybe I'm wrong.

    Nevertheless I will give it a try after work and see what happens.

    Thanks!

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    You have a few other issues here:
    First, don't cast you malloc calls. Read the FAQ article to see why.

    Second, compile with all warnings set to the max. You're not using your list properly:
    Code:
    $ gcc -c -Wall -g listtest.c
    listtest.c: In function ‘main’:
    listtest.c:31: warning: passing argument 1 of ‘init’ from incompatible pointer type
    list.h:25: note: expected ‘struct List *’ but argument is of type ‘struct List **’
    listtest.c:31: warning: passing argument 2 of ‘init’ from incompatible pointer type
    list.h:25: note: expected ‘struct Node *’ but argument is of type ‘struct Node **’
    listtest.c:45: warning: passing argument 1 of ‘add’ from incompatible pointer type
    list.h:27: note: expected ‘struct List *’ but argument is of type ‘struct List **’
    listtest.c:45: warning: passing argument 2 of ‘add’ from incompatible pointer type
    list.h:27: note: expected ‘struct Node *’ but argument is of type ‘struct Node **’
    Fix all those by dropping the ampersand. You're passing, &list, &head and &node but list, head and node are already a pointers, which is what your functions need. &list is a pointer-to-pointer, which is wrong. Incorrectly passing list to init() means list is not initialized correctly, and thus your add segfaults. Otherwise, your add function is fine with the while(temp->next != NULL), since you init your list with one element in it already (I must admit, that's unusual). Your print function, however, needs to change to while(temp != NULL), or even a for loop:
    Code:
    for (temp = list->head; temp != NULL; temp = temp->next) {
        // print node
    }
    Removing those ampersands and fixing the loop in print made it work for me.

    The only concern I have with that though, which may be a simple fix, is that I want to traverse the list until I get to the last valid element
    Why traverse? You have a tail pointer. As long as you keep that correct and up to date, you don't need to traverse. Just use list->tail as a pointer to the last valid element.
    Last edited by anduril462; 07-25-2011 at 10:14 AM.

  5. #5
    Registered User
    Join Date
    Mar 2011
    Location
    USA
    Posts
    17
    Yeah that makes a lot more sense. I still don't have the reference and pointers down-pat. I want the functions to change the arguments that get passed (initialize the list and have that List struct you pass it stay initialized) I guess just passing the pointer will do that (I'm too used to Java where everything gets copied in a method parameter so any changes don't persist - but I suppose that's the point of passing the pointers).

    I'll give that a go as well. Thanks for all the help!

    PS - What would be the more "standard" way to implement that linked list? Initialize it with a head and tail, or neither. The reason I was traversing there was because it was initialized with one element so the first call to add() needed to set the tail... stupid of me.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Part of your confusion is how to handle the head/tail bit. If your list has zero elements, head and tail should both be NULL. If there's 1 element, both head and tail should point at that. It's okay, and actually good, to have them point at the same element.

    If you wanted to store phone numbers in your personal phone directory, you wouldn't go buy a phone directory that already has your one friend's phone number in there. You buy a blank one and add everything yourself. Your init should work the same way, start with a totally empty list and then you add to it later. Empty lists typically have a head and tail pointing to NULL. In your case, the count would be 0 also. The add function will have one clause (from an if statement) for adding to an empty list, and an else clause that handles inserts on any non-empty list:
    Code:
    void init(List *list)
    {
        // note you could move the malloc in here and have this function allocate, initialize and return the new, empty list -- just fix the declaration to take nothing and return a List *
        list->count = 0;
        list->head = NULL;
        list->tail = NULL;
    }
    
    void add(List *list, Node *node)
    {
        if (list->head == NULL) {
            // set head and tail to node, count to 1
        }
        else {
            // use tail for end-of-list and append node
            // increment count
        }
    }

  7. #7
    Registered User
    Join Date
    Mar 2011
    Location
    USA
    Posts
    17
    Great guys thanks for all the help and suggestions! The program's running fine now and now I know how to go about setting up the linked lists. I think I've now got a good grasp on pointers now too. Thanks again!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. next pointer in linked list
    By c_weed in forum C++ Programming
    Replies: 5
    Last Post: 11-15-2010, 06:42 PM
  2. Linked List, a pointer problem?
    By SkidMarkz in forum C Programming
    Replies: 3
    Last Post: 09-16-2008, 10:39 AM
  3. sorted linked list...why seg faults!
    By S15_88 in forum C Programming
    Replies: 4
    Last Post: 03-24-2008, 11:30 AM
  4. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 03:19 PM
  5. Warnings with Pointer In Linked List
    By charIie in forum C Programming
    Replies: 8
    Last Post: 12-27-2007, 05:18 PM

Tags for this Thread