Fast List Data Structure

• Download source code - 284 KB

Introduction

FastList is purely my implementation of combining data structures to have a more powerful (maybe not for all cases, but for some specific cases) one. It is a templated class which enables you to use the fast insertion and deletion properties of doubly linked lists and fast access operation of arrays. This way one can have O(1) deletion, O(1) insertion, and O(1) access time.

Background

In many applications, what we want is just add or delete some elements to a dynamic array and have operations on those values. Wouldn't it be nice to have a structure that is able to perform all of these operations in O(1) time?

I came across a problem where I needed fast insertion, deletion, and accessing operations when I was doing a connected component analysis on an image. Because I didn't need a sorting algorithm, I haven't implemented it, but you can try implementing a quick sort (my code has the basis for it, so I'll implement it soon). That would be fascinating.

Algorithm & Structure

The data structures used in this article is pretty simple. The doubly linked list holds the actual data. Every element of the array holds a pointer to a node in the linked list. When an item is deleted, it's deleted from the linked list. The only change in the fastlist is the value that specifies if a location is free or already deleted or still occupied. Because of this, the fastlist constantly grows even if you delete the elements, untill you deconstruct the fastlist. This is because I don't want to perform any reallocation, since it's a waste of time.

Using the Code

To properly use the code, the only requirement is to specify the maximum amount of data. If you don't know this amount, give it a huge value which is hard to get (or implement dynamic growing, which is obviously not my purpose). For example, in my image processing code, what I was doing was process a color image, and color images have dimensions like 640x480x3. And, the value of an array cannot go beyond this. (This is not even 1 MB, and your memory will always have enough space for such data.) Because as technology evolves, memory becomes a less serious problem for many applications.

Here is how you declare the templated object:

FastList<int>* ft = new FastList<int>(100);

After that, you only need to call the functions:

ft->AddItem(5);
ft->AddItem(3);
ft->RemoveItem(2);

Accessing array elements:

ft->GetItem(2);

Important!

Please be aware that when you delete an element, the size of the array doesn't get smaller. So, if you add an item and delete the previous one, don't bother with decrementing an index to get to your old value. Your old inserted value doesn't move anywhere. It remains where it was, no matter what and how you delete.

Points of Interest

The search I have implemented is O(n), which is a classical array search. I have put the code for quicksort, which was taken from Wikipedia.

History

• Version 1.0.
• Initial version.

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)