Doubly Linked Lists and Dual Pointer Searches

Back at it again with the data structures! This week I’ll be writing about a topic I just learned about, namely double linked lists and an algorithmic technique known as two pointer list iteration.

Two weeks ago I discussed what is known as a singly linked list, a string of nodes that each possess data and a pointer that connects them to a string of data points. What makes these “singly linked lists”, is the fact that the list goes in only one direction. Each node has a next attribute, but no previous attribute. This means that, when iterating through the linked list, you can only go in one direction, from the head to the tail. Doubly linked lists can be searched through from either end, starting at the head or the tail. Doubly linked lists are a slightly more realistic version of a list of things, be it subway stops or street names, and are therefore a better representation of real life concepts.

In order to create a doubly linked list, nodes need to be instantiated with a pointer or a next, leading to the next node, and a previous, leading to the previous one. Having both a next and a previous attribute as part of a node, complicates certain things. When removing a node from the middle of the list, both the previous node and the upcoming one need to be adjusted so that their respective next and previous attributes reflect the changed status.

Now that we’ve gotten that squared away, let’s talk about something a little more interesting.

Using two pointers to iterate over a linked list. Why would anyone do this you might ask? For a number of reasons. One is that you can use two pointers, moving at different speeds to find the middle element of a linked list. Having one pointer iterating at a rate of two increments, and the other at one, will results in the slower pointer being as close to the center of the linked list as possible when the faster pointer reaches the end of the list. A useful attribute about this technique is it obviates the need to create a replicative array. Arrays have indexes which makes it very easy to find things in sequence or in a certain part of the array, simply by referencing this index. The problem with this rather brute force method though, is the fact that it creates two instances of the data you are working with. One as an array and one as a linked list. Given that mastery over data structures and algorithms is all about efficiency of time and space, using a two pointer method is the far superior option.

This is one of the first actual actionable algorithms I’ve learned that can be applied to data structures that I’m familiar with. Very exciting stuff. Apparently using more than one pointer in a linked list can have myriad uses when it comes to sussing data out of a linked list. You can use two pointers to find a node that is a given amount of nodes behind the final node by setting a count to zero, setting the first pointer off running, incrementing the count and node once each go around, and then setting off the second pointer once the count has reached however many spaces back from the end of the list you want to be. Once the first pointer has reached the end of the list, the second pointer will be directly where you need it to be to find the node in question.

I’m looking forward to using the two pointer method to solve any number of algorithmic problems should they arise.