Linear Linked List Library

Overview

list.h

Implementations for singly-linked and doubly-linked list functions.

Basic Working Example

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct node {
    int key;
    struct node *next;
} node_t;

node_t *head = NULL;
 
int main(){
    node_t *item, *tmp;

    item = malloc(sizeof(node_t));
    item->key = 5;
    item->next = NULL;
    SL_APPEND(head, item);

    SL_FOREACH(head, item) printf("%d\n", item->key);

    SL_FOREACH_SAFE(head, item, tmp){
        SL_DELETE(head, item);
        free(item);
    }

    return 0;
}

Functions Available

Every function has a doubly-linked list counterpart. The doubly-linked list version takes the exact same arguments. They are referred to as DL_ and the function name. For example, DL_EMPTY and DL_APPEND.

Function Name Arg 1 Arg 2 Arg 3 Arg 4
SL_EMPTY head int
SL_APPEND head node
SL_PREPEND head node
SL_SORT head fn *
SL_LAST head node
SL_REVERSE head
SL_CONCAT head head
SL_LENGTH head int
SL_FOREACH head node
SL_FOREACH_SAFE head node node
SL_INDEX head node int
SL_SEARCH head fn * query node
SL_DELETE head node

SL_APPEND

This function appends a node to the end of a linked list.

Argument 1: The head node of the list

Argument 2: The node to be appended to the list

Call:

SL_APPEND(head, node);

SL_PREPEND

This function prepends a node to the end of a linked list.

Argument 1: The head node of the list

Argument 2: The node to be prepended to the list

Call:

SL_APPEND(head, node);

SL_SORT

This function sorts a linked list in O(n log n) time.

Argument 1: The head node of the list

Argument 2: A function pointer to a compare function

Call:

SL_SORT(head, fn *);

Note: The function pointer must be able to identify if one key is less than or equal to another and return a value accordingly. The check to swap is if the return value of the compare function is less than or equal to zero. For strings, you can use strcmp() and for integers you can simply return the difference.

SL_REVERSE

This function reverses a linked list. For example, a->b->c->d becomes d->c->b->a.

Argument 1: The head node of the list

Call:

SL_REVERSE(head);

SL_CONCAT

This function concatenates two linked lists. For example, list1: a->b and list2: c->d becomes a->b->c->d.

Argument 1: The head node of the first list

Argument 2: The head node of the second list

Call:

SL_CONCAT(head, head);

SL_LENGTH

This function stores the length of a linked list in the second argument.

Argument 1: The head node of the list

Argument 2: An integer to store the length of the list

Call:

SL_LENGTH(head, length);

Note: The second argument will be clobbered!

SL_FOREACH

This function iterates over the length of the list and returns the node at each step. This is helpful when operating on every node in the list (printing the list or altering each node).

Argument 1: The head node of the list

Argument 2: A temporary node to store each intermediary node

Call:

SL_FOREACH(head, node);

SL_FOREACH_SAFE

This function iterates over the length of the list and returns the node at each step. This is helpful when operating on every node in the list (printing the list, altering each node, or destroying the list).

Argument 1: The head node of the list

Argument 2: A temporary node to store each intermediary node

Argument 3: A temporary node to safely store the next node

Call:

SL_FOREACH_SAFE(head, node, tmp);

SL_INDEX

This function returns a node at the nth position in the list. The list is zero-indexed, so if you ask for the 0th node, you'll get the head.

Argument 1: The head node of the list

Argument 2: A temporary node to store the returned node

Argument 3: An integer index value

Call:

SL_INDEX(head, node, index);

Note: Check for a proper return value after a function call to SL_INDEX. If your index is out of range, a NULL node will be returned.

SL_SEARCH

This function searches the list and compares each node to the query using the function pointer argument. If a valid match is found, the matching node is placed in the fourth argument node. This is one of the most versatile functions due to the nature of the function pointer. You're given the ability to search for nodes, keys (int, char *, ...), etc. The limit to which you can search the list is your ability to write a proper compare function.

Argument 1: The head node of the list

Argument 2: A function pointer to a compare function

Argument 3: The item you want to query

Argument 4: A temporary node to store the returned node

Call:

SL_SEARCH(head, cmp, query, node);

Note: Check for a proper return value after a function call to SL_SEARCH. If a node is not found, a NULL node will be returned.

SL_DELETE

This function removes a node from the linked list. SL_DELETE only unlinks the node! The memory must be freed to avoid a memory leak.

Argument 1: The head node of the list

Argument 2: The node to be removed

Call:

SL_DELETE(head, node);

Recipes

Below are some common use cases for the above functions.

SL_FOREACH

Print an entire list

SL_FOREACH(head, node) printf("%d\n", node->key);

SL_FOREACH_SAFE

Delete an entire list

See SL_DELETE.

SL_SEARCH

Search by key

/* For integers */
int cmp(node_t *a, int key){
    return a->key - key;
}
SL_SEARCH(head, cmp, 5, node);

/* For strings */
int cmp(node_t *a, char *key){
    return strcmp(a->key, key);
}
SL_SEARCH(head, cmp, "Hello, world!", node);

/* For pointers */
int cmp(node_t *a, void *ptr){
    return (a->data.ptr == ptr) ? 0 : 1;
}
SL_SEARCH(head, cmp, ptr, node);

SL_DELETE

Delete a single node

SL_DELETE(head, node);
free(node);

Delete an entire list

SL_FOREACH_SAFE(head, node, tmp){
    SL_DELETE(head, node);
    free(node);
}
Issues
  • SL_DELETE in SL_FOREACH doesnt work

    SL_DELETE in SL_FOREACH doesnt work

    When deleteing an element during FOREACH and free the element the for loop cant acess next member because the item which holds the next pointer is already freed

    opened by exellian 1
  • typeof undefined when `-std=` specified

    typeof undefined when `-std=` specified

    how to reproduce: compile Basic Working Example with any -std

    cc -std=c11 test.c
    

    and it produce:

    list.h:11:17: warning: implicit declaration of function 'typeof' [-Wimplicit-function-declaration]
       11 |                 typeof(head) _tmp = head; \
          |                 ^~~~~~
    

    and more


    with -Dtypeof=__typeof__ everything compiles fine

    so i suggest change all typeof() to __typeof__()

    https://stackoverflow.com/a/27508311

    opened by dm9pZCAq 0
Owner
Nick Bulischeck
Kernel-mode developer and CTF fanatic. Engineer at CrowdStrike. Former President of Clemson University Cyber Security.
Nick Bulischeck
Own implementation of a linked list stack in C++.

Linked-List-Stack-CPP Own implementation of a linked list stack in C++. This is my manual implementation of a linked list stack. This stack is abstrac

Adam Peters 1 Oct 21, 2021
linked list implementation (C++)

linked-list linked list implementation (C++) author's name: Artem Kolpakov date: 06/06/2021 Hello there! Here is important information about my linked

Artem Kolpakov 1 Dec 28, 2021
Data Structure Studying Group: array, linked list, stack, queue, deque, tree, graph. Summary of these concepts are descripted in the markdown files.

DATA_STRUCTURE STUDY ?? CURRICULUM ✔️ Day1 array linked list ✔️ Day2 circular linked list double linked list polynomial addtion reverse linked list ✔️

Soyeon Kim 3 Jun 26, 2022
100daysofDSA - Explore about arrays, linked lists, stacks & queues, graphs, and more to master the foundations of data structures & algorithms!

Explore about arrays, linked lists, stacks & queues, graphs, and more to master the foundations of data structures & algorithms!

null 25 Jun 6, 2022
libsais is a library for linear time suffix array and burrows wheeler transform construction based on induced sorting algorithm.

libsais libsais is a library for fast (see Benchmarks below) linear time suffix array and Burrows-Wheeler transform construction based on induced sort

Ilya Grebnov 89 Jun 21, 2022
Is a linear data structure with O(log n) searches and O(cbrt n) insertions and index lookups.

A binary cube is a linear data structure that contains a sorted two dimensional dynamic array of nodes which each point to a sorted array

null 21 May 17, 2022
simple hash table linear probing method can expand/reduce

hash table a simple c hash table implementation based on https://benhoyt.com/writings/hash-table-in-c/ project can store different data types (data al

Fabio Murer 1 Oct 3, 2021
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..

Access list is a collection of multiple types of lists used during pentesting, collected in one place, created by Undercode This list include a collec

UNDERCODE UTILITIES 7 Jan 6, 2022
A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf::list A drop-in replacement for std::list with (on average): 293% faster insertion 57% faster erasure 17% faster iteration 77% faster sorting 70%

Matt Bentley 115 Apr 11, 2022
A lightweight library of Behavior Trees Library in C++.

A lightweight behavior tree library in C++. NEWS! ?? Thanks to Davide Faconti there is now a more sophisticated version of the library. The new versio

Michele Colledanchise 157 May 29, 2022
A library of generic data structures.

Collections-C A library of generic data structures including a list, array, hashtable, deque etc.. Examples Building and Installing Using the library

Srđan Panić 2.4k Jun 26, 2022
A simple C library for working with KD-Trees

kdtree Overview kdtree is a simple, easy to use C library for working with kd-trees. Kd-trees are an extension of binary search trees to k-dimensional

John Tsiombikas 331 Jun 19, 2022
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

PpHd 493 Jun 20, 2022
C header library for typed lists (using macros and "template" C).

vector.h C header library for typed lists (using macros and "template" C). Essentially, this is a resizable array of elements of your choosing that is

Christopher Swenson 28 May 6, 2022
Directed Acyclic Graph Execution Engine (DAGEE) is a C++ library that enables programmers to express computation and data movement, as task graphs that are scheduled concurrently and asynchronously on both CPUs and GPUs.

Directed Acyclic Graph Execution Engine (DAGEE) is a C++ library that enables programmers to express computation and data movement, as tasks in a graph structure, where edges represent task dependencies

null 23 May 11, 2022
nanoplan is a header-only C++11 library for search-based robot planning.

nanoplan is a header-only C++11 library for search-based robot planning. The primary design goals are correctness, ease-of-use, and efficiency (in tha

Jordan Ford 14 May 17, 2022
An open source library for C

Eric O Meehan C Library Introduction Eric O Meehan's C Library is an open source collection of tools for the C programming language. The project is in

Eric O Meehan 90 Jun 12, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

Lib9wada Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada Usage Compile the library with mak

Lprogrammers Lm9awdine 47 May 29, 2022
Experimental managed C-strings library

Stricks Managed C strings library. ?? API Why ? Because handling C strings is tedious and error-prone. Appending while keeping track of length, null-t

Francois Alcover 79 Jun 21, 2022