linkedlist.h File Reference

This header file contains thee structures and functions needed to work with doubly-linked lists. More...

Typedefs
typedef linkedlist_adt *	LinkedList
	Structure representing a doubly-linked list.
typedef linkedlist_node *	LinkedListIterator
	Structure to hold a doubly-linked list iterator.
Functions
LinkedList	LL_New ()
	Creates a new linked list, with no elements.
void	LL_Free (LinkedList list)
	Destroys the specified linked list.
int	LL_Size (LinkedList list)
	Returns the size of the linked list.
int	LL_Empty (LinkedList list)
	Determines if the list is empty (has no elements), or not.
LinkedListIterator	LL_Begin (LinkedList list)
	Returns an iterator to the first element in the list.
LinkedListIterator	LL_End (LinkedList list)
	Returns an interator after the last element in the list.
LinkedListIterator	LL_Next (LinkedList list, LinkedListIterator it)
	Returns an iterator to the next element in the list.
void	LL_Add (LinkedList list, LinkedListIterator it, void *el)
	Inserts data in the list, before the specified position.
void *	LL_Remove (LinkedList list, LinkedListIterator it)
	Removes the specified element from the list.
void *	LL_Get (LinkedList list, LinkedListIterator it)
	Gets the data stored in the specified element from the list.
void	LL_Update (LinkedList list, LinkedListIterator it, void *el)
	Updates the data contained in the specified position from the list.
LinkedListIterator	LL_Find (LinkedList list, void *el)
	Searches for data in the list.

---

Detailed Description

This header file contains thee structures and functions needed to work with doubly-linked lists.

Author:

Stefan Bucur

It contains functions for creating a linked list, destroying it, manipulating elements, finding an element, as well as checking a list's size.

---

Typedef Documentation

typedef struct linkedlist_adt* LinkedList

Structure representing a doubly-linked list.

The structure contains pointers to the first and last items in the list as well as the item count for the list. However, accessing the structure members should be done only with the appropriate functions.

Element data is stored using a void pointer. Thus, one should note that there is no way to tell what kind of data is stored in the list or in a particular element of the list.

See also:

See also: LL_New(), LL_Free()

typedef struct linkedlist_node* LinkedListIterator

Structure to hold a doubly-linked list iterator.

The structure contains links to the next and previous elements and is used for navigating in the list and managing element data.

See also:

See also: LL_Add(), LL_Remove(), LL_Update, LL_Get(), LL_Find(), LL_Begin(), LL_End(), LL_Next()

---

Function Documentation

void LL_Add	(	LinkedList	list,
		LinkedListIterator	it,
		void *	el
	)

Inserts data in the list, before the specified position.

The function adds the data specified by the el void pointer in the list, at the position specified by the it iterator. A new element is created and inserted before it . If it is NULL the the element is added at the end of the list.

The el pointer must point to a memory zone which has been already initialized and holds the data to be stored in the list. The function doesn't make any kind of verifications regarding the value of el .

Parameters:

	list	the list in which to add.
	it	iterator specifying the position to add.
	*el	element data.

LinkedListIterator LL_Begin

(

LinkedList

list

)

Returns an iterator to the first element in the list.

The functions returns aniterator to the first element in the list.

Parameters:

list

list to get the iterator to the first element of.

Returns:

an iterator to the first element in the list, or NULL if the list is empty.

int LL_Empty

(

LinkedList

list

)

Determines if the list is empty (has no elements), or not.

In fact the function returns the value of the count == 0 expression. Thus, directly modifying the count structure member will lead to inaccurate results.

Parameters:

list

list to be tested.

Returns:

1 if the list is empty, 0 otherwise.

LinkedListIterator LL_End

(

LinkedList

list

)

Returns an interator after the last element in the list.

The function returns an iterator at the end of the list. Thus, in this implementation it always returns NULL.

Parameters:

list

an iterator for this list will be returned.

Returns:

always returns NULL.

LinkedListIterator LL_Find	(	LinkedList	list,
		void *	el
	)

Searches for data in the list.

The function searches for the data specified by the el in the given list.

Note:

This version of LinkedList uses for comparision strict pointer comparison. Further versions may include the possibilty to specify a comparator to provide more flexible searching.

Parameters:

	list	the list in which to search.
	*el	data to search for.

Returns:

returns a LinkedListIterator pointing to the position in the list where the data was found, or NULL otherwise.

void LL_Free

(

LinkedList

list

)

Destroys the specified linked list.

Memory used by the linked list as well as all elements is freed. Thus, trying to access the data in a destroyed list (e.g. through a pointer) will most likely result in a Access violation / segfault.

Parameters:

list

the list to be destroyed. A LinkedList structure.

void* LL_Get	(	LinkedList	list,
		LinkedListIterator	it
	)

Gets the data stored in the specified element from the list.

The function retrieves data from the list element specified by the iterator it .

Parameters:

	list	the list to retrieve data from.
	it	iterator specifying the position in the list.

Returns:

the data stored at the specified position in the list, or NULL if the iterator is NULL or does not belong to the list.

LinkedList LL_New

(

)

Creates a new linked list, with no elements.

The function creates a doubly-linked list structure and reserves memory for it. No element is created, nor memory reserved for.

See also:

Adding elements should be done with LL_Add()

LinkedListIterator LL_Next	(	LinkedList	list,
		LinkedListIterator	it
	)

Returns an iterator to the next element in the list.

The function returns an iterator to the next element in the list. The current element is given through an interator, obtained through a call to LL_Begin() or subsequent calls to LL_Next().

Parameters:

	list	the list for which the next element is required.
	it	iterator specifying current position in the list.

Returns:

an iterator to the next element in the list or NULL if either the iterator points to LL_End() (is NULL), or does not belong to the list.

void* LL_Remove	(	LinkedList	list,
		LinkedListIterator	it
	)

Removes the specified element from the list.

The function removes the element specified by the iterator it from the list list. The memory for the data stored in the element is not freed.

Parameters:

	list	the list from which to remove the element.
	it	iterator specifying the position of the element to be removed.

Returns:

the data stored at the location specified by the iterator. If the iterator is NULL , does not exist in the list, or points to the end of the list, the function returns NULL.

int LL_Size

(

LinkedList

list

)

Returns the size of the linked list.

The function returns the number of elements in the specified linked list. Note that the function returns the value of the count element. Thus, directly modifying the count structure member will lead to inaccurate results.

Parameters:

list

list whose length is to be returned.

Returns:

the number of elements in the list.

void LL_Update	(	LinkedList	list,
		LinkedListIterator	it,
		void *	el
	)

Updates the data contained in the specified position from the list.

The function updates the data of the element specified by the iterator it . The old data is discared and the element will point to the new data.

Parameters:

	list	the list to update the data in.
	it	the position of the element whose data is to be updated (replaced).
	*el	void* pointer to a memory location containing new data.

---