Name/Brief Description:

Singly-linked list

Date of Original Submission:

February 7, 2004

Submitted by:

dsmith

License:

None - there is nothing ground breaking here

Detailed Description:

I have posted this previously in a reply, but I wanted to explain it a little more. This is an extremely small and simple singly-linked list routine. It is written entirely as an inline function, so there is no external libraries to call. It is less than 200 lines with comments. This may seem like really simple or redundant code, but almost every project that I do includes this file. In real world programs, the amount of your data is rarely known, so a dynamic storage solution is crucial. With this routine, I am confident that errors are not being caused by my storage code. I have written a tiny example showing the use of the common functions. This may seem like a simple thing where an array would be easier to use, but what size is that array going to be? Also, typecasting can be confusing, but in reality I can make a list that contains any type of data all in the same list.

CPP / C++ / C Code:

#include <stdio.h>
#include "list1.h"

int main()
{
	list*	numbers;
	int*	entry;

	numbers = new list;
	do{
		printf("Enter number(0 to end): ");
		entry = new int;
		scanf("%d",entry);
		if(*entry != 0)
			numbers->add_data((void*) entry);
	}while(*entry != 0);

	printf("Here are your numbers:\n");
	if(!numbers->is_empty()){
		numbers->home();
		do{
			printf("Number: %d\n", *((int*) numbers->get_data()));
		}while(numbers->next());
	}
	return 0;
}

If anyone has any question, comments or improvements, you can post them here.

Problems/Limitations:

• I have not done alot of testing on the set_mark/goto_mark calls
• All data has to be typecast
• Uses C++ class, so it is not portable to strictly c compilers

I have done several updates to my linked list implementation.

1. I changed the home() call to return a zero if the list is empty so instead of doing this:
   
   CPP / C++ / C Code:

   if(!numbers->is_empty()){
   	numbers->home();
   

   You can just do this:
   
   CPP / C++ / C Code:

   if(!numbers->home()){
   

   Not a huge savings, but every little bit helps.
2. After doing some coding using set_mark/goto_mark I found that these needed to be modified.

I have reposted this file. Again comments or questions are encouraged.

Okay, in testing my linked list with a data structure test, I found a major flaw in my logic that was extremely inefficient in the placing of a lot of data into the list. By removing one line of this code, I fixed that inefficiency. I have posted this new implementation. (I also deleted the old ones, since I notice that people have been downloading my old implementation).

Attached Files

list1.zip (1.0 KB, 341 views)