Thread: Doubly linked list woes

  1. #1
    Registered User foniks munkee's Avatar
    Join Date
    Nov 2001
    Posts
    343

    Doubly linked list woes

    Hi all,

    Just having a few dramas with doubly linked lists. I am just trying to write an insert function with the following structures. The insert function does not have to insert the data into a sorted list, so basically it can just add another node to the end of a list.

    The trouble I am having is that I figure I can use a for loop to loop through the list until I find the last node.. but my logic is not right. Can anyone make some suggestions?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <memory.h>
    
    #define MAX		50		// The maximum size of the arrays in the struct
    
    typedef struct list DLL;
    typedef struct node NODE;
    
    struct node 
    {
    	void *data;
    	NODE *prior;
    	NODE *next;
    };
    
    struct list
    {
    	long int count;
    	NODE *head;
    	NODE *tail;
    };
    
    typedef struct
    {
    	long int id;
    	char name[MAX];
    	char address[MAX];
    	float salary;
    } PERSON;
    
    typedef struct
    {
    	PERSON details;
    	char department[MAX];
    	char position[MAX];
    } EMPLOYEE;
    
    
    void init_list(DLL *);
    int insert(DLL *, void*, size_t);
    
    int main(void)
    {
    	DLL		*pMylist;
    	EMPLOYEE	*pEmployees;
    
    	if ((pMylist = (DLL *) malloc (sizeof(DLL))) == NULL)
    	{
    		printf("Error: Unable to allocate memory");
    		exit(1);
    	}
    
    	if ((pEmployees = (EMPLOYEE *) malloc (sizeof(EMPLOYEE))) == NULL)
    	{
    		printf("Error: Unable to allocate memory");
    		exit(1);
    	}
    
    	init_list (pMylist);
    
    	printf("Enter a number: ");
    	while (pEmployees->details.id != 999)
    	{
    		scanf("%d", &pEmployees->details.id);
    		insert(pMylist, pEmployees, sizeof(EMPLOYEE));
    		printf("Enter a number: ");
    	}
    
    	free (pMylist);
    	free (pEmployees);
    
    	return EXIT_SUCCESS;
    }
    
    // The function with all the dramas :)
    int insert(DLL *pRoot, void *pData, size_t size)
    {
    	NODE *pNewnode;
    	NODE *pThis;
    	NODE *pNext;
    
    	// Allocate memory for a new node in the list
    	if ((pNewnode = (NODE *) malloc(sizeof(NODE))) == NULL)
    	{
    		printf("Error: Unable to allocate memory for pNewnode");
    		exit(EXIT_FAILURE);
    	}
    
    	// Allocate memory for the input from user
    	if ((pNewnode->data = malloc(size)) == NULL)
    	{
    		printf("Error: Unable to allocate memory for pNewnode->data");
    		exit(EXIT_FAILURE);
    	}
    
    	// Copy user input to node
    	memcpy(pNewnode->data, pData, size);
    
    	// If the first node
    	if (pRoot->head == NULL)
    	{
    		printf("this is the start of a beautiful list");
    		pRoot->head = pNewnode;
    		return 1; 
    	}
    	else
    	{
                                    // This loop is erroneous
    		for (pThis = (pRoot->head); (pNext = pThis->next) != NULL; pThis = pNext)
    		{
    			// Insert next in list
    		}
    	}
    	
                    return 1;
    }
    
    void init_list(DLL *pMylist)
    {
    	pMylist->count = (long) NULL;
    	pMylist->head = NULL;
    	pMylist->tail = NULL;
    }
    This is not the final code obviously, it is a test program to demonstrate the issues that I am having so there could be some other unusual things happening in this code

  2. #2
    Registered User foniks munkee's Avatar
    Join Date
    Nov 2001
    Posts
    343
    Ok - Got it working! Thanks goes to Salem for a post to a previous thread which held the answer! (Should have used search..)

    Ok - new problem. I have modified the insertion code - all I want to do is insert the new data at the end of the list.. no sorting required at this stage.

    However - This function is supposed to be generic, so regardless of what kind of data the user of this function wants to store in list, it should be able to do it.

    For example I can have a root node:
    DLL *root;

    internally (not visible to the user) the list is made of nodes of type NODE * as declared in the above code, but the user should be able to create their own lists by passing their data of any type to the function, for example:

    EMPLOYEE *pEmployees;
    or
    int *pTest;

    My problem is that the function works fine when I am passing data of type EMPLOYEE *, but if I try to pass a pointer of type int * it fails on the memcpy. Any ideas??

    Code:
    int insert(DLL *pRoot, void *pData, size_t size)
    {
    	NODE *pNewnode;
    
    	// Allocate memory for the next node in the list
    	if ((pNewnode = (NODE *) malloc(sizeof(NODE))) == NULL)
    	{
    		printf("Error: Unable to allocate memory for pNewnode");
    		fflush(stdout);
    		exit(EXIT_FAILURE);
    	}
    
    	// Allocate memory for the input from user
    	if ((pNewnode->data = malloc(size)) == NULL)
    	{
    		printf("Error: Unable to allocate memory for pNewnode->data");
    		fflush(stdout);
    		exit(EXIT_FAILURE);
    	}
    	
    	pNewnode->next = NULL;
    	pNewnode->prior = NULL;
    
    	// Copy the data to the new node
    	memcpy(pNewnode->data, pData, size);
    
    	if (pRoot->head == NULL)
    	{
    		pRoot->head = pNewnode;
    		pRoot->tail = pNewnode;
    		pRoot->count = 1;
    	}
    	else
    	{
    		pNewnode->prior = pRoot->tail;
    		pRoot->tail->next = pNewnode;
    		pRoot->tail	= pNewnode;
    		pRoot->count += 1;				// Increase the count for the number of nodes
    	}
    	return 1;
    }
    Last edited by foniks munkee; 03-05-2002 at 05:30 AM.

  3. #3
    Sayeh
    Guest
    Look at the flagbits (about 12 bytes worth of info) prepended to the block to tell how big it is. Then just copy that size. coerce to void pointers.

    Think generic.

    ---

    If you don't know enough to walk the block pointer for its flagbits, then create a macro that caller calls instead which does a 'sizeof()' of their datablock and then passes the address and the size to your 'insert' function.

    enjoy

  4. #4
    Registered User foniks munkee's Avatar
    Join Date
    Nov 2001
    Posts
    343
    Thanks Sayeh, but I am going to have to plead ignorance here..
    Could someone explain this to me?

    Is the problem that I am having above the same as the one I am having with this code snippet? I assumed that by using the
    sizeof operator I was passing the size of the users data?

    Thanks again all

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    
    typedef struct
    {
    	void *data;
    } NODE;
    
    int main(void)
    {
    	NODE *pNode;
    	int  input;
    
    	pNode = (NODE *) malloc (sizeof(NODE));
    	pNode->data = malloc (sizeof(int));
                    // Tests for success of memory allocation go here..
    	
    	printf("Enter an int: ");
    	scanf("%d", &input);
    	
    	memcpy (pNode->data, input, sizeof(input));
    	
    	printf("The number is : %d", pNode->data);
    
    	return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM