The next node is bigger than the current one, Iterate through the list, start at the head This is a bubble sort, for details on how this works, check out Don't bother to sort a list smaller than 2 nodes big The actual sorting function now looks like this: void sortList(tList *list)
#ROBOTC WIKI UPDATE#
If the second node was the tail, update the tail pointer WriteDebugStreamLine("nodePtr->next = nodeA") WriteDebugStreamLine("nodePtr: %p (%d)", nodePtr, nodePtr->value) Start at the head and go through until we reach the end node, whose next pointer points to our We'll have to iterate through to find the The first node is a node somewhere in the list swap 'em and update the list's head pointer. If the list is less than two nodes big, there's not much point WriteDebugStreamLine("and %p (%d)", nodeB, nodeB->value) WriteDebugStream("swapping nodes %p (%d)", nodeA, nodeA->value) In code, it looks like this: void swapNodes(tList *list, tListNode *nodeA, tListNode *nodeB) Swapping two nodes with one of them being the head.Swapping two nodes, with one of them being the tail.Swapping two nodes in a list with just those two nodes.There are some special cases again, of course: If we wish to swap the nodes “99” and “37”, we’ll have to do some serious pointer swapping: To make it work, we’ll need a way to swap nodes. Details about how that works can be read in a previous tutorial. If you want to sort your list from small to large, you can easily do this with a bubble sort. Using pointer magic, you can have all sorts of fun with your list. The nodePtr's neighbour is the node we're looking for we need to start looking for the obsoleteNode's The node we want to delete is the head of the list When you translate that to code, it looks like this: void deleteNode(tList *list, tListNode *obsoleteNode) Just point the previous node’s next pointer to the next node of the one you wish to delete. if the node was the tail, update this pointer to the newNodeĭeleting a node is pretty simple operation. Insert the newNode into the list, after the node node = NULL, so put the newNode at the start Void insertNode(tList *list, tListNode *node, tListNode *newNode) Inserting a new node at the beginning of the list (and whether or not that’s the first one).
#ROBOTC WIKI CODE#
In code it’s a bit more complex, because we also need to deal with special cases, like: It’s not all that complicated, as you can see. 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. On the left you can see a node with a neighbour (node.next) and a new node. So how do you add a new node? Consider the drawing below: Inserting a new nodeĪ list is no good if you can’t add anything to it, this is called insertion. You’ll see how I use those in a little bit. An array of booleans is used to keep track of which ones are allocated. 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. 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. TListNode *tail // pointer to the node at the top of the list TListNode *head // pointer to the node at the head of the list You need something to keep track of all the node, so in order to do that, we create a List struct: struct tList In ROBOTC, you could represent such a list node with a struct like this: struct tListNode The last pointer in the list is nothing, or NULL. 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. What is a linked list, you say? Consider the image below.Įach 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 want to know more about stacks, you should check out part 2: You can read about pointers in this tutorial. I will also be covering things like queues, binary trees and other fun stuff. Please note that this is the second instalment of a multi-part tutorial on how you can use pointers in ROBOTC. Please note that some of the images are based on the ones found in the original WikiPedia article on linked lists. In any case, when ROBOTC implemented pointers, I started working on a little implementation of a linked list in ROBOTC. I don’t pretend to understand the math behind most of them. It was my favourite subject when studying computer science and I have a few good books on the subject. That sounded a lot less geeky in my head, but it’s true.
0 kommentar(er)
