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!

It should be

while ( temp != NULL )

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!

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.

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.

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

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!