Implementing a Doubly Linked List (to be used on an Arduino Board)

• Download source - 170 KB

Contents

• Introduction
  • Why not std::list?
• Risks
• Background
  • How a Doubly Linked List works
• Using the Code
  • Declaration of the template ListItem
  • Private structures and variables
  • Constructor
  • Public methods
    • void Add (ListItem)
    • void RemoveAt (int)
    • ListItem GetAt (int)
    • ListItem First ()
    • ListItem Last ()
    • int Count ()
    • void Clr ()
  • Destructor

Introduction

Working on a personal project, I encountered the use case that I need a class representing a command which has an unknown amount of command parameters. Nothing too difficult, you say? Well - The said project is a program running on an Arduino Board which communicates with a program over a serial interface (I did another article on that topic earlier) where I wanted a command to have a not-yet-known amount of command parameters. So what to do? A dynamic memory re-allocation for a fixed-size array would be very time-wasting, especially on the Arduino board, and it needs much more memory than a simple doubly linked list where each element's memory is allocated (and deleted) separately.

Why not std::list?

I needed a command class which holds the command parameters to behave exactly the same way, no matter whether it was compiled for a Windows or an Arduino Environment - Since the Arduino compiler uses it's own accent of C++, where the std::list isn't included I was not able to use it, which was the major factor of my decision towards a self-implemented list.

Another important decision factor towards the self-implemented solution was the fact that the Arduino board only has a limited storage capability, even for source code - An STL-Port of the std::list would have had a major impact on the source code's size since it implements a lot of operations I may never need, and therefore the decision went towards the do-it-yourself approach - It wouldn't have made any sense to take the std::list and shrink it to what I need, especially since I'd have had no Copyright on the full source code.

On a side note: Yes, there is an STL-Port for Arduino - But it is stated that the STL-Port impacts the Flash and SRAM usage of the Board. Also, there are some issues listed on the GitHub page, some of the are affecting the List-functionality which is another risk - I see it as a great gimmick, but not quite production-ready yet.

Risks

Of course there is a reason why the Arduino platform has not a built-in list implementation yet: Imagine that a board may has only 512 byte of RAM. If you now have an object which needs 2 Byte of RAM each and dynamically add 256 copies of it (in practice even less copies, since the list itself needs RAM, too) to the list the script execution will come to a (terrible) screeching halt because the board ran out of RAM - An overflow happened. Be cautious when using this list, and do not dynamically add stuff to it without setting boundaries before. My main concern is with AList::Add(ListItem): If you add a list item and the added item causes the total objects in the RAM of the board to overflow the board will either hang in a crashed state, or restart and do everything again. Some people have asked me why I don't throw an exception when this scenario happens. I can't, even if I wanted to throw an exception because the Arduino C++ accent doesn't know exceptions.

Background

Implementing a list with only basic features such as adding, removing and clearing the list (plus getting the counter for the list) is not a big deal - I decided to use the Doubly Linked List approach to avoid bigger delays caused by memory allocation operations.

How a Doubly Linked List works

A Doubly Linked List is a collection of elements, linked together using pointers between the single elements. Each element has two pointers: One to the previous element, another one to the next element in the List. Plus, each element has a variable storing the element's value. A graphical representation of a Doubly Linked List therefore looks similar to this:

The above illustration shows a Doubly Linked List, containing three elements (having the value '1', '2', and '3'). The arrows show a pointer from one Doubly Linked List element to another.

Using the code

The code mainly consists of the class representing the list, called AList.

An instance of the class is instantiated easily, for a list of integer values the AList class simply type the following in your source code (don't forget to #include "AList.h"):

AList<int> myListOfIntegers;

It is declared in the header file AList.h as follows:

#ifndef ALIST_H
#define ALIST_H
template <typename ListItem>
class AList{
  private:
      /** Intended for private representation 
          of a ListItem within the AList class - Internal use only!
      @author Marco Bertschi
      */
      struct PrivateListItem{
        PrivateListItem* prv;
        PrivateListItem* nxt;
        ListItem crnt;
      };
    
    PrivateListItem* last;        //!< The last item of the list.
    PrivateListItem* first;        //!< The first item of the list.
    int count;            //!< Zero-based count of items within the list.
  public:
    AList();
    ~AList();
    ListItem First();
        ListItem Last();
    
    int Count();
    void Add(ListItem listItem);
    void RemAt(int index);
    ListItem GetAt(int index);
    void Clr();
};
#endif //ALIST_H 

Declaration of the template ListItem

template <typename ListItem>
class AList{ //....

The first line after the guardians declares that the class AList uses the type ListItem internally as parameter for methods and as field variable. The ListItem is hereby used as a placeholder for the type of which the List will be holding after compilation - For example, if an AList<int> the compiler will generate a new class where it exchanges every occurrence of ListItem with int. You never really notice it, but this is in general how a template works.

Private structures and variables

struct PrivateListItem{
  PrivateListItem* prv;
  PrivateListItem* nxt;
  ListItem crnt;
}; 

The class AList has an internal structure named PrivateListItem - It is used to encapsulate a single Doubly Linked List Element. As written in a previous chapter, it contains a pointer to the next (nxt) and the previous (prv) PrivateListItem plus a variable holding the value of the current item in the List (crnt, has the type of a ListItem).

PrivateListItem* last;        //!< The last item of the list.
PrivateListItem* first;        //!< The first item of the list. 
int count;            //!< Zero-based count of items within the list.

Two private pointers to a PrivateListItem are also held in the AList class: One to the first item of the list and another one to the last item of the list. In addition to that, there is a private integer variable holding the zero-based count of items in the AList, named count (-1 means that the list is empty).

Constructor

The AList class has exactly one default constructor, accepting no arguments. Why is it mentioned anyways?

It is because the default constructor is somewhat important for the internal functionality of the AList class because it initializes the internal count variable to a value of -1. If the initialization step of the said variable would be skipped its value would be undefined, leading to a malfunction of each and every method relying on the on the count variable or AList<ListItem>::Count() method (within and outside of the AList class!). Asking yourself why -1 and not zero? Simples, because I decided to make count zero-based, meaning that a value of zero would say that one element is stored in the list.

 //! Instantiates a new instance of an AList.
/*!
\return        AList<ListItem>        A new instance of an AList.
*/
template <typename ListItem>
AList<ListItem>::AList(){
    count = -1;//-1 == "The list is empty!
}

Public Methods

This chapter explains every public method exposed by the AList class.

void AList<ListItem>::Add(ListItem)

template <typename ListItem>
void AList<ListItem>::Add(ListItem li){
    PrivateListItem* pLItem = new PrivateListItem;
    pLItem->crnt = li;
    if (count > -1){//If the list contains one or more items
        pLItem->nxt = first;
        pLItem->prv = last;
        last->nxt = pLItem;
        first->prv = pLItem; // Missed fix of head to point to new tail
        last = pLItem;
        count++;
    }
     else if (count == -1){//If no items are present in the list
        first = pLItem;
        last = pLItem;
        pLItem->nxt = pLItem; // He is alone and point to himself
        pLItem->prv = pLItem;
        count = 0; 
    }
}

This method adds a ListItem at the end of the list. The code looks a bit special since I have to watch for the case when the list is empty - In this case, the last and the first item of the list point to the same PrivateListItem. If there is already at least one item in the list it is enough to reconnect the pointers between the (former) last, the first, and the newly added list item.

void AList<ListItem>::RemoveAt(int)

template <typename ListItem>
void AList<ListItem>::RemAt(int index){
    if (index <= count){
        PrivateListItem* pLItem = last;
        for (int i = 0; i <= index; i++){
            pLItem = pLItem->nxt;
        }
        pLItem->prv->nxt = pLItem->nxt;
        pLItem->nxt->prv = pLItem->prv;
        delete pLItem;
        count--;
    }
}

This method removes an item at a given index from the list. The index must be smaller than the count variable, and if no item is found at the given index the method caller is not informed about the fail of the removal process (The method doesn't crash either - It is just that I haven't found the time to implement that feature yet). The method works the way that at first the index is checked for being inside the range of the count - If the index is greater than the count the method execution is skipped. Afterwards the method goes through every item in the list whilst the counter i is smaller or equal than/to the index (At this point, the loop is skipped, the item's neighbors in the list are connected to each other and the item's memory space is freed, which is equal to the item's deletion).

ListItem AList<ListItem>::GetAt(int)

template <typename ListItem>
ListItem AList<ListItem>::GetAt(int index){
    PrivateListItem* pLItem = first;
    if (index <= count && index > -1){
        int i = 0;
        while(i < index){
            pLItem = pLItem->nxt;
            i++;
        }
    }
    
    return pLItem->crnt;
} 

This method returns an item at a given index in the list - The index must be smaller than the <code>count variable, and if no item are found at the given index (or the list is empty) the further progress is not defined - The program may crash or behave otherwise unexpected.

First of all, the method acquires the first ListItem in the list. If the index is a positive value and below or equal to the count variable of the AList<ListItem> the program continues to iterate though the list until the given index was found, and the returns the ListItem at this position.

An another approach was submitted by CodeProject member Meir Michanie, he changed this procedure to allow negative indexes in order to get items which are at the end of the list:

template <typename ListItem>
ListItem AList<ListItem>::GetAt(int index){
    PrivateListItem* pLItem = first;
    if (index < 0 ) index =count +1 + index;
    if (index <= count && index > -1){
        int i = 0;
        while(i < index){
            pLItem = pLItem->nxt;
            i++;
        }
    }
 
    return pLItem->crnt;
}

For instance, GetAt(-2) will return the item before the last.

ListItem AList<ListItem>::First()

AList<ListItem>::First() 
template <typename ListItem>
ListItem AList<ListItem>::First(){
    return first->crnt;
}

This method returns the first item (index = 0) in the list as a value of the type ListItem. Note: If there is only one item stored in the list this method returns the same value as AList<ListItem>::Last(). Don't call this method if the list is empty - It may lead to a system crash.

ListItem AList<ListItem>::Last()

template <typename ListItem>
ListItem AList<ListItem>::Last(){
    return last->crnt;
}

This method returns the last item in the list as a value of the type ListItem. Note: If there is only one item stored in the list this method returns the same value as AList<ListItem>::First(). Don't call this method if the list is empty - It may lead to a system crash.

int AList<ListItem>::Count()

template <typename ListItem>
int AList<ListItem>::Count(){
    return count;
}

This method returns the zero-based count of ListItems in the list, represented by the variable AList<ListItem>::count.

void AList<ListItem>::Clr()

template <typename ListItem>
void AList<ListItem>::Clr(){
    PrivateListItem* pLItem = first;
    while(count > -1){
        PrivateListItem* tbdListItem = pLItem;
        pLItem = pLItem->nxt;
        delete tbdListItem;
        count--;
    }
}

This method deletes all items stored in the list by iterating through them, starting at the list's index 0. Every PrivateListItem's memory space is freed, effectively deleting them (calling AList<ListItem>::RemoveAt(int) is not recommended since it would reconnect the list items after every deletion of a single list item, leading to a time impact of the operation's execution time).

Destructor

template <typename ListItem>
AList<ListItem>::~AList(){
    if (count > -1){
        Clr(); //Clear the List in order to free memory
    }
}

The AList class' destructor is important to avoid memory leakages since it calls AList<ListItem>::Clr() which frees the dynamically allocated memory space which would stay occupied by PrivateListItems other ways.