linked_list.h File Reference

Detailed Description

Date

Sept 12, 2019

Author

Jonathan Moriarty

Design Philosophy

This is a basic doubly linked list data structure. Each entry in the list has a void* which can point to any data.

Data can be added or removed from the head or tail in O(1) time, making this suitable as a queue or stack.

Usage

push() and pop() add and remove from the tail of the list.

unshift() and shift() add and remove from the head of the list.

addIdx() and removeIdx() add and remove from the middle of the list, by index. These run in O(N), not O(1).

removeEntry() can remove a specific entry.

Links are allocated, so when done with a list, be sure to call clear() when done.

Example

Creating an empty list:

// Use calloc to ensure members are all 0 or NULL
list_t* myList = calloc(1, sizeof(list_t));

Adding values to a list:

// Malloc the value to be persistent
// push to tail
uint32_t* val1 = malloc(sizeof(uint32_t));
*val1          = 1;
push(myList, (void*)val1);
// unshift to head
uint32_t* val2 = malloc(sizeof(uint32_t));
*val2          = 2;
unshift(myList, (void*)val2);

Iterating over a list:

// Iterate over all nodes
node_t* currentNode = myList->first;
while (currentNode != NULL)
{
    // Print the nodes
    printf("%d, ", *((uint32_t*)currentNode->val));
    currentNode = currentNode->next;
}

Removing values from a list:

// Remove from head
uint32_t* shiftedVal = shift(myList);
// Remove from tail
uint32_t* poppedVal = pop(myList);

Go to the source code of this file.

Data Structures
struct	node
	A node in a doubly linked list with pointers to the previous and next values (which may be NULL), and a void* to arbritray data. More...
struct	list_t
	A doubly linked list with pointers to the first and last nodes. More...

Typedefs
typedef struct node	node_t
	A node in a doubly linked list with pointers to the previous and next values (which may be NULL), and a void* to arbritray data.

Functions
void	push (list_t *list, void *val)
	Add to the end of the list.
void *	pop (list_t *list)
	Remove from the end of the list.
void	unshift (list_t *list, void *val)
	Add to the front of the list.
void *	shift (list_t *list)
	Remove from the front of the list.
bool	addIdx (list_t *list, void *val, uint16_t index)
	Add at an index in the list.
void	addBefore (list_t *list, void *val, node_t *entry)
	Insert a value into the list immediately before the given node.
void	addAfter (list_t *list, void *val, node_t *entry)
	Insert a value into the list immediately after the given node.
void *	removeIdx (list_t *list, uint16_t index)
	Remove at an index in the list.
void *	removeEntry (list_t *list, node_t *entry)
void	clear (list_t *list)
	Remove all items from the list.

---

Data Structure Documentation

node

struct node

Data Fields
void *	val	A pointer to the data for this node.
struct node *	next	The next node in the list.
struct node *	prev	The previous node in the list.

list_t

struct list_t

Data Fields
node_t *	first	The first node in the list.
node_t *	last	The last node in the list.
int	length	The number of nodes in the list.

Typedef Documentation

node_t

typedef struct node node_t

A node in a doubly linked list with pointers to the previous and next values (which may be NULL), and a void* to arbritray data.

Function Documentation

push()

void push	(	list_t *	list,
		void *	val )

Add to the end of the list.

Parameters

list	The list to add to
val	The value to be added

pop()

void * pop

(

list_t *

list

)

Remove from the end of the list.

Parameters

list	The list to remove the last node from

Returns

The value from the last node

unshift()

void unshift	(	list_t *	list,
		void *	val )

Add to the front of the list.

Parameters

list	The list to add to
val	The value to add to the list

shift()

void * shift

(

list_t *

list

)

Remove from the front of the list.

Parameters

list	The list to remove from

Returns

The value from the first node

addIdx()

bool addIdx	(	list_t *	list,
		void *	val,
		uint16_t	index )

Add at an index in the list.

Parameters

list	The list to add to
val	The value to add
index	The index to add the value at

Returns

true if the value was added, false if the index was invalid

addBefore()

void addBefore	(	list_t *	list,
		void *	val,
		node_t *	entry )

Insert a value into the list immediately before the given node.

If the given node is NULL, inserts at the end of the list

Parameters

list	The list to add the entry to
val	The new value to add to the list
entry	The existing entry, after which to insert the value

addAfter()

void addAfter	(	list_t *	list,
		void *	val,
		node_t *	entry )

Insert a value into the list immediately after the given node.

If the given node is NULL, inserts at the beginning of the list

Parameters

list	The list to add the entry to
val	The new value to add to the list
entry	The existing entry, after which to insert the value

removeIdx()

void * removeIdx	(	list_t *	list,
		uint16_t	index )

Remove at an index in the list.

Parameters

list	The list to remove from
index	The index to remove the value from

Returns

The value that was removed. May be NULL if the index was invalid

removeEntry()

void * removeEntry	(	list_t *	list,
		node_t *	entry )

Remove a specific entry from the linked list by node_t. This relinks the entry's neighbors, but does not validate that it was part of the given list_t. If the given node_t was not part of the given list_t, the list length will desync.

Parameters

list	The list to remove an entry from
entry	The entry to remove

Returns

The removed value from the entry, may be NULL if the entry was invalid

clear()

void clear

(

list_t *

list

)

Remove all items from the list.

Parameters

list	The list to clear