Minimal Linked List library for arduino

Linked lists are like arrays but they can be dinamically sized while program is running. There are many implementations but this is very basic, customizable, optimizable, and fun. Special for small platforms like arduinos

how to install

• through arduino ide library manager (recommended), search for MinimalLinkedList in data processing category
• manually, by downloading this repo as zip and decompress it into your library folder

class documentation

• MinimalLinkedList<MyType> myList: template based constructor, you first need to declare your custom data type (see faq below)
• MyType* myList.insert(): allocates ram to create a new default element, then inserts it to your list and returns a pointer to
• size_t myList.count(): returns the current list elements count
• MyType* myList.walk(Function *callback, bool extract = false): executes a callback function in list elements from the newest, when callback function return true it stops the iteration and returns a pointer to matched element, but if never happens and reaches the end of the list it returns a null pointer. Additionally you can set extract = true to extract (i.e. remove) the element from list
• callback function: bool callback(MyType someVar): can be used to test elements against some condition or to modify them directly

basic usage example

// load the library
#include <MinimalLinkedList.h>

// create your custom data type
struct Point{
  int x = 0;
  int y = 0;
};

// instance a linked list of your type (points)
MinimalLinkedList<Point> points;

// insert and get a default point (0,0) in the list
Point *p1 = points.insert();

// modify the actual point
p1->x = 3;
p1->y = 4;

// write a callback function to get the most recent point over X axis
// it has to be "bool myFunc(MyType someVar)"
bool pointOverX(Point p){
  if ( p.y == 0 )
    return true;
  return false;
}

// get the actual point using the callback function above
Point *pointHorGet = points.walk(*pointOverX);

// extract (i.e. get + remove) the actual point with the callback function above
// almost the same, but notice the "true" argument
Point *pointHorExt = points.walk(*pointOverX, true);

// get the most recent point over Y axis, now using an anonymous function
Point *pointVer = points.walk([](Point p){
  if ( p.x == 0 )
    return true;
  return false;
});

// delete the newest point with X greater than some value, using an anonymous function
// if you need to pass some var into the callback func, you need to make it static or global before (what will make it not thread-safe also)
static int maxX;
maxX = 5;
points.walk([](Point p){
  if ( p.x > maxX )
    return true;
  return false;
}, true);

faq

• why can't i make it work with integers, floats or chars?
• in assignment operations like int a = b() primitives and derived data types copy their values and store them in different memory locations (i.e. they are assigned by copy) breaking the link with previously reserved memory space... however you can store a single primitive or derived type in 1-element array and get a pointer to
• so why the callback function handles the actual data type directly instead a pointer?
• the callback function is not executed where you see declared, is executed later inside the linked list, and there it has direct access to list elements, so using pointers inside would be a silliness
• why insert() and walk() return pointers instead of actual objects?
• because pointers are assigned by reference, i.e. they can point where actual data resides in memory (unlike assigned by copy), if no pointers were used you couldn't be able to modify elements inside list... i cracked my head many days understanding this (i am a self-learner xD)
• why did you used new/delete() instead malloc()/free()?
• AFAIK both functions/operators allocates ram in heap free store
• because new also initializes the allocated ram with default values and malloc() doesn't, so newly created elements would have garbage
• because we are actually in C++ and i CAN
• why did you name the function count() instead size() or length() to get list size/length that is more common?
• because size and length in C often return single byte lengths instead number of group elements regardless their byte-size, and i wanted to avoid confussions, count() returns number of elements not bytes used... think of it like count() in SQL :)
• why do you wrote a single method for all actions involving iteration?, is confusing
• because sketch/ram space optimization... why to write duplicated code if you can use the same function with minor adjustments?, try to understand anonymous functions in C, they were very satisfying to me
• how can i make this library work with single primitives like ints?
• see included examples, there is an ArrayList example xD
• how can i write a function/snippet to empty the whole list?

while ( myList.count() ){
  myList.walk([](MyType t){return true;}, true);
}

OLD README: how to create a minimal Linked List implementation on arduino

surely there are many linked list implementations for arduino, some of them are (in no particular order):

• ArduinoQueue
• LinkedList
• Arduino Linkedlist Library
• LinkedPointerList
• QList
• others i don't know

but where ram memory are highly constrained and for learning, i wrote my own implementation

what are Linked Lists?

is a group of elements of same type, like an array but dynamic sized

in C, C++ and other languages and platforms (like Arduino) there are Arrays... they are a contiguous sequence (in memory space) of elements of same type... as they are contiguous, array must be defined at compile time so it results in fixed size

but what to do if you need a dynamic sized "array" that could be shrink or enlarge while program is running as needed?... i needed this to manage session cookies for an http server i am writing, if i define an array with space for let's say 10 cookies and there is 1 client connected then there is a waste of memory, and if an 11th client comes then he couldn't connect ... so then came the Linked List concept... i heard it before in Java, i used but never get interested how it works until now (Arduino pushes me to learn new things :))

but how they work?

https://en.wikipedia.org/wiki/Linked_list

like arrays, is also a list of elements not necessarily contiguous, in which the basic element is called a "Node", which holds your data and has a pointer to next node, so basically a linked list is a chain of nodes (hence the name)... each node's pointer points to the address where next node resides so nodes could be anywhere in the memory, but that memory block must be reserved (allocated) for nodes could persist and not be overwritten eventually

you need a pointer to first node, in each node a pointer to the next one, and in last node a pointer to NULL... you can insert a node anywhere just by switching pointers with nodes already in the list, same for removing them (and freeing the memory next)... there are many types of linked lists, double linked, circular, cached, etc., but here we will make the most simple and light

LIST:    .->.------.    .->.------.    .-> NULL
        /   | data |   /   | data |   /
head --'    | next +--'    | next +--'
            '------'       '------'



INSERTING:            .->.------.
                      |  | data |
         .->.------.  |  | next +-->.------.    .-> NULL
        /   | data |  |  '------'   | data |   /
head --'    | next +--'      v      | next +--'
            '------'         v      '------'



REMOVING :            .------.(free)
                      | data |
         .->.------.  | next |  .->.------.    .-> NULL
        /   | data |  '------'  |  | data |   /
head --'    | next +------------'  | next +--'
            '------'               '------'

advantages

• evidently, can insert or remove nodes randomly while running, making it dinamically sized
• can store any data type(s), even arrays or structs, all nodes the same type like arrays
• very simple and light implementation

disadvantages

• to access any element you need to iterate the list from the start, so could be not so efficient under intense work conditions
• they tend to fragmentate memory with use (generate not contiguous free blocks), especially with large and very dynamic lists
• adds some memory overhead, represented by next node pointers and related functions
• this implementation is single threaded... if you have multiple running threads, race conditions could appear or one can undo what other made, turning it a mess

this implementation (edit: the one before class library)

i could make an arduino library (even i tried), but in sake of optimization, simplicity and learning consider this sketch more like a "code snippet".... it has only 2 methods, one for inserting nodes and other for list iteration that can do everything else... this way the code keeps damn small and efficient (as in memory usage)... is not so "abstracted" so you need to supply callback functions and dirt your hands for everything you want to do, learning a lot in the process (as i did).... for example you could modify this sketch to emulate and handle "associative array" like nodes, by adding members to Node struct