The idea behind an Associative Array Doubly Linked List (AADLList) starts with an associative array and adds a doubly linked list to it. In an associative array, you have a bunch of key/value pairs, where the value is accessed by its key (normal arrays can be viewed as an associative array where the keys are integers starting with 0). In a linked list, you have to define an object that has not only its data, but also a pointer to the next object in the list. A linked list will also have a pointer to the front of the list. A doubly linked list takes this a step further, by giving each object a pointer to the object before it AND after it, and the list must have pointers to the first and last items in the list.
I wanted to make this data structure independent of the application you're going to use it in, so instead of defining information fields in the objects as well as the pointers, the nodes in this list will have another variable inside that you can fill with whatever object you want.
First, we have to define the list objects, AADLListNode and AADLList:
Note that I omitted a trailing bracket at the end of the AADLList definition. That is because the rest of the code goes inside the AADLList class definition.
As you can see, the ListNode class has a node object and its two pointers. The List object has a list (which is an array) and its two pointers. At first, the first and last pointers are null, which means the array is empty.
The first thing we need to do is add nodes to the list. When we're adding the first item in the list, we have to take more things into consideration. When the first node is inserted, the list's first and last pointers have to change from null to the new first node. So we write our first function:
After our first node has been added, we can start adding more nodes. Since it's a doubly linked list, we have the desirable ability to add nodes to either the front or the back of the list. (Actually, we will be able to insert a node anywhere in the list.) So we write two functions, to add a node to the front or back of the list.
The code in these functions is pretty simple. We just need to set the prev or next pointers of the newly created node, and update the first or last pointers of the list. As you can see, these functions use the isEmpty() function to determine whether they should call addFirst() or not. We have to create isEmpty() for ourselves, like so:
I often don't care whether my nodes are inserted at the front or the back, so I threw a convenience function in:
Now we can add as many nodes as we want, either at the front or the back of the list. But how do we access the nodes once they're there? One way is to simply go through the object's members and use them, but this is generally not an awesome way to go (if you really wanted to do it, you'd have to do something like this: myList.list[myKey].node.myField ... etc. Clearly not what you want to be doing every time you want to retrieve something from the list). So we can write a function that will retrieve a given node for us based on its key.
But that isn't always what we want, because it will return an AADLListNode object, which you probably won't want to use in your application. So we write another, similar function, to just return the object inside the node (without the pointers).
Note that if we were simply doing a linked list (or even a doubly linked list), this operation would have an O(n) efficiency (worst case), because we would have to traverse the list and check each node to see if it was the one we're looking for. But since it's also an associative array, we can access it in O(1) time, greatly speeding up our data access. This is good.
I'm sure you've noticed that what this is missing is a way to remove a node from the list. So we're going to add that function now. We need to make sure we check that the node actually exists, then change the next object's prev pointer to point to the removed object's prev, and vice versa. (Don't know how to explain that very well, except to use the term "switcharoo," which I think should cover it pretty well.)
As you can see, this is by far the most complicated function in the class (and it's not even very complicated!).
And don't forget that trailing bracket!
Now we have a working AADLList, which gives us all the advantages of a doubly linked list and an associative array in one easy to use package. You have O(1) access to any node in the list, but you can also traverse from the back or the front and add nodes in whatever order you want (although that isn't implemented in this version).
So what would you want to add to the AADLList to make it a little better?
- How about an insert() function of some kind, so you can decide where in the list you want a node to be added?
- Build on your insert() function and make the AADLList a sorted list.
- Give it some queue-like or stack-like functionality, with push() and pop() operations. (Who wouldn't want the ultimate data structure?)
Feel free to use it, add to it, whatever. Let me know if you have any issues with it, or problems using it or implementing new features for it.