Data Structures

Most algorithms work on data. Naturally, the efficiency of the algorithm depends upon how we lay the data. If the structure of our data is not good, the algorithm could turn out to be a lot costlier. Hence, the structure of our data is an important component of functional design.

Each problem requires a unique structure of the data. But, often that is composed of some very common data structures. Let us have a look these common data structure elements. Once we understand them, we can build up a good data structure for the given problem

The 5 primary structures are:

  • Array
  • Linked List
  • Stack
  • Queue

An array is a continuous block of memory allocated for a series of variables of the same type. Since the memory block is continuous, accessing a given index requires very little processing. Hence it takes very little time. At the same time, it may be difficult to obtain a block of contiguous memory. That makes it very costly in memory usage. It leads to fragmentation very fast. Thus, if arrays are not used well, we end up spending a lot on the defragmentation.

Linked Lists, on the other hand are very efficient with memory management. But then, the performance is not so good. We have to go through the entire chain to locate any given element. We have variants like Circular Linked Lists and Doubly Linked Lists that may be useful in speeding up some specific kinds of iterations. If we are sure the traversal is limited to these constraints, then a linked list could be an ideal combination of memory as well as processing.

We also have a combination of arrays and linked lists - Array List. Here, we have a list of small arrays. That gives us a golden mean between the two. We have an intermediate memory and processing cost.

Arrays and Lists are meant for random access - when we want to directly access any given element. But there are times when we really do not need that. In some algorithms, we are sure we will need to access the elements in the LIFO (Last In First Out) order. In such a case, we can afford a little more. Such data structure is called a Stack.

Similarly, there are some algorithms that require elements in the FIFO (First In First Out) order. In such a case, we use a Queue.

Working with Data Structures

For us to meaningfully work with the data structures, we need one or more of these functions implemented for it.

  • Traversing - Sequentially accessing all the elements
  • Searching - Looking for an element with the given value or constraint.
  • Insertion - Adding a new element into the structure, at the given position.
  • Deletion - Removing a particular element from the data structure.
  • Sorting - Rearranging the elements in the data structure according to a given order.
  • Merging - Combining the elements of two different data sets.

There are several different ways of implementing each of these. Each implementation offers a trade off between the memory and processing cost.

Search and Sort are the most important. These are the fundamental operations that load any computational process. In any application of any complexity, the most computational resources are spent on the search and sort. Hence, optimizing the search and sort has a major impact on the overall performance of any software application.