I really love data structures. That sounded a lot less geeky in my head, but it’s true. It was my favourite subject when studying computer science and I have a few good books on the subject. I don’t pretend to understand the math behind most of them. In any case, when ROBOTC implemented pointers, I started working on a little implementation of a linked list in ROBOTC. Please note that some of the images are based on the ones found in the original WikiPedia article on linked lists.

Please note that this is the second instalment of a multi-part tutorial on how you can use pointers in ROBOTC. I will also be covering things like queues, binary trees and other fun stuff. You can read about pointers in this tutorial: [LINK]. If you want to know more about stacks, you should check out part 2: [LINK]

#### What makes up a list

What is a linked list, you say? Consider the image below.

Each list element contains a number and a reference (or pointer) to the next node in the list, a bit like a chain of nodes. If you were looking at the node with “99” in it, and you wanted to know which one’s the next in line, you’d simply follow the pointer to the next node. The last pointer in the list is nothing, or NULL. This signifies the end. Of the list, of course, not the world.

In ROBOTC, you could represent such a list node with a struct like this:

struct tListNode { tListNode *next; // neighbouring node ubyte value; // value held by node } tListNode;

You need something to keep track of all the node, so in order to do that, we create a List struct:

struct tList { tListNode *head; // pointer to the node at the head of the list tListNode *tail; // pointer to the node at the top of the list int size; // current size of the list } tList;

So why the head and tail? That just makes things easier; it’s always nice to be able to quickly get to the first and last node of a list. The node array is necessary because we cannot allocate things dynamically, so we pre-allocate a fixed array of nodes and use them as a pool. An array of booleans is used to keep track of which ones are allocated. You’ll see how I use those in a little bit.

#### Inserting a new node

A list is no good if you can’t add anything to it, this is called insertion. So how do you add a new node? Consider the drawing below:

On the left you can see a node with a neighbour (node.next) and a new node. If we want to insert it between these two, we simply point the node’s “next” pointer to the new node and make the new node’s “next” pointer point to the node that was previously known as node.next. Now the list has a new node added to. It’s not all that complicated, as you can see. In code it’s a bit more complex, because we also need to deal with special cases, like:

- Inserting a new node at the beginning of the list (and whether or not that’s the first one)
- Adding a node at the end of the list

void insertNode(tList *list, tListNode *node, tListNode *newNode) { // Is the list empty? if (list->size == 0) { list->head = newNode; list->tail = newNode; list->size++; } // node == NULL, so put the newNode at the start // of the list else if (node == NULL) { newNode->next = list->head; list->head = newNode; list->size++; } // Insert the newNode into the list, after the node else { newNode->next = node->next; node->next = newNode; // if the node was the tail, update this pointer to the newNode if (list->tail == node) list->tail = newNode; list->size++; } }

#### Deleting a node

Deleting a node is pretty simple operation. Just point the previous node’s next pointer to the next node of the one you wish to delete.

We have a few special cases, though:

- Deleting the last node (the tail)
- Deleting the first node (the head)
- Deleting the last node

When you translate that to code, it looks like this:

void deleteNode(tList *list, tListNode *obsoleteNode) { tListNode *nodePtr; // We only have one node! if (list->size == 1) { list->head = NULL; list->tail = NULL; list->size--; FREE(obsoleteNode); } // The node we want to delete is the head of the list else if (list->head == obsoleteNode) { list->head = obsoleteNode->next; list->size--; FREE(obsoleteNode); } else { // we need to start looking for the obsoleteNode's // left neighbour nodePtr = list->head; while (nodePtr != NULL) { // The nodePtr's neighbour is the node we're looking for if (nodePtr->next == obsoleteNode) { // Check if it is also the tail if(obsoleteNode == list->tail) { list->tail = nodePtr; } // Update the node's left neighbour nodePtr->next = obsoleteNode->next; list->size--; FREE(obsoleteNode); return; } // advance to the next node nodePtr = nodePtr->next; } } }

#### Sorting the list

Using pointer magic, you can have all sorts of fun with your list. If you want to sort your list from small to large, you can easily do this with a bubble sort. Details about how that works can be read in a previous tutorial: [LINK]. To make it work, we’ll need a way to swap nodes. Consider the list below. If we wish to swap the nodes “99” and “37”, we’ll have to do some serious pointer swapping:

There are some special cases again, of course:

- Swapping two nodes in a list with just those two nodes
- Swapping two nodes, with one of them being the tail
- Swapping two nodes with one of them being the head

In code, it looks like this:

void swapNodes(tList *list, tListNode *nodeA, tListNode *nodeB) { writeDebugStream("swapping nodes %p (%d)", nodeA, nodeA->value); writeDebugStreamLine("and %p (%d)", nodeB, nodeB->value); tListNode *nodePtr; // If the list is less than two nodes big, there's not much point if (list->size < 2) return; // If the list if exactly two nodes big, just swap 'em around else if (list->size == 2) { nodeB->next = nodeA; nodeA->next = NULL; list->head = nodeB; list->tail = nodeA; return; } // If the first node is the list's head, // swap 'em and update the list's head pointer. if (list->head == nodeA) { writeDebugStreamLine("nodeA is head"); nodeA->next = nodeB->next; nodeB->next = nodeA; list->head = nodeB; return; } // The first node is a node somewhere in the list else { // We'll have to iterate through to find the // node, whose next pointer points to our // first node. // Start at the head and go through until we reach the end nodePtr = list->head; while(nodePtr != NULL) { writeDebugStreamLine("nodePtr: %p (%d)", nodePtr, nodePtr->value); // We've found the node, start swapping if (nodePtr->next == nodeA) { writeDebugStreamLine("nodePtr->next == nodeA"); nodePtr->next = nodeB; nodeA->next = nodeB->next; nodeB->next = nodeA; // If the second node was the tail, update the tail pointer if (list->tail == nodeB) { writeDebugStreamLine("nodeB is tail"); list->tail = nodeA; } return; } // go to the next node nodePtr = nodePtr->next; } } }

The actual sorting function now looks like this:

void sortList(tList *list) { writeDebugStreamLine("sortList"); tListNode *nodePtr; // Don't bother to sort a list smaller than 2 nodes big if (list->size == 1) { return; } // This is a bubble sort, for details on how this works, check out // http://botbench.com/blog/2012/07/21/tutorial-sorting-your-data/ for(int i = 0; i < list->size; i++) { // Iterate through the list, start at the head nodePtr = list->head; while(nodePtr != list->tail) { // The next node is bigger than the current one, // so swap them around if (nodePtr->value > nodePtr->next->value) { swapNodes(list, nodePtr, nodePtr->next); } // Update the nodePtr else if (nodePtr->next != NULL) { nodePtr = nodePtr->next; } } } }

#### Using a resource pool of nodes

As I mentioned earlier, ROBOTC does not have dynamically allocated memory, so no new() or free(). To simulate something like it, you can use an array of list nodes and keep track of their allocated status in another array of booleans.

tListNode _listNodePool[MAX_LIST_SIZE]; // array of nodes bool _allocStatus[MAX_LIST_SIZE]; // Array to keep track of allocation // status of nodes. // true == node is allocated

When a node becomes used, the status gets updated, when it becomes available again, the contents are cleared and the status is set to free.

tListNode * NEW() { for (int i = 0; i < MAX_LIST_SIZE; i++) { // Return the node if it is not already allocated if (!_allocStatus[i]) { writeDebugStreamLine("NEW: found node[%d]: %p", i, _listNodePool[i]); _allocStatus[i] = true; return _listNodePool[i]; } } // No free nodes available writeDebugStreamLine("NEW: no free nodes left"); return NULL; }

void FREE(tListNode *node) { for (int i = 0; i < MAX_LIST_SIZE; i++) { if (_allocStatus[i]) { if (node == _listNodePool[i]) { writeDebugStreamLine("FREE: deleting node[%d]: %p", i, _listNodePool[i]); _allocStatus[i] = false; memset(node, 0, sizeof(tListNode)); return; } } } writeDebugStreamLine("FREE: could not find node: %p", node); }

You can find the complete source code here: [LINK].

Excellent explanations and supplemental drawings. Now on to double linked lists

There’s a trick that you can use to delete nodes that handles all special cases:

https://gist.github.com/eric-wieser/e4f8b1edd10c256d87ef

Hi Eric,

It looks like ROBOTC does not like ** much. I’m afraid it won’t work that way.

I wasn’t aware of that (having never used RobotC). Does it produce a compiler error, or simply behave strangely?

Also, looks like you missed the implementation of swapNodes, instead providing deleteNode twice!

I contacted the devs and it seems that it’s just broken at the moment, but it is supported 🙂 The exact words were: “It’s supported. Apparently incorrectly.” Thanks for the heads up on the code SNAFU, I’ll fix it.