src/LinkedList.c File Reference

a doubly-linked list data structure, with location-aware functionality. More...

#include "LinkedList.h"
#include "misc.h"
#include "MemoryManager.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

Functions
Functions on Link structures
These functions operate on Link structures.
int	isHead (Link *list)
	tells if a given Link is the head sentinel.
int	isTail (Link *list)
	tells if a given Link is the tail sentinel.
Link *	addAfter (Link *list, void *data)
	location-aware function to add a link after a given link.
Link *	addBefore (Link *list, void *data)
	location-aware function to add a link before a given link.
void *	delete (Link *list)
	delete the given link, and return its data.
void	addLinkBefore (Link *list, Link *newLink)
	location-aware method to add a link before another link.
Link *	removeLink (Link *list)
	location-aware method to remove a link, and return it.
Functions on LinkedList structures
These functions operate on LinkedList structures.
LinkedList *	createLinkedList (void)
	create a new empty linked list
void	destroyLinkedList (LinkedList *linkedList)
	destroy a linked list
void	destroyLinkedListWithClean (LinkedList *linkedList, void(*clean)(void *))
	destroy a linked list and run a clean function on the data in each link.
void	copyLinkedList (LinkedList *destination, LinkedList *source)
	copy a linked list
int	equal (LinkedList *list1, LinkedList *list2, int(*comparator)(void *, void *))
	Compare two linked lists to see if they are equal.
int	contains (LinkedList *linkedList, void *data, int(*comparator)(void *, void *))
	decide if a linked list contains a piece of data.
Link *	addFirst (LinkedList *linkedList, void *data)
	A location-aware function to add data to the beginning of a linked list.
Link *	addLast (LinkedList *linkedList, void *data)
	A location-aware function to add data to the end of a linked list.
void *	getFirst (LinkedList *linkedList)
	return the first piece of data in a linked list
Link *	removeFirst (LinkedList *linkedList)
	remove the first link from a linked list
Link *	removeLast (LinkedList *linkedList)
	Remove and return the last link from a linked list.
void	deleteLast (LinkedList *linkedList)
	delete the last link in the linked list
void	printListAbbv (LinkedList *linkedList, void(*printFunc)(void *))
	Print the first 10 items in the linked list.
void	printList (LinkedList *linkedList, void(*printFunc)(void *))
	Print the items in the linked list.
int	length (LinkedList *linkedList)
	Compute the number of data elements in a linked list.
int	isEmpty (LinkedList *linkedList)
	Determine if a linked list is empty.

---

Detailed Description

a doubly-linked list data structure, with location-aware functionality.

Author:

Darren Strash (first name DOT last name AT gmail DOT com)

Copyright (c) 2011 Darren Strash. This code is released under the GNU Public License (GPL) 3.0.

See GPL 3.0 here

This file contains two types of functions, those that operate on Links and those that operate on LinkedLists. These have not been optimized for speed or memory usage.

Sentinels are used as the head and tail to mark the first Link and the last Link in the LinkedList. This makes the logic for adding and removing Links more succinct.

---

Function Documentation

Link* addAfter	(	Link *	list,
		void *	data
	)

location-aware function to add a link after a given link.

Parameters:

	list	The link that we want to add our data after.
	data	A peice of data to put in the added link.

Returns:

A pointer to the Link that was added after list.

Link* addBefore	(	Link *	list,
		void *	data
	)

location-aware function to add a link before a given link.

Parameters:

	list	The link that we want to add our data before.
	data	A peice of data to put in the added link.

Returns:

A pointer to the Link that was added after list.

Link* addFirst	(	LinkedList *	linkedList,
		void *	data
	)

A location-aware function to add data to the beginning of a linked list.

Parameters:

	linkedList	A linked list.
	data	The data that we want to add to the beginning of linkedList.

Returns:

The link where data was placed in the linked list.

Link* addLast	(	LinkedList *	linkedList,
		void *	data
	)

A location-aware function to add data to the end of a linked list.

Parameters:

	linkedList	A linked list.
	data	The data that we want to add to the end of linkedList.

Returns:

The link where data was placed in the linked list.

void addLinkBefore	(	Link *	list,
		Link *	newLink
	)

location-aware method to add a link before another link.

Parameters:

	list	The link that we want to add a link before.
	newLink	The Link to be added after list.

int contains	(	LinkedList *	linkedList,
		void *	data,
		int(*)(void *, void *)	comparator
	)

decide if a linked list contains a piece of data.

Parameters:

	linkedList	A linked list.
	data	The data that we want to look for in linkedList.
	comparator	A function that returns 0 when two data elements are equal.

Returns:

true if linkedList contains data.

void copyLinkedList	(	LinkedList *	destination,
		LinkedList *	source
	)

copy a linked list

Parameters:

	destination	copy the linked list here
	source	copy this linked list

LinkedList* createLinkedList

(

void

)

create a new empty linked list

Returns:

the created linked list

void* delete

(

Link *

list

)

delete the given link, and return its data.

Parameters:

list

The link that we want to get rid of.

Returns:

the data that was in the link, if it was allocated by you, you need to free it..

void deleteLast

(

LinkedList *

linkedList

)

delete the last link in the linked list

Parameters:

linkedList

A linked list.

void destroyLinkedList

(

LinkedList *

linkedList

)

destroy a linked list

If you allocated data that is in each link, then this will cause a memory leak for you.

See also:

destroyLinkedListWithClean

Parameters:

linkedList

The linked list to destroy.

void destroyLinkedListWithClean	(	LinkedList *	linkedList,
		void(*)(void *)	clean
	)

destroy a linked list and run a clean function on the data in each link.

Parameters:

	linkedList	The linked list to destroy.
	clean	A pointer to a function that cleans the data in the links.

int equal	(	LinkedList *	list1,
		LinkedList *	list2,
		int(*)(void *, void *)	comparator
	)

Compare two linked lists to see if they are equal.

Parameters:

	list1	A linked list.
	list2	Another linked list.
	comparator	A function to compare data in the links copy this linked list.

Returns:

true if the input linked lists have the same data in the same order.

void* getFirst

(

LinkedList *

linkedList

)

return the first piece of data in a linked list

Parameters:

linkedList

A linked list.

Returns:

The data in the first link of the linked list.

int isEmpty

(

LinkedList *

linkedList

)

Determine if a linked list is empty.

Parameters:

linkedList

A linked list.

Returns:

Non-zero if the linked list is empty, zero otherwise.

int isHead

(

Link *

list

)

tells if a given Link is the head sentinel.

Parameters:

list

A link structure.

Returns:

true if the link is the head sentinel, false otherwise.

int isTail

(

Link *

list

)

tells if a given Link is the tail sentinel.

Parameters:

list

A link.

Returns:

true if the link is the tail sentinel, false otherwise.

int length

(

LinkedList *

linkedList

)

Compute the number of data elements in a linked list.

Parameters:

linkedList

A linked list.

Returns:

The number of data elements in the linked list.

void printList	(	LinkedList *	linkedList,
		void(*)(void *)	printFunc
	)

Print the items in the linked list.

Parameters:

	linkedList	A linked list.
	printFunc	A function to print the data elements in the linked list.

void printListAbbv	(	LinkedList *	linkedList,
		void(*)(void *)	printFunc
	)

Print the first 10 items in the linked list.

Parameters:

	linkedList	A linked list.
	printFunc	A function to print the data elements in the linked list.

Link* removeFirst

(

LinkedList *

linkedList

)

remove the first link from a linked list

Parameters:

linkedList

A linked list.

Returns:

The first link of the linked list.

Link* removeLast

(

LinkedList *

linkedList

)

Remove and return the last link from a linked list.

Parameters:

linkedList

A linked list.

Returns:

The last link of the linked list.

Link* removeLink

(

Link *

list

)

location-aware method to remove a link, and return it.

Parameters:

list

The link that we want remove and return.

Returns:

the removed link