This week we will be looking at some basic data structures, the array, the linked list and the stack, and looking at their relevance.

The importance of data structures

We will start with a look at data structures. First of all, what is a data structure and why is it important? When it comes to programming, we frequently need to deal with collections of data, rather than a single item of data. For example, we might write a program to manage student records. This program would need to deal with not just one student, but many students. Similarly, you might want to write a program for a live music venue, to allow the venue to store concerts and allow users to book tickets. Again, such a program would have to deal with many concerts and many users.

To store multiple items in a computer program, we need to choose an appropriate data structure. A data structure is a programming construct which allows us to store multiple items. When dealing with data structures, an important thing to consider is which is the most appropriate data structure for the problem we are trying to solve? Certain data structures are more suited to specific types of problem, and we will be looking at this through the module.

A basic data structure - the array

Let's start with the most basic data structure of all, the array. An array is a data structure which can hold more than one item of data, and can be thought of as a series of "boxes" which can hold data. With an array, the key thing is that each box is adjacent to its neighbours in memory which has some consequences in terms of efficiency which we will consider as we go on

The diagram below shows an example of an array which holds the names of five items of fruit.

The things to note here are:

• Arrays have indices. An index is a number which represents the position of an item in an array. In most programming languages, including Python, indices begin with zero. So the first item in the array has the index zero.
• The items in an array are stored continuously in the computer's memory and each item in the array uses the same amount of memory. Here we assume that each item uses 64 bytes, so that the first item is stored at memory address 512, the second at memory address 576 and so on. This has some important consequences for performance of arrays versus other data structures, to be considered later.

Arrays do have some disadvantages. Their simplicity makes them easy to work with but this simplicity can lead to limitations.

Answer to exercise 1

• Kate Stevenson is the fourth member of the array, so would have index 3 (because indices start from zero). Mike Watson is the eighth member, so by the same logic, would have index 7.
• The memory address of the start of the array is 1600, and each item uses up 80 bytes. There are three members before Kate Stevenson, so these three members would use up 80*3 = 240 bytes. Therefore, Kate Stevenson will be 240 bytes on from the start of the array, i.e. at memory address 1600+240 = 1840.
• Likewise, there are seven members before Mike Watson, so these seven members would use up 80*7 = 560 bytes. Therefore, Mike Watson will be 560 bytes on from the start of the array at memory address 1600, i.e. 1600+560 = 2160.

Advantages and disadvantages of arrays

Advantage: Fast lookup

As we saw above, the advantage of using an array is that it is very fast to index an array. This is because arrays are always sequentially stored in memory, so that in the example above, "apple", "orange", "pear", "grape" and "cherry" will be stored adjacent to each other in memory.

When indexing an array, the computer is able to work out where in memory the data is stored, because each member of an array uses up the same number of bytes. THe address is simply:

So imagine, for example, that each member of an array uses up 32 bytes, and the start of the array is at memory location 24576.

It's an easy calculation to work out where the member with the index of 3 is located. If we substitute the values into the equation we get:

which is 24576 + 96, which is 24672.

We ourselves do not need to do this calculation. The computer does it, when it encounters an array index. The CPU needs to work out where the data at that index is stored, so it uses the start address of the array, the size of one member, and the index, to work it out. This is just simple arithmetic. Therefore, arrays are optimised for fast look-up of data using a numerical index.

Creating a simple program making use of an array

Here is a program which makes use of an array. We are creating an array called fruits to hold the names of types of fruit.

Note a couple of things:

-To use an array we use the NumPy library, which provides a range of features for scientific computing. However our use of NumPy here will simply be to create an array.

• We define the array using the statement:

  
  

  Note the square brackets surrounding the list of items to go in the array.

• Note the code to print the members of the array:

  This code shows the use an array index to access each member of the array. The index is the number within the square brackets: 0 for the first member, 1 for the second and 2 for the third. Remember we discussed array indices above.

Coding exercise 1.1

You will need to install numpy first. From the PyCharm console, enter pip install numpy.

Write a program which creates an array with the 10 employees mentioned in Exercise 1, i.e:

Display "Jane Smith" and "Mike Watson" by indexing the array appropriately.

Disadvantage: not flexible, an array cannot be resized

Now, imagine you want to add two more entries to the array:

Now run it. Do you get the result that you expected? See how this illustrates an issue with arrays: they have fixed size. If an array is initialised with a certain number of elements, you cannot add additional elements later and the only valid indices are those indices within the capacity of the array. Here, the array was initialised with 10 elements so only indices 0-9 are valid. Furthermore attempting to append to the end of the array via an append operation would not work either:

Not enough space, or too much space!

We can visualise our array of 10 employees below. (Just the initials of the employees are shown).

Let's say, though, the company takes on an 11th employee, Kevin Kennedy (KK), as discussed above. Do we have space in the array to fit this 11th employee? No, we don't, because an array has fixed size!

Answer to exercise 2

We could make the array significantly larger so that if the company expands, there will be enough space to hold new employees.

Answer to exercise 3

If we made our array significantly larger, the storage could be inefficient as the array may have many more spaces than we are likely to need and therefore it is wasteful of memory. This is shown below.

On the other hand, if we only make the array a little bit larger (e.g. 15 spaces), we are likely to run into the same problem of running out of space in the near future.

Using a List

One solution is to use a more complex data structure, which can be extended with new data. In fact Python uses one such data structure, the list. A list is essentially a wrapper round an underlying array. With the list you can add new items of data to the end of the list using the append operation, and keep doing so until the computer runs out of memory.

Other languages have similar "extensible array" data structures, for instance C++ has the vector and Java has the ArrayList.

Creating a simple program making use of a list

Here is a program which makes use of a list. We are creating a list called people to hold the names of members of a team. The list initially has space for three members, however we can later append to it, to expand the list.

Note a couple of things:

• We define the list using the statement:

* is the multiplication symbol in most programming languages. This will create a list with three blank members (i.e. None times 3; None basically means "nothing here yet").

• Note the code: people[0]. This is using an index - remember we discussed indices above. Specifically this code is retrieving the member of the list with index zero.
• Note also how we can append to the list: unlike an array, we can extend it after we created it so we are not restricted to the original size.

Coding Exercise 1.2

Rewrite your exercise 1.1 code to use a list rather than an array. Try appending to it using append(). Does it work?

Answer to exercise 4

Lists contain an internal array. So what happens when we need to extend a list? We create a new array with more space when the old one runs out of space. We need to:

• Create an array of the new, larger, size (large enough to hold all the new members we're trying to add);
• Copy all the existing members into the new array;
• Add the new members onto the end of the array.

This is shown below. This diagram shows a simplified version of what happens when you append to a list. It is a repeat of the diagram showing array resizing, but also shows the list (in green) as a wrapper round the array. It shows how the internal array has to be recreated and the old data copied across when you append to a list.

This however is inefficient because a new internal array is created with additional space to hold the new elements, and then the old data is copied across from the old array to the new array. We have to loop through each element in the old array and copy it across to the new array, which is slow.

The Python list does however include some optimisations to improve the efficiency of append and insertion operations by reducing the frequency this has to be done. For instance, more memory is allocated for the internal array than is needed to hold the new items, reducing the frequency that we have to recreate the array. See here for details.

The stack

A stack data structure involves adding items from bottom to top, rather like a stack of plates. When we remove items from the stack, we remove from the top, again just like a stack of plates. The stack is known as a "last in first out" or "LIFO" data structure. It is called this, because the last things we add to the stack, are the first things we remove. Here is an example of a simple stack of numbers.

The two key operations of a stack, adding and removing items, have special terms.

• Push. To push an item onto a stack means to add it to the top. It is possible the stack may only have a certain capacity, i.e. it can only hold a certain number of items (perhaps due to memory constraints) in which case an error occurs if the stack is full.
• Pop. To pop an item off the stack means to remove it from the top. The item is removed, and we also obtain it as a result of the pop operation. If the stack is empty, an error is generated.

An additional operation is:

• Peek, To peek a stack is to obtain the value of the top-most item of the stack without removing it.

Answer to exercise 5

A stack can be used for any operation in which we need to navigate back to a previous state. Examples could include:

• Browser navigation. When we visit a website, we often need to navigate back to a previous site. When we click the 'Back' button, we want to return to the site immediately preceding the one we are currently viewing. So when you click 'Back', the current site might be removed from the stack so that you return to the previous site.
• Directory/folder structure. When navigating the folder system of your computer, you typically start at a 'root' folder (for example C:\ on Windows, or your home directory on Linux) and then navigate to subfolders, for example C:\Pictures. You then might navigate to a sub-sub-folder, such as C:\Pictures\Holiday and then C:\Pictures\Holiday\2018 and so on. In a subfolder you can navigate upwards to the previous folder, so that if you are in C:\Pictures\Holiday and you navigate upwards, you arrive at C:\Pictures and then C:\ if you navigate upwards once more. So the process of navigating upwards removes the current folder from the stack and returns to the previous folder.
• "Undo" commands in desktop applications. Each action you take in a desktop application might be stored on a stack, so that if you select "Undo", the topmost operation would be reversed, and then removed from the stack.

(In actual fact, each of these is now implemented in a slightly more complex way, in the sense that you can, in modern browsers, move both back and forwards along your history, but we are assuming a more simplified implementation in which you can only move back for the purposes of illustrating a stack).

Another use of stacks, which you will appreciate more when you have done more programming, is:

• Storing function calls in a program.

Paper Exercise 1.3 : Stacks

We are now going to perform a paper-based exercise with stacks, to help you understand them and their operations.

Imagine you have an empty stack. Draw the stack after each operation below, and explain what, if anything is returned from each operation and any errors that might occur.

push (a), push (b), pop (), push (c), peek (), pop (), pop (), pop (), push (d), push (e), push (f), pop (), push (g), push (h), peek (), push (i), pop (), pop (), pop (), peek ().