Linked List

A linked list data structure.

This linked list data structure provides most basic features necessary in a linked list, along with some more advanced ones like iterators, stack functionality, and a generic list data structure that can use a different implementation.

Author
Stephen Brennan
Date
Created Sunday, 3 August 2014

Copyright
Copyright (c) 2013-2016, Stephen Brennan. Released under the Revised BSD License. See the LICENSE.txt file for details.

Typedefs

typedef smb_ll_node

Node structure for linked list.

This must be exposed in order for other data types to be public. This should not be used by users of the library.

typedef smb_ll

The actual linked list data type. “Bare” functions return a pointer to this structure.

Functions

void ll_init(smb_ll * new_list)

Initializes a new list in memory which has already been allocated.

Parameters
  • new_list: A pointer to the memory to initialize.

smb_ll* ll_create()

Allocates and initializes a new, empty linked list.

Return
A pointer to the new list.

void ll_destroy(smb_ll * list)

Frees all the resources held by the linked list without freeing the actual pointer to the list.

If you create a list on the stack and use ll_init to initialize it, calling ll_delete will attempt to free your stack memory (bad). Use this to free all the resources of the list without freeing the pointer.

Parameters
  • list: The list to destroy.

void ll_delete(smb_ll * list)

Frees the resources held by the linked list, and the memory allocated to the smb_ll object.

This is equivalent to calling ll_destroy on the pointer, and then calling smb_free() on the pointer.

Parameters
  • list: A pointer to the list to delete.

smb_list ll_create_list()

Creates a new, empty list, and returns it as an instance of the generic smb_list data structure.

See
smb_list
Return
A generic list interface object.

smb_list ll_cast_to_list(smb_ll * list)

Cast a smb_ll pointer to an instance of the smb_list interface.

See
smb_list
Return
A generic list interface object.
Parameters
  • list: The linked list to cast to a generic list.

void ll_append(smb_ll * list, DATA new_data)

Append the given data to the end of the list.

Parameters
  • list: A pointer to the list to append to.
  • new_data: The data to append.

void ll_prepend(smb_ll * list, DATA new_data)

Prepend the given data to the beginning of the list. All other data is shifted forward one index.

Parameters
  • list: A pointer to the list.
  • new_data: The data to prepend.

void ll_push_back(smb_ll * list, DATA new_data)

Push the data to the back of the list. An alias for ll_append().

Push, of course, refers to its usage in the context of stacks. In other words, the function appends an item at the end fo the list.

Parameters
  • list: A pointer to the list to push to.
  • new_data: The data to push.

DATA ll_pop_back(smb_ll * list, smb_status * status)

Pop data from the back of the list.

Pop, of course, refers to its usage in the context of stacks. In other words, the function removes the item at the back/end of the list and returns it.

Return
The item from the back of the list.
Parameters
  • list: A pointer to the list to pop from.
  • status: Status variable.
Exceptions
  • SMB_INDEX_ERROR: If the list is empty.

DATA ll_peek_back(smb_ll * list, smb_status * status)

Peek at the back of the list.

Peek, of course, refers to its usage in the context of stacks. So this returns the item at the end/back of the list without removing it.

Return
The item from the back of the list.
Parameters
  • list: A pointer to the list to peek from.
  • status: Status variable.
Exceptions
  • SMB_INDEX_ERROR: If the list is empty.

void ll_push_front(smb_ll * list, DATA new_data)

Push the data to the front of the list. An alias for ll_prepend.

See
ll_push_back If the term ‘push’ is unfamiliar.
Parameters
  • list: A pointer to the list.
  • new_data: The data to push.

DATA ll_pop_front(smb_ll * list, smb_status * status)

Pop the data from the front of the list.

See
ll_pop_back If the term ‘pop’ is unfamiliar.
Return
The data from the front of the list.
Parameters
  • list: A pointer to the list to pop from
  • status: Status variable.
Exceptions
  • SMB_INDEX_ERROR: If the list is empty.

DATA ll_peek_front(smb_ll * list, smb_status * status)

Peek at the front of the list.

See
ll_peek_back If the term ‘peek’ is unfamiliar.
Return
The data from the front of the list.
Parameters
  • list: A pointer to the list to peek from.
  • status: Status variable.
Exceptions
  • SMB_INDEX_ERROR: If the list is empty.

DATA ll_get(const smb_ll * list, int index, smb_status * status)

Gets the data from the given index.

However, there is no guarantee that the index was valid. An empty DATA object is returned in that case, and an SMB_INDEX_ERROR is raised.

Return
The data at the specified index, if it exists.
Parameters
  • list: A pointer to the list to get from.
  • index: The index to get from the list.
  • status: Status variable.
Exceptions
  • SMB_INDEX_ERROR: If the given index is out of range.

void ll_remove(smb_ll * list, int index, smb_status * status)

Removes the node at the given index, if the index exists.

If the item is not at the end of the list, the index of every item after this one will be shifted down one.

Parameters
  • list: A pointer to the list to remove from.
  • index: The index to remove from the list.
  • status: Status variable.
Exceptions
  • SMB_INDEX_ERROR: If the given index is out of range.

void ll_insert(smb_ll * list, int index, DATA new_data)

Inserts an item at the specified location in the list.

If the location is not the end of the list, then every item at the given index and after will be shifted up one index. If the provided location is less than 0, the location will be treated as 0. If the provided location is greater than the length of the list, the item will be added to the end of the list.

Parameters
  • list: A pointer to the list to insert into.
  • index: The index to insert at.
  • new_data: The data to insert.

void ll_set(smb_ll * list, int index, DATA new_data, smb_status * status)

Sets an existing element to a new value.

It is illegal to call ll_set() on an out of bounds index. You must use ll_insert() for that.

Parameters
  • list: The list to modify.
  • index: The index of the item to set.
  • new_data: The data to set the index to.
  • status: Status variable.
Exceptions
  • INDEX_ERROR: If the index is out of bounds

int ll_length(const smb_ll * list)

Returns the length of the given list.

Return
The length of the list.
Parameters
  • list: A pointer to the list

int ll_index_of(const smb_ll * list, DATA d, DATA_COMPARE comp)

Returns whether or not the list contains the item.

Parameters
  • list: Pointer to the list.
  • d: The item to search for.
  • comp: The comparator to use. NULL for bit comparison.

void ll_sort(smb_ll * list, DATA_COMPARE cmp)

Stable sort of linked list.

Return
Nothing, but the list is sorted in place.
Parameters
  • list: List to sort.
  • cmp: Comparator for sorting.

smb_iter ll_get_iter(const smb_ll * list)

Get an iterator for the linked list.

Return
an iterator
Parameters
  • list: A pointer to the list.

void ll_filter(smb_ll * list, bool(*test_function)( DATA ))

Remove every element for which test_function returns true.

Parameters
  • list: List to remove from.
  • test_function: Returns true if an element should be removed.

void ll_map(smb_ll * list, DATA (*map_function)( DATA ))

Apply a function to every item in the list.

Calls the function (with one argument) with each element of the list. Then, puts the return value back into the list at the same location. This is all IN PLACE, and thus pretty bad if you need to keep the references for the future.

Return
nothing - the list is modified!
Parameters
  • list: The list to map over.
  • map_function: Function to apply.

DATA ll_foldl(smb_ll * list, DATA start_value, DATA (*reduction)( DATA , DATA ))

Fold a function starting on the left.

Applies `reduction(start_value, list[0])`, then `reduction(result, list[1])`, etc. Returns the final result.

Return
the final result
Parameters
  • list: List to reduce the function along.
  • start_value: Initial value to give to the reduction.
  • reduction: Function to reduce.

DATA ll_foldr(smb_ll * list, DATA start_value, DATA (*reduction)( DATA , DATA ))

Fold a function starting on the right.

Applies `reduction(start_value, list[n-1])`, then `reduction(result, list[n-2])`, etc. Returns the final result.

Return
the final result
Parameters
  • list: List to reduce the function along.
  • start_value: Initial value to give to the reduction.
  • reduction: Function to reduce.

struct smb_ll_node
#include <ll.h>

Node structure for linked list.

This must be exposed in order for other data types to be public. This should not be used by users of the library.

Public Members

struct smb_ll_node* prev

The previous node in the linked list.

struct smb_ll_node* next

The next node in the linked list.

DATA data

The data stored in this node.

struct smb_ll
#include <ll.h>

The actual linked list data type. “Bare” functions return a pointer to this structure.

Public Members

struct smb_ll_node* head

A pointer to the head of the list.

struct smb_ll_node* tail

A pointer to the tail of the list. Useful for speeding up navigation to a particular spot.

int length

The number of items stored in the list.