[Programming] #6: Double pointer trick with Linked Lists.

If you are using C/C++, there is this really cool trick you can use when dealing with linked lists thanks to the existence of pointers. It saves you a bit of memory, computation power and also coding annoying special cases, so why not use it!

Honestly though, this isn't much of a 'trick'. It's more of understanding pointers themselves. Once you understand them, implementing this 'trick' becomes really trivial.

Say we have a simple linked list like so:

struct Node {
  Node(int tData) : data(tData), nextNode(NULL) {}
  int data; // some kind of data your node holds; I will just use integer in this case
  Node * nextNode; // pointer to the next node
};

// ... somewhere in your program... 
Node * linkedListHead = new Node(0);
Node * iterator = linkedListHead;
for ( int i = 1; i < 5; ++i ) {
  iterator->nextNode = new Node(i);
  iterator = iterator->nextNode;
}

This simply creates 5 nodes in a linked list that looks like this (I'm using its data to represent itself):

0 -> 1 -> 2 -> 3 -> 4 -> NULL

Simple enough.

So let's say we want to perform a really standard list operation: Removing an items from the list...say, the node containing 3. Usually there are 2 kinds of functions you can implement for removal: Removal by comparing data, and removal by the node itself. I will just use the former as an example and skim on the latter later.

So let's go: Removal by comparing data. The brute force algorithm is simple:
1) Find node 3
2) Get node 2
3) link node 2 to node 4 via node 3
4) delete node containing 3

However implementation is not so easy. Here's how it can get really messed up:
1) Find 3; Okay that's easy, loop until I get the node containing 3!
2) Find 2; Oh that's easy too I will again until I find 2...wait...

So that's the first alarm that sounded in your head. Why on earth should a search and destroy algorithm take O(N^2)? No, that shouldn't be the case BUT we can remedy this cleanly like so:
1) For every node, check next node.
2) If next node contains 3, link current node to node 3's next node (which is node containing 4).
3) Delete node containing 3.

That looks much better...except that it's not going to work if we are trying to remove the 1st node in the linked list. All of a sudden, we have an special case to code for. There are several ways to do this; one is to just code a special case, the other is to introduce a 'dummy' node at the start of the linked list and iterate from there (that might introduce special cases for other functions)...or we do the 'trick'!

OKAY, now we finally get to the 'trick'. The trick is to have your iterator be double pointers instead of single pointer. This means that we are iterating Node* instead of Node. Here's a snippet of the double pointer in action:

Node ** iterator = &linkedListHead;
while ( (*iterator) != NULL ) {
  if ( (*iterator)->data == 3 ) {
   Node * nodeAfter = (*iterator)->nextNode;
   delete (*iterator);
   (*iterator) = nodeAfter;
   break;  
  }
  iterator = &iterator->nextNode;
}

With this, you can see that there is no need for any special cases and also why the hell STD list's remove function takes in a wonky item called 'iterator' (which essentially holds a double pointer for just this reason!). It's so clean and elegant that it gives me chills ^_^

Well explaining this is going to delve into a crazy rabbit hole about pointers and stuff, so I'm just going to do what teachers do and say 'work it out on paper!'. This is actually good practice to strengthen your understanding of pointers. My advice is to draw every component in detail while you are figuring this out.

And if next time someone asks you what double pointers are for other than creating double array, this is a really solid and practical example to give.