Re: Link List In C

#21 28-Jan-2008, 09:53

Quote:

Originally Posted by Peter_APIIT

I want to know how to implement deallocate function because i didn't have any clue.

I not asking you all to wrote for me but at least give me some hint.

CPP / C++ / C Code:

struct LList* list_allocate(struct LList *myList)
{
	int count = 1;

	do
	{
		myList = (struct LList *)malloc(sizeof(struct LList *));
		assert(myList != NULL);
	 // Ptr must initialize No dangling ptr

		if (count == 2)
		{
			fprintf(stdout, "\n\t\t\tList Memory Allocation unsuccessful");
			exit(0);
		}
		count++;
		fflush(stdout);
	}while( LList_ValidateIsAlloc(myList) == 0 && count < 3);

	/* 
	   Continue to loop even though memory is exhausted 
	   for first time but not over second times because
	   this is unrealistic
	*/
	return myList;
}

You probably want to malloc(sizeof(struct LList)) and not the size of the pointer.

Also, separate your list allocation from your list population. List population should probably NEVER be a "feature" of list allocation at the "bottom" API layer.

Populate your list after you've allocated it.

Having "said" that...it doesn't really look as if that's what you're trying to do. You seem to be allocating twice, since you failed to allocate for the size of the list structure, rather you allocated for the size of the list structure pointer and, undoubtedly, found that you couldn't access your tail member.

CPP / C++ / C Code:

// -------------------------------------------------------
void list_deallocate(struct LList *myList)
{
	free(myList);
}

You usually want to make a call to the list management function that ensures that the list is emptied before freeing the list itself.

CPP / C++ / C Code:

// -------------------------------------------------------
void Initialize_List(struct LList *myList)
{
	if (LList_ValidateIsAlloc(myList) != 0) // Not NULL
	{
		myList->head = NULL;
		myList->tail = NULL;
	/*	head->next = NULL;
		head->value = 0;*/
	}
	else
	{
		exit(0);
	}
}

This is probably better done as part of the allocation so that there doesn't need to be two calls. A simpler choice is calloc, which will zero all of the members in the list structure.

CPP / C++ / C Code:

// -------------------------------------------------------
int LList_ValidateIsAlloc(struct LList *myList)
{
	assert(myList != NULL);

	// If allocation is successful, then return true
	if (myList != NULL)
	{
//		fprintf(stdout, "Memory Allocation successful");
		return 1;
	}// Three control structure
	else
	{
		fprintf(stdout, "Memory exhausted");
		return 0;
	}
}

...this code is a complete waste of effort, IMO.

CPP / C++ / C Code:

// -------------------------------------------------------
struct node* node_allocate()
{
	struct node *node;
	int count = 1;

	do
	{
		node = (struct node *)malloc(sizeof(struct node *));
		assert(node != 0);

		count++;

	}while(	node_validateIsAlloc(node) == 0 && count < 3);


	if (node != NULL)
	{
		return node;
	}
	else
	{
		exit(0);
	}
}

Here you've screwed yourself up again by allocating for the size of the pointer and not the size of the structure.

CPP / C++ / C Code:

// -------------------------------------------------------
void Initialize_node(struct node *node, int * numberptr)
{
	node->next = NULL;
	userInput(numberptr);
	node->value = *numberptr;
}

I'd strongly recommend that you separate user I/O from node initialization functions. In other words, get the "value" from the user FIRST and then assign that value to the node value member.

CPP / C++ / C Code:

// -------------------------------------------------------
void InitializeCurrent(struct LList *myList,
							   struct node *node)
{
	if (myList->tail != NULL)
	{
		myList->tail = node;
		myList->head = node;
	}

}

What happened to your asserts...don't you want to ensure that the list and node are valid pointers? I'm not sure what you're trying to do with this function, but the name of the function is undoubtedly "wrong" for whatever it is you're trying to do and what the name "generally means" to someone else who might be reading it. Ask yourself the following:

InitializeCurrent WHAT? The arguments of the function should provide a very powerful hint to the answer of that question. You are passing a list pointer and a node pointer. Are you initializing the current list pointer, the current node pointer or both? In other words, the "API" sorta-kinda sucks in that it is unclear and badly named for whatever it is that you're really trying to accomplish with it.

I think that what you're trying to do is insert an initial node into the list. This is why we write a "list_append" function. If the list is empty, then append will correctly add the "initial node" to the list. All subsequent appends provide for the proper head/tail pointer management.

CPP / C++ / C Code:

// -------------------------------------------------------
int node_validateIsAlloc(struct node *node)
{
	// If allocation is successful, then return true
	if (node != NULL)
	{
		fprintf(stdout, "\n\n\t\t\tNode Memory Allocation successful");
		return 1;
	}
	else
	{
		fprintf(stdout, "Memory exhausted");
		return 0;
	}
}

...another total waste of code.

CPP / C++ / C Code:

// ------------------------------------------------------
void userInput(int *numberptr)
{
	int number;
	
	fflush(stdin);
	printf("\n\n\t\t\t\tEnter a value : ");
	fflush(stdin);
	scanf("%d", &number);

	*numberptr = number;
}

I'm not very excited by the direction this function takes. Why even have the "int number" variable? Why not ensure that numberptr is a valid pointer and then simply scanf (if you're going to use scanf) with the pointer passed in...rather than spend so much additional "effort" to assign it later?

Also, as I mentioned, I'd probably do something like:

initialize a new node
ask user for a number (can use node's value member to hold the response)
append the node to the list

CPP / C++ / C Code:

// ------------------------------------------------------
struct LList* InsertBehind(struct LList *myList, struct node *node)
{	
	if (myList->head == NULL)
	{
		myList->head = node;
		myList->tail = node;	// Traversal ptr          

		myList->tail->next = NULL;
		node->next = NULL;
		return myList;
	}
	else
	{
		while (myList->tail != NULL)
		{
			myList->tail->next = node;  // Previous node point to newly node
			myList->tail = node;  // Traversal to new node	
			return myList;
		}
	}

	
/*
	// Find length of List

	while (current != NULL)
	{
		current = node->next;
		length++;
	}

	printf("\n\n\t\t\tLength of list is %d", length);
*/


}
// ------------------------------------------------------
void length_of_List(struct LList *myList)
{
	struct node *traversal;
	int length = 1;
	
	traversal = myList->head;

	length = 1;
	while (traversal->next != NULL)
	{
		traversal = traversal->next;
		length++;
	}

	printf("\n\n\t\t\t\tLength of List is %d", length);
}

...so why do you have code to find the length of the list in two places? Why doesn't the code that needs to know the length of the list call its own "get length" function?

...and, WHY doesn't the get length function RETURN the length of the list?

Here is a very good idea to learn right away and to keep in mind for as long as you are going to write C programs. Separate user I/O from "core API." That is, if you want to tell the user how many nodes are in the list, do something like:

CPP / C++ / C Code:

int length_of_list( const struct LList* pList ); /* prototype */
printf( "There are %d nodes in the list\n", length_of_list( &list ) );

This way, if a piece of code that manages the list needs to also know the length of the list, it can use the same body of code. This is how we separate the user I/O with the core API.

:davis:

Peter_APIIT · #22 28-Jan-2008, 20:42

Quote:

Also, separate your list allocation from your list population. List population should probably NEVER be a "feature" of list allocation at the "bottom" API layer.

I not really understand what u mentioned above.
What is list population ? Is it list_append function ?

CPP / C++ / C Code:


void Initialize_List(struct LList *myList)
{
	if (LList_ValidateIsAlloc(myList) != 0) // Not NULL
	{
		myList->head = NULL;
		myList->tail = NULL;
	/*	head->next = NULL;
		head->value = 0;*/
	}
	else
	{
		exit(0);
	}
}

I will use calloc to zero(NULL) the pointer rather than waster stack memory.

Quote:

I'd strongly recommend that you separate user I/O from node initialization functions. In other words, get the "value" from the user FIRST and then assign that value to the node value member.

I really want to follow your advise but i don't know how to do that because i am quite stupid.

Any good programming articles ?

API is almost same with library where programmer can include this program into many other program to achieve reuseability.

A billion thanks for your help.

Peter_APIIT · #23 29-Jan-2008, 03:27

CPP / C++ / C Code:

void userInput(int *numberptr)
{
	int number;
	
	fflush(stdin);
	printf("\n\n\t\t\t\tEnter a value : ");
	fflush(stdin);
	scanf("%d", &number);

	*numberptr = number;
}

The reason i use this techniques because i don't know how to directly scanf from user using ptr. 

A billion thanks for your help.

#24 29-Jan-2008, 16:00

Quote:

Originally Posted by Peter_APIIT

CPP / C++ / C Code:

    //scanf("%d", &number);
    //*numberptr = number;
    scanf( "%d", &p_node->value );

The reason i use this techniques because i don't know how to directly scanf from user using ptr.

A billion thanks for your help.

... a billion is perhaps overstated. A few hundred million is plenty...

:davis:

#25 29-Jan-2008, 16:54

Quote:

Originally Posted by Peter_APIIT

I not really understand what u mentioned above.
What is list population ? Is it list_append function ?

list_append would be one way of populating a linked list, right? By population, I mean "adding nodes to the list."

list_insert_node_at ...would be another way.
list_append_list ...is another.
...etc.

Quote:

Originally Posted by Peter_APIIT

I will use calloc to zero(NULL) the pointer rather than waster stack memory.

It isn't so much of a waste of stack space that I'm concerned about, rather, you have a function that is a total waste of your time and effort. Try to remember that whatever code you write, you'll have to spend time debugging and maintaining over time. A function that is an "internal function" that can be done away with very easily is a waste of "energy" from your perspective and from the perspective of CPU processing cycles.

Quote:

Originally Posted by Peter_APIIT

I really want to follow your advise but i don't know how to do that because i am quite stupid.

...if that is what you believe, you're screwed!

Quote:

Originally Posted by Peter_APIIT

Any good programming articles ?

I'm sure that there are many.

Quote:

Originally Posted by Peter_APIIT

API is almost same with library where programmer can include this program into many other program to achieve reuseability.

Yes...at least you've essentially said it. An API is a set of interfaces used by programmers to accomplish some meaningful work. A library is a packaging method used to provide (usually) object files that provide functionality desired by other programmers. A library *is* made available to other programmers THROUGH its API. Therefore, for any usable library, it MUST have an API...at least this is true in the context that we're talking about now. There are libraries that have "single APIs" that "evolve" or are "discovered" during runtime, but let's focus on the traditional set of libraries common to most C and C++ programmers.

:davis:

Peter_APIIT · #26 30-Jan-2008, 02:05

What is the differences between library and API ?

Do i mixed between list allocate and list population ?

I try to calloc it but this doesn't set my pointer to nowhere.

My Initialize_list set head and tail point to nowhere, then if this head and tail is null, node added to it and else do another job.

Is this a good method or techniques ?

Below is my latest program :

CPP / C++ / C Code:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h> // memset

#include "Link_List.h"

// -------------------------------------------------------
/*
   1. Insert Behind            // Done
   2. Insert In Front          // Done
   3. Random Insert Front-nth   // Done
   4. Remove Behind until zero or one only    // Done
   5. Remove In Front
   6. Random Remove -nth
   7. Display                    // Done
   8. Length   Index            // Done
   9. Palindrome
   10. Full Reverse             // Circular Link List
   11. merge                    // Done  SortedMerge MergeSort
   12. Count a particular int
   13. Get_Node_At_Index
   14. Split List
   15. Remove Duplicates
   16. Swap
   17. Empty          // Done
   18. Calcualte number of node can malloc 
       from heap memory


Random cannot in head and tail

Double Link List
Circular Link List
Double Circular Link List
Associate Link List
Skip List

Josephus problem

Searching
move-to-front heuristic = Once an elemnt found move to 
                          first node
Index

*/



 /* 
	Random must have a index to indicate the postion where
    almost same as array in order to achieve fast 
	processing
*/


// -------------------------------------------------------

// tail->next = head->next; Circular Link List

void draw();

// --------------------List Function----------------------

struct LList* list_allocate(struct LList *);
void list_deallocate(struct LList *);

void Initialize_List(struct LList *);

int LList_ValidateIsAlloc(struct LList *); 


struct LList* InsertBehind(struct LList *, struct node *);
struct LList* InsertFront(struct LList *, struct node*);
struct LList* RandomInsert(struct LList *, struct node*);
// Random Insert cannot insert at first node
struct LList* RemoveBehind(struct LList *);
struct LList* MergeList(struct LList *, struct LList *);


int get_Value_at_index(struct LList *);

int Validate_Index(struct LList *, int); 
int isEmpty(struct LList *);
int length_of_List(struct LList *);  


// --------------------Node Function----------------------

struct node* node_allocate(); 
void node_deallocate(struct node *); 


void Initialize_node(struct node *, int *); 
int node_validateIsAlloc(struct node *);   

void userInput(int *);
void display(const struct LList *);



// ------------------------------------------------------
int main(int argc, char *argv[]) // char **argv
{
	struct LList *myList = 0;
	struct LList *myListSecond = 0;
	struct node *node;

	int length = 0, result, number, *numberptr;

	numberptr = &number;
	
	draw();
	                  
	myList = list_allocate(myList); // Call by reference
	Initialize_List(myList);


// 1 node
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);//	InitializeCurrent(myList, node);
	myList = InsertBehind(myList, node);

// 2 node
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);
	myList = InsertBehind(myList, node);

// 3 node
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);
	myList = InsertBehind(myList, node);

// 4 node
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);
	myList = InsertBehind(myList, node);

// ----------------------------------------------------

// 2 List
	myListSecond = list_allocate(myList);
	Initialize_List(myListSecond);

// 1 node of 2 list
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);
	myListSecond = InsertBehind(myListSecond, node);

    myList = MergeList(myList, myListSecond);

	// InsertFront
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);
	myList = InsertFront(myList, node);

	length = length_of_List(myList);
	display(myList);

	// Random Insert 
	node = node_allocate();
	userInput(numberptr);
	Initialize_node(node, numberptr);
	myList = RandomInsert(myList, node);


	length = length_of_List(myList);
	display(myList);


	myList = RemoveBehind(myList);
	display(myList);


	result = get_Value_at_index(myList);

	node_deallocate(node);
	list_deallocate(myList);
	
	return 0;
}

// ------------------------------------------------------
void draw()
{
	int loop;

	printf("\n\n\n\t\t");

	for (loop=0;loop<60;loop++)
	{
		printf("-");
	}
	
	printf("\n\n\t\t\t  Welcome to newly Link List Simulation Program");
	printf("\n\n\n\t\t");
	for (loop=0;loop<60;loop++)
	{
		printf("-");
	}
	printf("\n\n\n\n");
	
}
// -------------------------------------------------------
struct LList* list_allocate(struct LList *myList)
{
	int count = 1;

	do
	{
		myList = (struct LList *)malloc(sizeof(struct LList));
		assert(myList != NULL);
	 // Ptr must initialize No dangling ptr

		if (count == 2)
		{
			fprintf(stdout, "\n\t\t\tList Memory Allocation unsuccessful");
			exit(0);
		}
		count++;
		fflush(stdout);
	}while( LList_ValidateIsAlloc(myList) == 0 && count < 3);

	/* 
	   Continue to loop even though memory is exhausted 
	   for first time but not over second times because
	   this is unrealistic
	*/

	return myList;
}

// -------------------------------------------------------
void list_deallocate(struct LList *myList)
{
	if (myList != NULL)
	{
		free(myList);
		myList = NULL;
	}
	else
	{
		exit(0);
	}
}
// -------------------------------------------------------
void Initialize_List(struct LList *myList)
{
	if (LList_ValidateIsAlloc(myList) != 0) // Not NULL
	{
		myList->head = NULL;
		myList->tail = NULL;
	}
	else
	{
		exit(0);
	}
}
// -------------------------------------------------------
int LList_ValidateIsAlloc(struct LList *myList)
{
	assert(myList != NULL);

	// If allocation is successful, then return true
	if (myList != NULL)
	{
//		fprintf(stdout, "Memory Allocation successful");
		return 1;
	}// Three control structure
	else
	{
		fprintf(stdout, "Memory exhausted");
		return 0;
	}
}
// -------------------------------------------------------
struct node* node_allocate()
{
	struct node *node;
	int count = 1;

	do
	{
		node = (struct node *)malloc(sizeof(struct node));
		assert(node != 0);

		count++;

	}while(	node_validateIsAlloc(node) == 0 && count < 3);


	if (node != NULL)
	{
		return node;
	}
	else
	{
		exit(0);
	}
}

// -------------------------------------------------------
void node_deallocate(struct node *node)
{
	if (node != NULL)
	{
		free(node);
		node = NULL;
	}
	else
	{
		exit(0);
	}
}	
// -------------------------------------------------------
void Initialize_node(struct node *node, int * numberptr)
{
	node->next = NULL;
	
	node->value = *numberptr;
}
// -------------------------------------------------------
int node_validateIsAlloc(struct node *node)
{
	// If allocation is successful, then return true
	if (node != NULL)
	{
		fprintf(stdout, "\n\n\t\t\tNode Memory Allocation successful");
		return 1;
	}
	else
	{
		fprintf(stdout, "Memory exhausted");
		return 0;
	}
}
// ------------------------------------------------------
void userInput(int *numberptr)
{
	int number;
	
	fflush(stdin);
	printf("\n\n\t\t\t\tEnter a value : ");
	fflush(stdin);
	scanf("%d", &number);

	*numberptr = number;
}
// ------------------------------------------------------
struct LList* InsertBehind(struct LList *myList, struct node *node)
{	
	if (myList->head == NULL)
	{
		myList->head = node;
		myList->tail = node;	// Traversal ptr          

		myList->tail->next = NULL;
		node->previous = NULL;
		node->next = NULL;

		return myList;
	}
	else
	{
		while (myList->tail != NULL)
		{
			myList->tail->next = node;  // Previous node point to newly node
			node->previous = myList->tail;  // New node point to previous node   
			myList->tail = node;  // Traversal to new node	
			return myList;
		}
	}
}
// ------------------------------------------------------
struct LList* InsertFront(struct LList *myList, struct node *node)
{
	struct LList *tempHead;
	
	tempHead = (struct LList *)malloc(sizeof(struct LList *));
    assert(tempHead != 0);

	if ( LList_ValidateIsAlloc(tempHead) == 1 )
	{
		tempHead->head = myList->head;
		node->next = myList->head;
		node->previous = NULL;
		myList->head = node;
	}
	else
	{
		exit(0);
	}

	free(tempHead);

	return myList;
}
// ------------------------------------------------------
struct LList* RandomInsert(struct LList *myList, struct node *node)
{
	struct node *traversal_First;
	struct node *traversal_Second;
	struct node *dummy_one;
	struct node *dummy_two;

	// Position of node insert
	int index, length = 1; 

	traversal_First = myList->head;
	traversal_Second = myList->head;
	dummy_one = myList->head;
	dummy_two = myList->head;

	do
	{
		printf("\n\n\t\t\t\tEnter a index : ");
		scanf("%d", &index);  // Validate index no exceed length of list
	
		if ( Validate_Index(myList, index) == 1 )
		{
			length = 1;
			while (myList->tail != NULL && traversal_Second != NULL)
			{
				if (length == index)
				{
					traversal_First = traversal_First->previous;
					traversal_First->next = node;
					node->next = traversal_Second;
					node->previous = traversal_First;
					traversal_Second->previous = node;
					goto exit;
				}

				traversal_First = traversal_First->next;
				traversal_First->previous = dummy_one;
				dummy_one = traversal_First;

				traversal_Second = traversal_Second->next;
				traversal_Second->previous = dummy_two;
				dummy_two = traversal_Second;

				length++;
			}
			exit:
				return myList;
		}
	}while( Validate_Index(myList, index) == 0);
}
// -----------------------------------------------------
struct LList* RemoveBehind(struct LList *myList)
{
	struct node *traversal;
	struct node *dummy;

	int length = 1;
	int numberNode;

	fprintf(stdout, "\n\n\t\t\tHow many removed node count from behind : ");
	scanf("%d", &numberNode);

	traversal = myList->head;

	length = 1;
	while (traversal->next != NULL)
	{
		traversal = traversal->next;
		length++;
	}

	// 1 2 3 4 5 
	numberNode = length - numberNode;

	do
	{
		dummy = myList->tail;
		myList->tail = myList->tail->previous;
		dummy->value = NULL;
		node_deallocate(dummy); // free what pointed by dummy  Error
		length--; 

	}while(length != numberNode);

	myList->tail->next = NULL;

	return myList;

}
// -----------------------------------------------------
struct LList* MergeList(struct LList *first, struct LList *second)
{
	struct node *dummy;

	dummy = first->tail;

	first->tail->next = second->head;  // first list point to second list
	first->tail = first->tail->next;   // traverse to new tail after merge list
	first->tail->previous = dummy;    // tail node point back to second last node

	second = NULL;
	dummy = NULL;
	
	free(second);
	free(dummy);

	return first;
}
// ------------------------------------------------------
int get_Value_at_index(struct LList *myList)
{
	struct node *traversal;
	int length = 1, index, value;
	
	traversal = myList->head;

	fprintf(stdout, "\n\n\t\t\t\tEnter an index : ");
	scanf("%d", &index);

	length = 1;
	do
	{
		if (index == length )
		{
			value = traversal->value;
			goto exit;
		}

		traversal = traversal->next;
		length++;
	}while (traversal->next != NULL && index != length);
	
	exit:
		value = traversal->value;
		fprintf(stdout, "\n\n\t\t\t\tValue at node %d is %d\n\n", index, value);
	return value;
}

// ------------------------------------------------------
int Validate_Index(struct LList *myList, int index)
{
	struct node *traversal;
	int length = 1;

	traversal = myList->head;

	length = 1;

	while (traversal->next != NULL)
	{
		traversal = traversal->next;
		length++;
	}

	if (index < length)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// ------------------------------------------------------
int isEmpty(struct LList *myList)
{
	if (myList->head == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// ------------------------------------------------------
int length_of_List(struct LList *myList)
{
	struct node *traversal;
	int length = 1;
	
	traversal = myList->head;

	length = 1;
	while (traversal->next != NULL)
	{
		traversal = traversal->next;
		length++;
	}

	printf("\n\n\t\t\t\tLength of List is %d", length);
	

	return length;
}
// ------------------------------------------------------
void display(const struct LList * myList)
{
	printf("\n\n\n");

	struct node *traversal;
	int length;

	traversal = myList->head;

	length = 1;
	while(traversal != NULL)
	{
		printf("\t\t\t\tNode %d of List : %d\n", length, traversal->value);
		traversal = traversal->next;
		length++;
	}
	
}
// ------------------------------------------------------

CPP / C++ / C Code:

#ifndef _LList_
#define _LList_

// Single Node
struct node
{
	int value;
	struct node *next;
	struct node *previous;
};


// Consists of many nodes
struct LList
{
	struct node *head;
	struct node *tail;
};

	
// Add index to struct

#endif

Peter_APIIT · #27 31-Jan-2008, 03:01

How to remove duplicates value or string in link list ?

What i try so far ?

CPP / C++ / C Code:

struct LList* RemoveDuplicates(struct LList *myList)
{
	struct node *traversal;
	int *numberptr, length = 1;

	traversal = myList->head;

	length = length_of_List(myList);

	numberptr = (int *) malloc (sizeof(int) * length);
	assert(numberptr != 0);

	length = 1;
	while(traversal != NULL)
	{
		*(numberptr + length - 1) = traversal->value;
		traversal = traversal->next;
		length++;
	}




	return myList;
}

#28 31-Jan-2008, 15:35

Quote:

Originally Posted by Peter_APIIT

Is this a good method or techniques ?

Not particularly...

I don't mean to be rude, but your code is all over the place. You do not seem to grasp the fundamentals of the basic notion of pointers, memory allocation and how all of this stuff works together. This is not your fault, but you're trying to do WAY TOO MUCH CODE before you understand the BASICS. Start VERY SIMPLY and work up from there...

Here is a GOOD STARTING PLACE for you. You can take the code out of this "single big file" and put it into several smaller files, but for now, I recommend that you just make one file so that when you post here, we don't have to look at several files to see where you've made mistakes.

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// Single Node
struct node
{
    int value;
    struct node *next;
    struct node *previous;
};

// Consists of none, one or possibly more nodes
struct LList
{
    struct node *head;
    struct node *tail;
};

struct LList* list_allocate()
{
    struct LList * myList = (struct LList *)calloc(sizeof(struct LList), 1);
    return myList;
}

void list_deallocate(struct LList *pLList )
{
    if( pLList != NULL ) // don't try to deallocate a null pointer
    {
        // first try to empty the list
        // list_empty(pLList); // not yet implemented!
        free( pLList );
        pLList = 0;
    }
}

int main()
{
    struct LList *myList = 0;
    //struct node *node    = 0; // comment this back in when we actually need it

    myList = list_allocate();

    if( myList != NULL )
    {
        // now add nodes to the list

        // do something meaningful with the nodes in the list

        // now empty and deallocate the list so we can go return cleanly
        list_deallocate( myList );
    }
    else
    {
        // print error message...
    }

    return 0;
}

Output: (nothing)

valgrind/memcheck (a portion of the output from running valgrind):

Code:

==17287== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1)
--17287--
--17287-- supp:   11 dl-hack3
==17287== malloc/free: in use at exit: 0 bytes in 0 blocks.
==17287== malloc/free: 1 allocs, 1 frees, 8 bytes allocated.
==17287==
==17287== All heap blocks were freed -- no leaks are possible.

BUILD on this starting point. If you ALLOCATE anything using malloc/calloc, be sure that you DEALLOCATE it with a corresponding call to free!

Don't add functionality TOO QUICKLY. Figure out how to implement "node_allocate" and "list_append" BEFORE GOING FURTHER. Write code in main that allocates a single node and appends it to your list. At that point, write a "list_empty" function that removes all of the nodes in the list by traversing the links and freeing the nodes using "node_deallocate."

Then, add a "list_print" (or whatever you want to call it) so that you can print out the value for each of the nodes in your list. A simple and good step is to loop through (in main or in a function that you call from main) adding nodes with values of 1 through 10 to the list, print the list and then empty the list and deallocate the list. Once you've done that much, you're ready for the more challenging list management and list manipulation functions.

Also, in this case, I don't think that the "Full Reverse" task has anything to do with circularly linked lists. You can eliminate some complexity by making this list singularly linked AND not circular.

:davis:

Peter_APIIT · #29 03-Feb-2008, 21:40

I will follow your advise.

Thanks.

#30 04-Feb-2008, 10:02

Quote:

Originally Posted by Peter_APIIT

I will follow your advise.

Thanks.

No problemo. Note that "advise" means to give advice. You will want to use "I will follow your advice" in the future. English is a strange and difficult language.

:davis:

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
game problem using linkedListType.h and random function	eureka360	C++ Forum	5	16-Feb-2007 11:48
C++ class -- Please help	vnca_1	C++ Forum	3	14-Jun-2006 13:31
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 14:12
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 15:13