Introduction
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
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
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 .
Dynamic Array Interface
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
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
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
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
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
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
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!