A doubly linked list implementation in C. The list stores (void) pointers to the data. The actual data is never copied, modified or deleted in this implementation. This allows for the same data to be stored in multiple different lists.
- Fast Stack operations (push/pop)
- Fast Queue operations (pushBack/pop)
- Fast Deque operations (push/pushBack and pop/popBack)
- Forward/Backward iteration with function parameter
| Function | Running Time |
|---|---|
| gll_get / gll_set | O(1 + min{size-i, i} ) |
| gll_first / gll_last | O(1) |
| gll_add | O(1 + min{size-i, i} ) |
| gll_pop / gll_popBack | O(1) |
| gll_push / gll_pushBack | O(1) |
Number of Nodes: 10000000
gll_pushBack() (All): 1016.8580 ms
gll_popBack() (All): 803.8800 ms
gll_push() (All): 655.6550 ms
gll_pop() (All): 793.6100 ms
gll_pushBack() (All): 660.2480 ms
1 * gll_get() (middle): 55.3450 ms
1 * gll_get() (end): 0.0030 ms
1 * gll_get() (begin): 0.0010 ms
1 * gll_set() (middle): 56.5100 ms
1 * gll_set() (end): 0.0010 ms
1 * gll_set() (begin): 0.0010 ms
1 * gll_add() (middle): 54.9220 ms
1 * gll_add() (end): 0.0040 ms
1 * gll_add() (begin): 0.0020 ms
1 * gll_remove() (middle): 55.1510 ms
1 * gll_remove() (end): 0.0030 ms
1 * gll_remove() (begin): 0.0010 ms
gll_each(): 122.4990 ms
gll_eachReverse(): 123.8290 ms
make
make install
make uninstall
make tests
./tests
make performance
./performance
./performance [number of nodes]
Types
Functions
- gll_init
- gll_get
- gll_set
- gll_first
- gll_last
- gll_add
- gll_push
- gll_pushBack
- gll_remove
- gll_pop
- gll_popBack
- gll_each
- gll_eachReverse
- gll_clear
- gll_destroy
| Type & Name | Description |
|---|---|
int size |
number of elements |
gll_node_t *first |
pointer to head node |
gll_node_t *last |
pointer to tail node |
| Type & Name | Description |
|---|---|
void *data |
pointer to data stored at node |
gll_node_t *prev |
pointer to previous node |
gll_node_t *next |
pointer to next node |
Allocates and initializes a new list.
| Prototype: | gll_t *gll_init() |
|---|---|
| Return: | pointer to new list |
Gets the pointer to the data stored at the node in an arbitrary position. Returns NULL if position does not exist.
| Prototype: | void *gll_get(gll_t *list, int position) |
|---|---|
| list | pointer to list to retrieve data from |
| data | pointer to new data to be stored |
| position | position of node in the list |
| Return: | void pointer to previous data or NULL if not found |
Sets the data pointer of a node at an arbitrary position. Returns pointer that was previously stored at that node or NULL if position does not exist.
| Prototype: | void *gll_get(gll_t *list, int position) |
|---|---|
| list | pointer to list to retrieve data from |
| position | position of data in the list |
| Return: | void pointer to data or NULL if not found |
Gets the pointer to the data at the head of the list (position 0). Returns NULL if list is empty.
| Prototype: | void *gll_last(gll_t *list) |
|---|---|
| list | pointer to list to retrieve data from |
| Return: | void pointer to data or NULL if list is empty |
Gets the pointer to the data stored at the tail of the list (last position). Returns NULL if list is empty.
| Prototype: | void *gll_last(gll_t *list) |
|---|---|
| list | pointer to list to retrieve data from |
| Return: | void pointer to data or NULL if list is empty |
Adds a new element at an arbitrary position. Returns -1 if unsuccessful.
| Prototype: | int gll_add(gll_t *list, void *data, int position) |
|---|---|
| list | pointer to list to add data to |
| data | pointer to data to be stored |
| position | position of data in the list |
| Return: | 0 on success, -1 on failure |
Adds a new element at the head of the list (position 0).
| Prototype: | int gll_push(gll_t *list, void *data) |
|---|---|
| list | pointer to list to add data to |
| data | pointer to data to be stored |
| Return: | 0 on success, -1 on failure |
Adds a new element at the tail of the list (last position).
| Prototype: | int gll_pushBack(gll_t *list, void *data) |
|---|---|
| list | pointer to list to add data to |
| data | pointer to data to be stored |
| Return: | 0 on success, -1 on failure |
Removes an element at an arbitrary position. Returns the pointer to the data stored at the removed node, or NULL if unsuccessful.
| Prototype: | int gll_remove(gll_t *list, int position) |
|---|---|
| list | pointer to list to remove data from |
| position | position of element to remove |
| Return: | pointer to data or NULL if not found |
Removes the head of the list (position 0) and return the pointer stored at that position. Returns NULL if list is empty.
| Prototype: | void *gll_pop(gll_t *list) |
|---|---|
| list | pointer to list to remove data from |
| Return: | pointer to data or NULL if list is empty |
Removes the tail of the list (last position) and return the pointer stored at that position. Returns NULL if list is empty.
| Prototype: | void *gll_popBack(gll_t *list) |
|---|---|
| list | pointer to list to remove data from |
| Return: | pointer to data or NULL if list is empty |
Iterates over the entire list from beginning to end and calls the specified function with each element as a parameter. The function must be of return type void and take a void pointer (void *) parameter.
| Prototype: | void gll_each(gll_t *list, void (*function)(void *)) |
|---|---|
| list | pointer to list |
| function | pointer to function |
Iterates over the entire list from end to beginning and calls the specified function with each element as a parameter. The function must be of return type void and take a void pointer (void *) parameter.
| Prototype: | void gll_eachReverse(gll_t *list, void (*function)(void *)) |
|---|---|
| list | pointer to list |
| function | pointer to function |
Clears the entire list and deallocates all nodes. The data that is referenced by each node is not touched.
| Prototype: | void *gll_clear(gll_t *list) |
|---|---|
| list | pointer to list |
Clears the list and deallocates all list-related memory. The data referenced by each node is not touched.
| Prototype: | void *gll_destroy(gll_t *list) |
|---|---|
| list | pointer to list |