Click here to Skip to main content
15,867,330 members
Articles / Internet of Things / Arduino

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

Rate me:
Please Sign up or sign in to vote.
4.80/5 (18 votes)
11 Dec 2016CPOL9 min read 108.5K   1.2K   47   32
A native C++ implementation of a very basic Doubly Linked List

Contents

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:

Image 1

Illustration of a Doubly Linked List (M. Bertschi, 15-OCT-2013)

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"):

C++
AList<int> myListOfIntegers;

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

C++
#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

C++
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

C++
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).

C++
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.

C++
 //! 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)

C++
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)

C++
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)

C++
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:

C++
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()

C++
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()

C++
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()

C++
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()

C++
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

C++
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Switzerland Switzerland
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
SuggestionRemoving "first" or "last" item Pin
Notario Means21-Apr-18 7:14
Notario Means21-Apr-18 7:14 
Questioncompiling error Pin
Song Changhun28-Sep-17 18:14
Song Changhun28-Sep-17 18:14 
AnswerRe: compiling error Pin
Marco Bertschi28-Sep-17 23:57
protectorMarco Bertschi28-Sep-17 23:57 
QuestionUndefined Symbols Pin
Member 1300794514-May-17 10:52
Member 1300794514-May-17 10:52 
AnswerRe: Undefined Symbols Pin
Marco Bertschi7-Aug-17 11:13
protectorMarco Bertschi7-Aug-17 11:13 
QuestionReview of method Add Pin
Alexander S. Yakovlev8-Dec-16 20:15
Alexander S. Yakovlev8-Dec-16 20:15 
AnswerRe: Review of method Add Pin
Marco Bertschi11-Dec-16 22:09
protectorMarco Bertschi11-Dec-16 22:09 
QuestionVery nice article about implementing a Doubly Linked List! Simple and clear! Pin
Volynsky Alex7-Jun-14 9:47
professionalVolynsky Alex7-Jun-14 9:47 
AnswerRe: Very nice article about implementing a Doubly Linked List! Simple and clear! Pin
Marco Bertschi7-Jun-14 23:18
protectorMarco Bertschi7-Jun-14 23:18 
QuestionRe: Very nice article about implementing a Doubly Linked List! Simple and clear! Pin
Volynsky Alex8-Jun-14 1:11
professionalVolynsky Alex8-Jun-14 1:11 
QuestionAllowing negative index. Pin
Meir Michanie27-May-14 0:39
Meir Michanie27-May-14 0:39 
AnswerRe: Allowing negative index. Pin
Marco Bertschi27-May-14 0:45
protectorMarco Bertschi27-May-14 0:45 
AnswerRe: Allowing negative index. Pin
Marco Bertschi6-Jun-14 23:27
protectorMarco Bertschi6-Jun-14 23:27 
QuestionSome tips for improvement... Pin
David Serrano Martínez26-Oct-13 9:52
David Serrano Martínez26-Oct-13 9:52 
AnswerRe: Some tips for improvement... Pin
Marco Bertschi26-Oct-13 10:33
protectorMarco Bertschi26-Oct-13 10:33 
GeneralRe: Some tips for improvement... Pin
Joren Heit10-Jun-14 3:26
Joren Heit10-Jun-14 3:26 
GeneralRe: Some tips for improvement... Pin
Marco Bertschi10-Jun-14 3:54
protectorMarco Bertschi10-Jun-14 3:54 
GeneralRe: Some tips for improvement... Pin
Joren Heit10-Jun-14 4:59
Joren Heit10-Jun-14 4:59 
GeneralRe: Some tips for improvement... Pin
CPallini23-Jul-15 7:03
mveCPallini23-Jul-15 7:03 
GeneralRe: Some tips for improvement... Pin
CDP180218-Jun-16 14:29
CDP180218-Jun-16 14:29 
QuestionNot ready for production use... Pin
Blake Miller25-Oct-13 5:23
Blake Miller25-Oct-13 5:23 
AnswerRe: Not ready for production use... Pin
David Serrano Martínez25-Oct-13 21:23
David Serrano Martínez25-Oct-13 21:23 
GeneralRe: Not ready for production use... Pin
Marco Bertschi26-Oct-13 9:32
protectorMarco Bertschi26-Oct-13 9:32 
AnswerRe: Not ready for production use... Pin
Marco Bertschi26-Oct-13 9:31
protectorMarco Bertschi26-Oct-13 9:31 
QuestionWhy "AList"? Pin
Qwertie22-Oct-13 6:45
Qwertie22-Oct-13 6:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.