Doubly Linked List for lite-C

Posted By: OCMvL

Doubly Linked List for lite-C - 12/27/15 20:40

EDIT: The list contained 3 errors that would lead to crashes.
EDIT 2: Several changes due to feedback and other requirements.

Hey all,

Just wrote a little data structure that imitates a doubly linked list from C++'s STL.

This implementation doesn't support everything a list can do, like sorting. Check out the header file for the given functionality.

Unfortunately there is no template functionality in C, so the structure only works with one specific data type. If you need to use lists for various data types, copy the .h and .c files and change the data type and the prefix name. You don't have to duplicate every single function, but I would recommend to do so, since it's more versatile. This list works with char*

For example:

Code:

CListInt.h
CListInt.c
typedef struct CListIntNode
CListInt* CListIntCreate();

CListChar.h
CListChar.c
typedef struct CListCharNode
CListChar* CListCharCreate();

etc.

Ok, so here's how you would use it, and below you find the implementation.

Code:

#include <acknex.h>
#include <default.c>

#include "CList.c"

function main()
{
	CList* mylist = CListCreate();
	
	CListDisplay(mylist);
	
	CListPush(mylist, "Bob");
	CListPush(mylist, "Max");
	CListPush(mylist, "Olly");
	CListPush(mylist, "John");
	CListPush(mylist, "Jim");
	CListPush(mylist, "Olly");
	CListPush(mylist, "Olly");

	CListNode* node = CListFindNode(mylist,"Olly"); // Get the first node that matches "Olly"
	if(node != NULL) CListRemoveNode(mylist, node);

	CListRemoveValue(mylist,"Olly"); // Removes every item that contains "Olly"
	
	CListEraseIndex(mylist, 1); // Remove Max
	
	CListNode* it = CListBegin(mylist);
	while( it != NULL )
	{
		if( str_cmp(it.data,"John") || str_cmp(it.data,"Jim") )
		{
			CListRemoveNode(mylist, it);
		}
		it = CListNext(mylist);
	}
	
	CListDisplay(mylist);
	CListFree(mylist);
	mylist = NULL;
}

Header file (CList.h):

Code:

/*
	Header file for CList class
	Author: Oliver Mistarz
	Purpose: C Doubly Linked List
*/

typedef struct CListNode {
	char* data; // CHNANGE DATA TYPE
	struct CListNode* previous;
	struct CListNode* next;
} CListNode;

typedef struct CList {
	CListNode* firstnode;
	CListNode* lastnode;
	CListNode* iterator;
	CListNode* nextiterator;
	int length;
} CList;

CList* CListCreate();
CListNode* CListBegin(CList* _list);
CListNode* CListNext(CList* _list);
function CListPush(CList* _list, char* _data); // CHNANGE DATA TYPE
int CListLength(CList* _list);
int CListFindIndex(CList* _list, char* _data); // CHNANGE DATA TYPE
CListNode* CListFindNode(CList* _list, char* _data); // CHNANGE DATA TYPE
function CListRemoveFront(CList* _list);
function CListRemoveBack(CList* _list);
function CListRemoveNode(CList* _list, CListNode* _node);
function CListRemoveValue(CList* _list, char* _value); // CHNANGE DATA TYPE
function CListRemoveIndex(CList* _list, int position);
function CListDisplay(CList* _list);
function CListDispose(CList* _list);
function CListFree(CList* _list);

Code file (CList.c):

Code:

#ifndef CList_C
#define CList_C
#include "CList.h"

CList* CListCreate()
{
	CList* this = malloc(sizeof(CList));
	memset(this, 0, sizeof(CList));
	
	this.firstnode = NULL;
	this.lastnode = NULL;
	this.iterator = NULL;
	this.nextiterator = NULL;
	this.length = 0;
	
	return this;
}

CListNode* CListBegin(CList* _list)
{
	if(_list.firstnode != NULL)
	{
		_list.iterator = _list.firstnode;
		_list.nextiterator = _list.iterator.next;
		return _list.iterator;
	}
	return NULL;
}

CListNode* CListNext(CList* _list)
{
	if(_list.nextiterator != NULL)
	{
		_list.iterator = _list.nextiterator;
		_list.nextiterator = _list.iterator.next;
		return _list.iterator;
	}
	return NULL;
}

function CListPush(CList* _list, char* _data) // CHNANGE DATA TYPE
{
	CListNode* newnode = malloc(sizeof(CListNode));
	memset(newnode, 0, sizeof(CListNode));
	newnode.data = _data;
	
	if(_list.firstnode != NULL)
	{
		newnode.previous = _list.lastnode;
		newnode.next = NULL;
		
		_list.lastnode.next = newnode;
		_list.lastnode = newnode;
	}
	else
	{
		newnode.previous = NULL;
		newnode.next = NULL;
		
		_list.firstnode = newnode;
		_list.lastnode = newnode;
	}
	
	_list.length++;
}

int CListLength(CList* _list)
{
	return _list.length;
}

int CListFindIndex(CList* _list, char* _data) // CHNANGE DATA TYPE
{
	CListNode* link;
	int count;
	for(link = _list.firstnode, count = 0; link != NULL; link = link.next, count++)
	{
		if( link.data == _data )
		{
			return count;
		}
	}
	return -1;
}

CListNode* CListFindNode(CList* _list, char* _data) // CHNANGE DATA TYPE
{
	CListNode* link;
	int count;
	for(link = _list.firstnode, count = 0; link != NULL; link = link.next, count++)
	{
		if( link.data == _data )
		{
			return link;
		}
	}
	return NULL;
}

function CListRemoveFront(CList* _list)
{
	if( _list.firstnode != NULL )
	{
		if( _list.firstnode == _list.lastnode )
		{
			free(_list.firstnode);
			_list.firstnode = NULL;
			_list.lastnode = NULL;
		}
		else
		{
			CListNode* tmpDel = _list.firstnode;
			_list.firstnode.next.previous = NULL;
			_list.firstnode = _list.firstnode.next;
			free(tmpDel);
			tmpDel = NULL;
		}
		_list.length--;
	}
}

function CListRemoveBack(CList* _list)
{
	if( _list.firstnode != NULL )
	{
		if( _list.firstnode == _list.lastnode )
		{
			free(_list.firstnode);
			_list.firstnode = NULL;
			_list.lastnode = NULL;
		}
		else
		{
			CListNode* tmpDel = _list.lastnode;
			_list.lastnode.previous.next = NULL;
			_list.lastnode = _list.lastnode.previous;
			free(tmpDel);
			tmpDel = NULL;
		}
		_list.length--;
	}
}

function CListRemoveNode(CList* _list, CListNode* _node)
{
	if( _list.firstnode != NULL )
	{
		if( _node == _list.firstnode )
		{
			CListRemoveFront(_list);
		}
		else if( _node == _list.lastnode )
		{
			CListRemoveBack(_list);
		}
		else
		{
			_node.previous.next = _node.next;
			_node.next.previous = _node.previous;
			free(_node);
			_list.length--;
		}
	}
}

function CListRemoveValue(CList* _list, char* _value) // CHNANGE DATA TYPE
{
	CListNode* link;
	for(link = _list.firstnode; link != NULL; link = link.next)
	{
		if( link.data == _value )
		{
			CListRemoveNode(_list,link);
		}
	}
}

function CListRemoveIndex(CList* _list, int position)
{
	if( position >= CListLength(_list) || position < 0 )
	{
		printf("Index out of bounds");
		return;
	}
	
	CListNode* link;
	int count;
	for(link = _list.firstnode, count = 0; link != NULL; link = link.next, count++)
	{
		if( count == position )
		{
			CListRemoveNode(_list, link);
			return;
		}
	}
}

function CListDisplay(CList* _list)
{
	CListNode* link;
	for(link = _list.firstnode; link != NULL; link = link.next)
	{
		printf("data: %s", link.data); // CHNANGE DATA TYPE
	}
}

function CListDispose(CList* _list)
{
	CListNode* tmp;

	if(_list.firstnode != NULL)
	{
		_list.iterator = _list.firstnode;
		_list.firstnode = NULL;
		while( _list.iterator != NULL )
		{
			tmp = _list.iterator.next;
			free(_list.iterator);
			_list.iterator = tmp;
		}
	}
}

function CListFree(CList* _list)
{
	CListDispose(_list);
	free(_list);
}

#endif

Have fun!

Posted By: sivan

Re: Doubly Linked List for lite-C - 12/28/15 12:07

thanks, it seems to be very useful.

Posted By: OCMvL

Re: Doubly Linked List for lite-C - 01/01/16 14:44

Fixed 3 bugs that would lead to crashes and memory leaks.
Especially when you store pointers in the list.
Please update the CList.c file.

Posted By: WretchedSid

Re: Doubly Linked List for lite-C - 01/01/16 20:13

There are several bugs/issues in this, for example, the find function returns an undefined value when it doesn't find the node, i.e., it is impossible to tell if a value exists. Furthermore, deleting by index is an O(n2) operation worst case, because the length function is, for whatever reason, an O(n) operation. And it's the only really usable deletion function because there is no find function which returns a node directly.

Posted By: WretchedSid

Re: Doubly Linked List for lite-C - 01/01/16 20:15

Plus, what's up with the iterator members? They are completely unnecessary and only add complexity.

Posted By: OCMvL

Re: Doubly Linked List for lite-C - 01/02/16 10:57

Thanks for the feedback.