Basic API

At their core other structures (Queues & Stacks) are just restricted implementations of a Linked List. This API describes the make up of a Doubly Linked List

Core

At its core a Linked List is an organized collection of "objects" that are linked together through references. These objects are not "fully meshed" meaning there is a link between every object to every other object. Instead each object is linked such as to reflect a list like structure. In an example with 3 objects (A, B, C). A and B are connected to each other, and B and C are connected to each other but A and C are not connected to each other.

typedef struct node {
    struct node* next;
    struct node* prev;
    void* data;

} node_t;

More concretely in the definition a node as this ambiguous object which will in fact hold some data, has two references one to its sequential next and previous items as relative to its position in the list.

Applying structure around this idea. A Doubly Linked List list is defined as two nodes which keep references to the beginning head and ending tail of the list as well as a count of items size in the list

typedef struct list {
    node_t* head;
    node_t* tail;
    unsigned long size;

} list_t;

Functions

newNode

Creates a new Node that holds the supplied newItem as its data value

node_t* newNode(void* newItem);

Returns: NULL if unable to allocate memory for the new Node; otherwise the new Node

newList

Creates an empty Linked List

list_t* newList();

Returns: NULL if unable to allocate memory for the new Linked List; otherwise the new Linked List

insertFirst

Adds a new item to the top/beginning of the list, aka position 1

int insertFirst(list_t* list, void* newItem);

Returns: 0 on failure, 1 on success

insertLast

Adds a new item to bottom/end of the list, aka position (current size of the list + 1)

int insertLast(list_t* list, void* newItem);

Returns: 0 on failure, 1 on success

insertAt

Adds a new item at position pos in the list

int insertAt(list_t* list, void* newItem, unsigned long pos);

Returns: 0 on failure, 1 on success

removeFirst

Removes and returns the first item on the list

node_t* removeFirst(list_t* list);

Returns: NULL if the list is empty; otherwise the first item on the list

removeLast

Removes and returns the last item on the list

node_t* removeLast(list_t* list);

Returns: NULL if the list is empty; otherwise the last item on the list

removeAt

Removes and returns an item at position pos on the list

node_t* removeAt(list_t* list, unsigned long pos);

Returns: NULL if the list is empty; otherwise the last item at position pos

destroy

Removes all items of on the list, frees allocated memory

int destroy(list_t* list);

Returns: 0 if the list is already empty or NULL; otherwise 1 if sucessful

getFirst

Gets the item at the top/beginning of the list

node_t* getFirst(list_t* list);

Returns: A copy of the item at position 1 on the list; Caller is responsible for freeing this memory

getLast

Gets the item at the bottom/end of the list

node_t* getLast(list_t* list);

Returns: A copy of the item at position size on the list; Caller is responsible for freeing this memory

getAt

Gets an item at position pos on the list

node_t* getAt(list_t* list, unsigned long pos);

Returns: A copy of the item at position pos on the list; Caller is responsible for freeing this memory

copyNode

Creates a copy of a Node, leaving the original Node untouched. The size of the original Node's data element dataSize is required to ensure adequate space is reserved to copy the data value into the new Node

node_t* copyNode(node_t* origNode, size_t dataSize);

Returns: NULL if the original Node's data element is NULL, if unable to allocate memory for the new Node, or if unable to copy the data value into the new Node; otherwise a copy of the original Node

isEmpty

Answers the question "is the list empty" by looking at the list's size parameter

int isEmpty(list_t* list);

Returns: 0 if false; 1 if true