Features, applications and implications of data structures

Stack

A stack is a LIFO data structure (Last In First Out). It understands two operations:

• PUSH – pushes a new value onto the stack
• POP – removes the topmost value from the stack

Stacks are used in many applications – a common one is in an “Undo” feature – each operation made is pushed onto a stack, and when the user asks to undo their actions, the changes made are popped off the stack and reversed in their document.

For example, given an empty stack, if the values 3, 5 and 7 are pushed onto the stack in that order, the value 3 will be at the bottom, and the value 7 at the top. Assuming there are no other changes, popping three values from the stack will result in 7, 5 and 3, in that order.

Queue

A queue is a FIFO data structure (First In First Out). Items added to a queue are added to the end of it. When an item is removed from the queue, it is always the items from the front of the queue that are removed.

In contrast to the stack, if the values 3, 5 and 7 are added to the queue in that order, the first three values to be removed from the queue will be 3, 5 and 7, again in that order.

Task lists use queues.

Array

An array is a data structure that allows multiple values of the same data type to be stored using a single variable. Individual values (elements) are accessed through the use of an index.

Arrays are static data structures. This means that all of the memory required for the array is allocated when the array is created, and it is allocated as a single block.

Once an array is created, updating values and retrieving them is fast. However, an array’s size can not be altered. If a larger array is required, it is necessary to create a new, larger array, and copy the existing array into the new one. Read more here.

Inserting and deleting elements from an array is considered to be a slow process: say you have an array containing 10,000 elements, and want to insert a new item at position 5. You must first move every existing item from item 5 onwards into the next element (i.e. 5->6, 6->7 and so on), before the new value can be inserted. Similarly, for deletion, once a value is no longer required, all subsequent values must be moved back one element in the array to avoid an empty space.

List

In contrast to an array, a list is a dynamic data structure. This means that memory is allocated at run-time on an as-needed basis. A list does not have a fixed size.

Lists are more accurately referred to as linked lists. In most respects, a list can be used in code in much the same way as an array. However, the internal working is different.

A list variable contains two pieces of information: the piece of data, and the memory location where the next piece of information can be found. If there is no more data, this memory location is null.

What this means is that whenever a new item is added, the memory for that item is reserved, and the last item in the list has its ‘next item’ pointer updated to point to the new item.

Whilst this means there is no limit to the list’s length, it makes retrieving information slower. If you have a list of 10,000 items and want to use the value of the 6457th item, you must start at the first item, and from it, find the location of the second item. This item will then tell you the location of the third item, which points you to the fourth item and so on. This will continue until the desired element is located.

On the other hand, deleting and inserting items is quick, because all that needs to the changed are the pointers around the inserted or deleted item.