Linked list – Library for Arduino

As I was struggling with my HC-05 Bluetooth module which might return an unspecified count of lines when responding to a command in AT (attention) mode, I have written a small library for a single chained list. It is just a dynamic data structure supporting chronological pushing while it allows iterating through all its elements.

/*
  List.h - Linked List (single chain)
  Created by B. Blechschmidt (Ovex), 16 August 2013
  Released into the public domain.
*/
#ifndef List_h
#define List_h

#include "Arduino.h"

template <class T> class ListElement
{
	public:
		ListElement(T Element)
		{
			Content = Element;
			NextElement = NULL;
		}
		~ListElement()
		{
			delete NextElement;
		}
		T Content;
		ListElement<T> *NextElement;
};

template <class T> class List
{
  public:
	~List()
	{
		Clear();
		delete FirstElement;
		delete LastElement;
		delete CurrentElement;
	}
	List()
	{
		FirstElement = NULL;
		CurrentElement = NULL;
		LastElement = NULL;
		Length = 0;
	}
	void Clear()
	{
		ToBegin();
		delete CurrentElement;
		FirstElement = NULL;
		CurrentElement = NULL;
		LastElement = NULL;
		Length = 0;
	}
	void Push(T Element)
	{
		if(LastElement)
		{
			LastElement->NextElement = new ListElement<T>(Element);
			LastElement = LastElement->NextElement;
		}
		else
		{
			FirstElement = new ListElement<T>(Element);
			LastElement = FirstElement;
			CurrentElement = FirstElement;
		}
		Length++;
	}
	bool IsEnd()
	{
		if(CurrentElement)
		{
			return false;
		}
		else
		{
			return true;
		}
	}

	bool IsEmpty()
	{
		return FirstElement == NULL;
	}

	unsigned long Count()
	{
		return Length;
	}
	void ToBegin()
	{
		CurrentElement = FirstElement;
	}
	void Next()
	{
		if(CurrentElement)
		{
			CurrentElement = CurrentElement->NextElement;
		}
	}
	T GetValue()
	{
		return CurrentElement->Content;
	}
  private:
	  unsigned long Length;
	  ListElement<T> *FirstElement;
	  ListElement<T> *LastElement;
	  ListElement<T> *CurrentElement;
};

#endif

Usage:

#include <List.h>

void setup()
{
	List<String> StringList;
	StringList.Push("a");
	StringList.Push("b");
	StringList.Push("c");

	//Iterate through list
	bool ListEmpty = StringList.IsEmpty(); //false
	Serial.println("Count: "+String(StringList.GetCount()));
	StringList.ToBegin();
	while(!StringList.IsEnd())
	{
		Serial.println(StringList.GetValue());
		StringList.Next();
	}
	/*Output:
		Count: 3
		a
		b
		c
	*/
	StringList.Clear();
	ListEmpty = StringList.IsEmpty(); //true
}

void loop()
{
}
Bookmark the permalink.

4 Responses to Linked list – Library for Arduino

  1. This is great! thanks a lot for sharing. I was creating my own linked list for the same thing, bluetooth incoming data, split the test in parts, etc… I’ll use this instead of my own messy code.

  2. stu says:

    Hi Just looking at the code should n’t the Clear method iterate the list as it looks like its only deleting the first item in the list leaving a memory leak for all other objects on the list.

  3. stu says:

    my mistake, deleting the first element is recursive deleting the other elements. Although this means you could never extend to allow deleting 1 item from the list without lots of refactoring.

Leave a Reply

Your email address will not be published.