Click here to Skip to main content
15,868,141 members
Articles / Desktop Programming / MFC

Fast List Data Structure

Rate me:
Please Sign up or sign in to vote.
3.13/5 (10 votes)
4 Sep 2007CPOL3 min read 34.7K   439   17   3
A fast data structure based on a linked list and dynamic array. This list has O(1) add, delete, and access time.

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:

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

After that, you only need to call the functions:

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

Accessing array elements:

C++
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.

License

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


Written By
CEO Gravi Information Technologies and Consultancy Ltd
Turkey Turkey
Currently, also an MSc. student in Technical University of Munich, I develop practical application in computer vision for more than 5 years. I design real-time solutions to industrial and practical vision problems, both 3D and 2D. Very interested in developing algorithms in C relating math and vision.

Please visit Gravi's web page (http://www.gravi.com.tr) and my page (http://www.tbirdal.me) to learn more about what we develop.

I admire performance in algorithms.

"Great minds never die, they just tend to infinity..."

Comments and Discussions

 
GeneralMy vote of 2 Pin
Eddy the breaker25-Mar-11 5:38
Eddy the breaker25-Mar-11 5:38 
GeneralSome more explainations Pin
xryl6694-Sep-07 22:43
xryl6694-Sep-07 22:43 
GeneralRe: Some more explainations Pin
Tolga Birdal5-Sep-07 6:31
Tolga Birdal5-Sep-07 6:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.