Doubly Linked List

June 6, 2004

dsmith

None

This is a simple implementation on a doubly linked list. Both are configured to put data in sorted order. There are two versions included. The first one uses a hash pattern for the find function. This greatly increases the seek times. The second does not implement this feature. For a speed comparison, refer to the Data Structure Test in this forum.

The data type is void* for these structures so that data of any type, including complex structures. Due to this, it is necessary to do some basic type casting when placing and getting data.

Also, since these structures are sorted, a comparison routine needs to be provided by the user program. A sample comparison function for an simple integer type is:

CPP / C++ / C Code:

int compare(void* data1, void* data2)
{
	if(*( (int*) data1 ) > *( (int*) data2) )
		return 1;
	if(*( (int*) data1 ) < *( (int*) data2) )
		return -1;
	return 0;
}

In addition, for the first version of the doubly linked list another routine needs to be created. This is a range function that returns a floating point value indicating the range where a search value is compared to two other locations. A sample of this for an integer value is as follows:

CPP / C++ / C Code:

float range(void* begin, void* end, void* eval)
{
	float	value1;
	float	value2;
	
	value1 = *( (int*) eval ) - *( (int*) begin);
	value2 = *( (int*) end ) - *( (int*) begin);

	if(value2 == 0)
		return 0.0;
	else
		return (value1/value2);	
}

So, which one is better? If you have a larger data set it is worth it to create and call the range function, so use the first list (dlist.h). However, if you are dealing with smaller data sets, the need for a range function diminishes, so the simpler second list (dlist2.h) can be used.

For examples of usage on both of these lists, refer to the Data Structure Test in this forum.

• Written with C++ style syntax, so it won't port to strictly C compilers
• Need to typecast so that it is universally implemented for different types.
• Need to create helper functions in order to use these.

• Inserting data into a linked list is much faster.
• Deleting data from a linked list is much faster.
• No memory reallocation calls are needed.
• No need for a large contiguous memory block.

• Much more intensive to setup.
• Indexing and parsing is slower.

• I have decided to use a c++ implementation. This is because of the ease of using a single class to contain all the data and functions and the ability to absolutely hide the data to the end user.
• I choose to store a generic address that points to data instead of any type of data itself. This allows for this list to store any type of data, including different data types in the same list.
• This particular implementation uses a simple algorithm to guess where the data needs to be inserted and then starts the normal search from there. In testing, I have found that this does speed things up.

//************************************
//*** CONSTRUCT/DESTRUCT FUNCTIONS ***
//************************************
dlist(int type = 0, int search_range = 200);
~dlist();
	
	
//**************************
//*** MOVEMENT FUNCTIONS ***
//**************************
int	next();
int	prev();
int	home();
int	end();
void goto_index(long where);
	
	
//**********************
//*** DATA FUNCTIONS ***
//**********************
void add_data(void* new_data);
void add_atpos(void* new_data);
void add_sort(void* new_data, int (*compare)(void*,void*), float (*range)(void*,void*,void*));
void* get_data();
void* get_atpos(long where);
void rem_data()};
	 
	
//************************
//*** SEARCH FUNCTIONS ***
//************************
int close_search(void* search_data, int (*compare)(void*,void*));
int find_data(void* search_data, int (*compare)(void*,void*),float (*range)(void*,void*,void*));
	
	
//***********************
//*** QUERY FUNCTIONS ***
//***********************
int is_empty();
int	is_home(); 	
int is_end();
long cur_index();
long get_size();
	
	
//***********************************
//*** MARKING/DEMARKING FUNCTIONS ***
//***********************************
void* set_mark();
void goto_mark(void* mark)};
void reindex();

• CPP / C++ / C Code:

  dlist(int type = 0, int search_range = 200);

  This is the constructor. This must be called prior to using the linked list. It configures all initial settings and sets the head and tail.
  It takes two parameters which both have defaults if not given.
  • type
    This indicates whether the list is to contain only unique items. A type 1 is only unique items, a type 0 accepts duplicate items. The default is non-unique(0).
  • search_range
    The search_range indicates at what size, the hash function will start being used. Through testing, I have found that it is best to only call the hash function a single time in any case. For smaller lists, it should not be used.
• CPP / C++ / C Code:

  ~dlist()

  The destructor. This deletes the list. This also removes any left over list links. It does NOT delete the data that these addresses points to as it doesn't know anything about the data that is there. It is recommended that the user program has a function that will parse through the list and delete the data that is pointed to, prior to calling the destructor.
  
• CPP / C++ / C Code:

  int next()

  Navigation command. Positions the current pointer at the next position. Returns 1 upon success and 0 if current can not go to next because it is at the end of the list.
  
• CPP / C++ / C Code:

  int prev()

  Navigation command. Positions the current pointer at the previous position. Returns 1 upon success and 0 if current can not go to previous because it is at the head of the list.
  
• CPP / C++ / C Code:

  int home()

  Navigation command. Positions the current pointer at the head of the list. Returns 1 upon success and 0 if the list is empty.
  
• CPP / C++ / C Code:

  int end()

  Navigation command. Positions the current pointer at the end of the list. Returns 1 upon success and 0 if the list is empty.
  
• CPP / C++ / C Code:

  void goto_index(long where)

  Navigation command. The dlist implementation keeps an internal numerical index of its position. The data itself is not indexed. This function will attempt to go to the index passed in where. It does not return anything. It indexes as far as possible until it finds the index or hits the beginning or ending of the list.
  This function is provided for convenience and not speed. It is not as fast as the name may indicate. It is a very expensive (in terms of processing) as it does several compares.
  
• CPP / C++ / C Code:

  void add_data(void* new_data)

  Data command. This function adds data to the end of the list in an unsorted manner. Generally, this command is not called by the end user. If you are using the dlist implementation, it is probably because you have sorted data. The one exception is if you are storing items that are known to be in order, such as a file read. In this case, this is an extremely fast function (can't be beat!).
  
• CPP / C++ / C Code:

  void add_atpos(void* new_data

  Data command. This adds data at the current position or rather in between current and its previous link. Again, calling this function directly doesn't make a whole lot of sense. It is used internally by add_sort, but I can't think of any reason that the end user would want to call this function. But it is public if you want it.
  
• CPP / C++ / C Code:

  int add_sort(void* new_data, int (*compare)(void*,void*), float (*range)(void*,void*,void*))

  Data command. This is the add command that the end user will generally use. It adds the data according to the sort function and hash function passed (and created) by the user program. 0 is returned upon sucess and -1 is returned if the user program is trying to put an identical data item in a unique list.
  • void* new_data
    This is address of the data to be added, NOT the data itself. dlist does not care what kind of data you use, only where you stick it. This is not as complicated as it may seem. It does require some typecasting (void*) and the user program is responsible for all memory allocation.
  • int (*compare)(void*,void*)
    This is where it gets a little more complicated. dlist has no idea how to sort your data. The user program must provide the compare routine. The structure of this routine is explained below.
  • float (*range)(void*,void*,void*)
    This is where it gets really confusing! In larger sorted lists, I have found that data can be inserted quicker by the limited use of a simple hash that tries to predict where to start the real search. If your data structure is not large or need this level of optimization, I have provided dlist2 which does not use this optimization. As can be seen here this can speed things up. The hash optimized dlist took almost half the time to complete my data structure test as the standard list. Again this function is described below.
• CPP / C++ / C Code:

  void* get_data()

  Data command. This command returns the address of the current position. Again this is going to require some type casting (my_data = (my_data_type*)my_list->get_data()).
  This will return NULL(0) if the list is empty).
  
• CPP / C++ / C Code:

  void* get_atpos(long where)

  Data command. This is simply two functions in 1. It calls the navigation function: goto_index() and then calls the get_data() command. It does reposition the current pointer. This will return NULL(0) if the list is empty).
  
• CPP / C++ / C Code:

  void rem_data()

  Data command. This removes the link from the list and frees any internal memory. In other words, it does not delete the user data (nor can it). The user needs to take care of deleting any allocated memory for the data itself.
  
• CPP / C++ / C Code:

  int close_search(void* search_data, int (*compare)(void*,void*))

  Search command. This is the first of two search routines and generally does not need to be called by the user program, unless you specifically don't want to use the hash function. Both of these functions position the current pointer to the data that is equal to or as close as possible to the search_data. In addtion, these functions returns a 0 if the data is empty or if the search_data is greater than the last item. They return 1 if there is an exact match and a -1 on an in-between match.
  
• CPP / C++ / C Code:

  int find_data(void* search_data, int (*compare)(void*,void*),float (*range)(void*,void*,void*))

  Search command. This is the search command that the user program will generally want to call. It implements the hash and then calls close_search for the finite searching. Since it calls close_search to finalize the search, the return values and functionality are identical.
  
• CPP / C++ / C Code:

  int is_empty()

  Query commmand. This function returms 1 if the list is empty and 0 if not.
  
• CPP / C++ / C Code:

  int is_home()

  Query command. This function returns 1 if the current pointer is at the top of the list and 0 if not.
  
• CPP / C++ / C Code:

  int is_end()

  Query command. This function returns 1 if the current pointer is at the end of the list and 0 if not.
  
• CPP / C++ / C Code:

  long cur_index()

  Query command. This returns the index (counter) of the current pointer. This is internally tracked by the movement of the navigation commands and is not tied to the data. This is also 1-based. (not 0).
  
• CPP / C++ / C Code:

  long get_size()

  Query command. The number of elements are tracked as they are added or deleted. This function returns this number.
  
• CPP / C++ / C Code:

  void* set_mark()

  Marking command. This returns the address of the current pointer to be quickly reset with a call to goto_mark. The use of these functions allows instantaneous movement between user-set points in the structure.
  
• CPP / C++ / C Code:

  void goto_mark(void* mark)

  Marking command. This function is used in conjunction with set_mark to return to a user-set point in the list.
  
• CPP / C++ / C Code:

  void reindex()

  Marking command. At first look, this function may seem very strange. This function is necessary to reposition the index (counter) after a call to goto_mark. This function should never need to be called by the user program. This function is also an unfortunate hit in speed, but it is necessary for the index feature.

• compare
  This function is identical in function to the standard strcmp function. It should return a 0 if the items are the same, a 1 if the first data is greater than the second data and -1 if the first data is less than the second data. Here is a sample using int:
  
  CPP / C++ / C Code:

  int compare(void* data1, void* data2)
  {
  	if(*( (int*) data1 ) > *( (int*) data2) )
  		return 1;
  	if(*( (int*) data1 ) < *( (int*) data2) )
  		return -1;
  	return 0;
  }   
  

  This may seem kind of strange with an int value, but remember this can be used with your own data structures which may have much more complex sorting criteria.
  
• range
  This function again is more complicated. It is designed to be used initially in searches to get close before the more intensive search is conducted. The purpose of this function is to guess where the search_data may fall between these two points. It basically returns a number between 0 and 1, where 0 indicates that the search value is at the first point and 1 indicates that the search value is at the second point. Any number between indicates a percentage of how far the search value is between points. This is a pretty simple equation:
  
  Code:

  range = ( search - first ) / ( last - first )

  
  This obviously works best for evenly distrubuted data. But remember, the intent is to get close (within about 200), not exact. Here is a sample using an integer type:
  
  CPP / C++ / C Code:

  float range(void* begin, void* end, void* eval)
  {
  	float	value1;
  	float	value2;
  
  	value1 = *( (int*) eval ) - *( (int*) begin);
  	value2 = *( (int*) end ) - *( (int*) begin);
  
  	if(value2 == 0)
  		return 0.0; 
  	else 
  		return (value1/value2);
  } 
  

#include <stdio.h>
#include <string.h>
#include "dlist.h"

//Compare function to pass to dlist add_sort
int compare(void* data1, void* data2)
{
	return(strcmp( (char*)data1, (char*) data2) );			// Too easy :)
}  

//range function to pass to dlist add_sort
//For a full string we will only compare the first letter.
float range(void* begin, void* end, void* eval)
{
	float	value1;
	float	value2;

	value1 = *( (char*) eval ) - *( (char*) begin);
	value2 = *( (char*) end ) - *( (char*) begin);

	printf("hash: value1 = %2.2f, value2 = %2.2f\n",value1,value2);
	if(value2 == 0)
		return 0.0; 
	else 
		return (value1/value2);
}  

//Function to allocate exact memory & remove return
char* reduce(char *from)
{
	char*	string = (char*) malloc(strlen(from));
	
	strcpy(string,from);
	if(*(string+strlen(string)-1) == '\n')
		*(string+strlen(string)-1) = 0;
	return(string);
}

//Reads a file and loads it in a list
void read_list(FILE* fp, dlist* stlist)
{
	char 	string[100];
	char*	new_string;
	
	while(fgets(string,100,fp)){
		new_string = reduce(string);			
		stlist->add_data((void*) new_string);	//DLIST: Add at end of list
	}
}

//Outputs strings to file (or screen)
void output(FILE* fp, dlist* stlist)
{
	if(stlist->home()){							//DLIST: Go to top of list
		do{
			fprintf(fp,"%s\n",(char*)stlist->get_data());	//DLIST: Get data
		}while(stlist->next());					//DLIST: Go to next item
	}
}	

void remove_data(dlist* stlist)
{
	if(stlist->home()){							//DLIST: Go to top of list
		do{
			free((char*)stlist->get_data());	//DLIST: Get data
		}while(stlist->next());					//DLIST: Go to next item
	}		
}	

int main(int argc, char* argv[])
{
	dlist*	stlist;
	FILE*	fp;
	char string[100];
	
	if(argc!=2)
		printf("You must include a file to load and save the list\n");
	else{
		stlist = new dlist(0,10);						//DLIST: Call constructor
		if(fp = fopen(argv[1],"r") ){
			read_list(fp,stlist);
			fclose(fp);
		}
		string[0] = 0;
		printf("Enter your strings.  Enter done when finished.\n");
		while(strcmp(reduce(string),"done")){
			printf("String: ");
			fgets(string,100,stdin);
			if(strcmp(reduce(string),"done"))
				stlist->add_sort((void*)reduce(string),compare,range);	//DLIST: Add sorted
		}
		output(stdout,stlist);
		if(fp = fopen(argv[1],"w") ){
			output(fp,stlist);
			fclose(fp);
		}
		else
			printf("Could not open output file!\n");
	
		remove_data(stlist);	
		delete stlist;
	}	
	return 0;
}