Doubly Linked List in C

Revisiting some of my old Arduino projects over the weekend, I remembered that C is not my strong point (that was almost a pun… close call). Rather than run away from the mountain of ampersands and hail of asterisks that ensued, I decided to improve on my Canon Rebel remote control project (loosely inspired by the awesome Camera Axe) by redoing the menu system for the Arduino-controlled LCD.

I will do the project write-up at another time as this post is largely aimed at higher-level language people like myself who struggle with pointers and memory addressing. But the good news is that there are a lot of tutorials and examples online for linked lists and various data structures in C.

First, let me lay out the requirements. This menu system must be:

  • Dynamic – I want to simply add one or two lines of code to add a new menu item or a sub menu item and not rewrite the entire flow.
  • Able to support an infinite amount of sub-menus, and must have a way to come back to the parent menu.
  • Able to be operated using only 3 buttons. (less hardware, less cost!)
  • Circular – the menu should “wrap around”, so if I used an array with 0-n elements, if I reached 0 and pushed “left”, it would take me to the nth element.

Some of these may be obvious to embedded systems veterans; nonetheless, I don’t work with hardware or mechanical systems, so the requirements and constraints can be vastly different from almost any modern computer (even smartphones).

So the data structure I will use is a Doubly-Linked List (DLL). The choice should be obvious: we can go forwards and backwards in our menu, just as in a DLL. There is a beginning to each menu (the head) and and end to it (the tail), but if we set tail.next to be head, and head.prev = tail, then we have a clean, neat way to express the requirements above.

Additionally, I will use three buttons “Left”, “Right”, and “Enter”. The suspiciously missing button is the “Back” button that would enable us to go back to the parent menu. To solve that problem, we will add a “Back” menu item to each sub-menu – pressing enter on the “Back” item would take us to the previous menu. Pressing “Enter” on an item without a sub-menu enters the “Edit” mode and allows us to modify a variable (for example, shutter speed) with the left and right arrows. Pressing “Enter” again allows us to exit the “Edit” mode.

Here is an example of what the menu should look like.

  • Menu 1
  • -subitem 1
  • -subitem 2
  • -back (goes back to and displays “Menu 1”)
  • Menu 2
  • -subitem 3
  • -subitem 4
  • -back (goes back to and displays “Menu 2”)

A doubly-linked list in C can be expressed with structs. I used one struct to store the head and the tail of a Linked List, and another to store a Linked List node:


typedef struct node NODE;

typedef struct LinkedList {
  NODE *head;
  NODE *tail;
} LINKEDLIST;

struct node {
  char c[17]; //16 characters max on an LCD screen, plus the venerable \0
  int value;
  NODE *prev;
  NODE *next;
  NODE *submenu;
};

Each level menu will be represented by a struct LinkedList, and each node could then have a pointer to another menu underneath (the struct node *submenu).

So when we start the program, we need to keep a pointer only to the first node in the top-level menu. As we advance through the menu and go into submenus, we obviously need a way to get back. We can set the NODE *submenu to be the pointer to the top level menu which then becomes a clean and convenient way of getting back without having to deal with remembering how many menu levels deep we are.

To add a node:


void add(LINKEDLIST *ll, const char *c, int value, NODE *s) {
  NODE *node = (NODE *)malloc(sizeof(NODE));
  if (ll->tail == NULL || ll->head == NULL) {
    ll->tail = node;
    ll->head = node;
  }
  ll->tail->next = node;
  ll->head->prev = node;
  
  node->prev = ll->tail;
  node->next = ll->head;
  node->value = value;
  strcpy(node->c, c);
  node->submenu = s;
  ll->tail = node;
}

One slightly annoying aspect of Linked Lists is that as the elements are added, they are added in reverse order. If you have 3 items (1, 2, 3), the fourth element would be added to the front (i.e. 4, 1, 2, 3). This is because when the new item is created, its “next” pointer is pointed to “head”, and then the new pointer becomes the “head”. This is done because it is in O(1) time — if we wanted to add to the end of the list (and we didn’t keep a “tail” pointer), we would have to traverse the list, making insert an O(n) operation. Seemingly it’s not a big deal in the scope of this application, but I want to preserve every little CPU cycle that I reasonably can on the Arduino (that said, there are probably many, many wasteful things I am doing with this code that shouldn’t be done in a C/embedded environment, so feel free to point them out!). Anyway, to get around inserting at the front, we also keep a tail and just add the new nodes to the tail, as above.

For completeness sake, here is the code along with an example.

Leave a Reply