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!

Last edited by OCMvL; 01/02/16 10:51. Reason: Bugfixes & Changes