Background Image

ADS 0x03: Dynamic Data Structures

Published November 25th, 2021

ADS Wallpaper

Introduction Get link to this section

Dynamic data structures are data structures that can grow and shrink as needed. The simplest example of a dynamic data structure is a dynamic array. Most other dynamic data structures are based on dynamic arrays. Dynamic arrays solve most of the problems of a normal array, and enables us to use almost all of the linked list operations in a more efficient way.

In this post, we will discuss the dynamic array and how it is used in other dynamic data structures. We will also implement a stack and queue using dynamic arrays.


Dynamic Array Get link to this section

When we allocate a normal array, we allocate a fixed amount of memory. If we have more elements than we can fit in the allocated memory, we cannot add any more elements to the array.

Dynamic arrays do support the behaviour of adding any number of elements to itself. A dynamic array allocates a fixed amount of memory in the background, but it will automatically grow and shrink the array as needed.

Growing and shrinking the array is done by reallocating the memory. This is done by creating a new array, copying the elements from the old array to the new array, and then deleting the old array.

It is trivial that it takes time to copy all the elements over, which is inefficient. A dynamic array solves this problem by reallocating a new array with double the capacity of the old array if we grow the array.


Dynamic Array Implementation Get link to this section

Let's consider a dynamic array implementation and analyse the time complexity of its methods to see that it is in fact more efficient.

 1
class DynamicArray<T>
 2
{
 3
	private T[] array;
 4
	private int size;
 5

 6
	public
 7
	DynamicArray(int capacity)
 8
	{
 9
		array = new T[capacity];
10
	}
11

12
	public int
13
	size()
14
	{
15
		return size;
16
	}
17

18
	public T
19
	get(int index)
20
	{
21
		if(index < 0 || index >= size)
22
		{
23
			throw new IndexOutOfBoundsException();
24
		}
25

26
		return array[index];
27
	}
28

29
	public void
30
	append(T element)
31
	{
32
		// Check if the array has space on it to append the element.
33

34
		if (size == array.length)
35
		{
36
			// Double the capacity of the array.
37

38
			reallocate(array.length * 2);
39
		}
40

41
		// Now we are sure the array has enough capacity.
42
		// Append the element to the array.
43

44
		array[size] = element;
45
		size++;
46
	}
47

48
	private void
49
	reallocate(int newCapacity)
50
	{
51
		// Create a new array of the requested new capacity.
52

53
		T[] newArray = new T[newCapacity];
54

55
		// Copy the elements over to the new array.
56

57
		for (int i = 0; i < size; i++)
58
		{
59
			newArray[i] = array[i];
60
		}
61

62
		// Delete the old array.
63

64
		array = newArray;
65
	}
66
}

This implementation of a dynamic array has two public methods that can be used to access and add elements: get and append.

get just returns the element at the given index or throws if the index is out of bounds. It takes time.

The append method appends an element to the end of the array. If the array has enough space, it will just append the element, which takes time:

If the array does not have enough space, it will double the capacity of the array, copy the elements over to the new array, delete the old array, and then append the element. This takes time:

What's interesting though, is that the average time complexity of the append method is actually .
This might seem counter-intuitive, but it is true. Consider the following scenario:

1
DynamicArray<int> array = new DynamicArray<int>(16);
2

3
for (int i = 0; i < 1073741824; i++)
4
{
5
	array.append(i);
6
}

Here, we create a dynamic array of initial capacity 16 and append 1073741824 () elements to it.

For the first 16 elements, the time complexity is of the append method is always , because the array has enough space to append the element.

We have to grow the array after it has reached 16 elements. The next time we have to grow the array is when the array has 32 elements on it. Then, when the array has 64 elements, and so on.
These are the powers of two, starting from 16. In these cases, we have to copy all elements on the array over to the new bigger array.
All other times, the array has enough space to append the element, so we can just put the element in the next free slot.

So, we're doing two operations: adding elements and and copying elements.

Let's compute the total number of individual operations that we have to perform to append all 1073741824 elements to the dynamic array.
It is trivial to see that we will have to perform add operations, since we certainly have to add all elements to the array.

But how many times will we have to copy elements over to the new array?
If the number of elements on the array is a power of two, the array is completely full and we have to grow it, which involves copying all currently stored elements over to a bigger chunk of memory.
Since there are 26 powers of two between (16) and (1073741824), we have to construct a new array 26 times.
The first time, we have to copy elements, the second time elements, ..., the last time elements.



It turns out we have to do approximately copy operations, which is the same number as the number of add operations.

So for each call to the append method, we have to perform two operations on average. Since this is a constant number and we can generalise this to any number of elements, we can conclude that the average time complexity of the append method is .

Appending an element to a dynamic array takes time on average.

Dynamic Array Interface Get link to this section

Many dynamic array implementations support the following operations: (Which the dynamic array implementation from the Java standard library ArrayList also does.)

Operation Time complexity
Accessing by index (get & set)
Appending an element to the end
Extracting an element from the end
Adding an element at a given index
(shifts the elements after the index to the right)
Removing an element at a given index
(shifts the elements after the index to the left)

We have already implemented the getting by index and appending an element operations. The implementations of the rest of the operations are left as an exercise for the reader.


Dynamic Array Vs. Linked List Get link to this section

In the previous post, we discussed that arrays are much faster than linked lists, but less flexible.

Dynamic arrays try to take the best of both worlds and are more flexible, while still storing its elements contiguously for maximum performance.

Dynamic arrays can do everything linked lists can do, but they are faster.
The one thing dynamic arrays are slower at is adding elements at arbitrary indices, provided that we have a reference to the element we want to add the item after.

A linked list really only makes sense if we have a very large number of elements and we keep a pointer to one or a couple of hotspot elements that we're currently processing.

A good example of a problem where using a linked list makes sense is the third problem of the TU Delft ADS Quadruple Quest . The input file can be found here .

Funny enough, an optimised implementation of a dynamic array still beats linked lists in this problem, because the input size (10000) is not extremely large.


Stack and Queue Implementation

Stacks and Queues are two very common dynamic linear data structures. We will discuss them both and how they can be efficiently implemented using dynamic arrays. Stacks and Queues can also be implemented using linked lists, but as you can see from the results of the benchmark I did, those implementations are much slower.


Stacks Get link to this section

A stack is a last-in-first-out data structure. We can push elements onto the stack, and pop elements off the stack. The last element that is pushed on the stack is the first element that is popped off the stack.

The stack in the picture above is represented horizontally, but it might be more intuitive to think of it as a vertical stack of elements.
Since it is hard to make a vertical image look good in a blog post, we will think of the stack as a horizontal array with a "bottom" on the left and a "top" on the right.

When we push an element onto the stack, we add it to the right of the stack:

When we pop an element off the stack, we remove the element from the right of the stack:

With the two main operations of a stack in mind, let's implement it using a dynamic array.


Stack Implementation Get link to this section

 1
class Stack<T>
 2
{
 3
	private T[] array;
 4
	private int size;
 5

 6
	public
 7
	Stack(int capacity)
 8
	{
 9
		array = new T[capacity];
10
		size = 0;
11
	}
12

13
	public int
14
	size()
15
	{
16
		return size;
17
	}
18

19
	public void
20
	push(T element)
21
	{
22
		// If the array is too small, grow it.
23

24
		if (size == array.length)
25
		{
26
			reallocate(array.length * 2);
27
		}
28

29
		// Add the element to the top of the stack.
30

31
		array[size] = element;
32
		size++;
33
	}
34

35
	public T
36
	pop()
37
	{
38
		if (size == 0)
39
		{
40
			throw new EmptyStackException();
41
		}
42

43
		// Remove the element at the top of the stack.
44

45
		size--;
46
		T element = array[size];
47

48
		// If the array is very big, shrink it to save memory.
49

50
		if (array.length > 16 && size == array.length / 2)
51
		{
52
			reallocate(array.length / 2);
53
		}
54

55
		return element;
56
	}
57

58
	private void
59
	reallocate(int newCapacity)
60
	{
61
		// Create a new array of the requested new capacity.
62

63
		T[] newArray = new T[newCapacity];
64

65
		// Copy the elements over to the new array.
66

67
		for (int i = 0; i < size; i++)
68
		{
69
			newArray[i] = array[i];
70
		}
71

72
		// Delete the old array.
73

74
		array = newArray;
75
	}
76
}

As you can see, the stack implementation looks very similar to the dynamic array we implemented earlier.
The push and reallocate methods are essentially the same as the append and reallocate methods from the dynamic array implementation, respectively.
We just added a method to pop an element off the stack.

Both the push and the pop methods are on average, because they double and cut in half the size of the array as needed.

The Java standard library has a stack implementation too.


Queues Get link to this section

A queue is a first-in-first-out data structure. The first element that is pushed onto a queue is the first element that is popped off.

Since the terms "bottom" and "top" don't really make sense in a queue, we'll use the terms "front" and "back" instead. The element at the front of the queue is the first element that was inserted and will be the first element that is removed.
In some implementations, the terms "push" and "pop" are called "enqueue" and "dequeue".

When we push an element onto the queue, we add it to the back of the queue:

When we pop an element off the queue, we remove the first element of the queue. Note that the indices of the array also change:


Queue Implementation Get link to this section

Implementing a queue using a dynamic array is slightly more tricky than the stack implementation.
The reason is that we need to be able to remove the first element of the queue, which means that we have to shift all the elements in the array to the left. This operation would be very expensive, because we have to move all elements one place to the left, which takes time.

However, we can also do something very clever and make the pop operation .
We do this by making the dynamic array circular. This means that we save the index of the actual first element (the front), and we can just increment the front whenever we pop an element off the queue. We will also keep track of the last element index (the back) to make our lives easier.
Elements that would be placed after the end of the array are circularly placed at the beginning of the array instead.

Let's bring it to life:

  1
class Queue<T>
  2
{
  3
	private T[] array;
  4
	private int front;
  5
	private int size;
  6

  7
	public
  8
	Queue(int capacity)
  9
	{
 10
		array = new T[capacity];
 11
		size = 0;
 12
		front = 0;
 13
	}
 14

 15
	public int
 16
	size()
 17
	{
 18
		return size;
 19
	}
 20

 21
	public void
 22
	push(T element)
 23
	{
 24
		// If the array is too small, grow it.
 25

 26
		if (size == array.length)
 27
		{
 28
			reallocate(array.length * 2);
 29
		}
 30

 31
		// Add the element to the back of the queue.
 32

 33
		array[back] = element;
 34
		size++;
 35

 36
		// If the back of the queue would exceed the array size,
 37
		// circularly place it at the front of the array.
 38

 39
		if (back == array.length - 1)
 40
		{
 41
			back = 0;
 42
		}
 43
		
 44
		// Else, we can safely increment the back.
 45

 46
		else
 47
		{
 48
			back++;
 49
		}
 50

 51
	}
 52

 53
	public T
 54
	pop()
 55
	{
 56
		if (size == 0)
 57
		{
 58
			throw new EmptyQueueException();
 59
		}
 60

 61
		// Remove the element at the front of the queue.
 62

 63
		T element = array[front];
 64
		size--;
 65

 66
		// If the front of the queue would exceed the array size,
 67
		// circularly place it at the front of the array.
 68

 69
		if (front == array.length - 1)
 70
		{
 71
			front = 0;
 72
		}
 73

 74
		// Else, we can safely increment the front.
 75

 76
		else
 77
		{
 78
			front++;
 79
		}
 80

 81
		// If the array is very big, shrink it to save memory.
 82

 83
		if (array.length > 16 && size == array.length / 2)
 84
		{
 85
			reallocate(array.length / 2);
 86
		}
 87

 88
		// Finally, return the element.
 89

 90
		return element;
 91
	}
 92

 93
	private void
 94
	reallocate(int newCapacity)
 95
	{
 96
		// Create a new array of the requested new capacity.
 97

 98
		T[] newArray = new T[newCapacity];
 99

100
		// Copy the elements over to the new array.
101
		// We start at the front and circularly copy all
102
		// elements until we reach the back.
103

104
		for (int i = 0; i < size; i++)
105
		{
106
			// Note the use of the modulo operator;
107
			// it ensures that we iterate over a circular range.
108

109
			newArray[i] = array[(front + i) % array.length];
110
		}
111

112
		// Delete the old array.
113

114
		array = newArray;
115

116
		// Reset the front and back.
117

118
		front = 0;
119
		back = size % array.length;
120
	}
121
}

I created an applet which can give you some more intuition about how the circular dynamic array we used in the queue implementation works.
Play around with it and push and pop some elements! See what happens when you push more elements than the array can hold.


Final Thoughts Get link to this section

I hope you enjoyed this post and acquired a greater understanding of dynamic data structures.
In the next post, we will discuss heaps and priority queues.

If you found this post helpful, feel free to share it! Any feedback is very welcome!