Lesson video

Hello, my name is Mrs. Holborow, and welcome to Computing.

I'm so pleased you've decided to join me for the lesson today.

Today we are going to be looking at what an array data structure is and comparing data structures.

Welcome to today's lesson from the unit Algorithms. This lesson is called Data Structures, and by the end of today's lesson, you'll be able to describe and compare data structures.

Shall we make a start? We'll be exploring these key words throughout today's lesson, data structure, data structure, a way of organising and storing data in a computer, composite, composite, something made up of various parts or elements, dynamic data structure, dynamic data structure, a data structure where the size and memory allocation can change as the programme runs, static data structure, static data structure, a data structure with a fixed size and memory allocation that is set before the programme runs.

Look out for these keywords throughout today's lesson.

Today's lesson is split into two parts.

We'll start by describing array data structures and then we'll move on to compare data structures.

Let's make a start by describing array data structures.

There is a strong relationship between data structures and algorithms. When working with algorithms, data structures are needed to organise and manipulate data to solve problems efficiently.

A data structure is a collection of data that is organised to allow efficient processing and storage.

Many types of data structure are used in algorithms such as one dimensional arrays, two dimensional arrays, and lists.

Note that many other data structures are used in algorithms. A primitive data type is a basic building block for representing values and storing data.

Data structures can store a wide variety of primitive data types such as integers, floats, characters, and Boolean values.

A composite data type is made up of a combination of other data types.

Strings are a composite data type because they are made up of a number of primitive characters.

For example, the string "Hello" is composed of the characters, H-E-L-L and O.

Data structures can store a number of composite data types such as strings, lists and, arrays.

Note that data structures can store many other composite data types not shown above.

An array is a data structure that holds a number of data items or elements of the same data type.

A one dimensional array can be represented in a single row of values, as shown in the example below.

So we have index zero through to four, and in those positions we have me, do, it, her and him.

This example stores five words that are used in a child's spelling game.

In an array, the elements hold data values or variables.

In this example, the array elements hold the string values "Me," "Do," "It," "Her" and "Him." Array elements are numbered using an index system.

In most programming languages, the numbering of the indices starts from zero.

This is called zero based indexing.

So you can see "Me" is in position zero, not position one.

Indexing allows programmers easy access to any element in the array without having to search through the whole array.

In this example, index position zero holds the string value "Me." Index position three holds the string value "Her." Time to check your understanding.

Which value is stored in the index position one? Pause your video whilst you have a think.

That's correct, index position one holds the string value "Do." True or false, arrays must only contain data of the same type? Pause the video whilst you have a think.

Did you select true? Well done.

At which index position would you find the first element of an array in most programming languages? Is it A, zero, B, one, or C, there isn't a first element? Pause the video whilst you have a think.

That's right, in most programming languages, indexing starts at zero or zero based indexing, so the first item will be held in position zero.

Arrays can have more than one dimension.

A two dimensional array can be represented like a table with rows and columns.

Note that a two dimensional array has two indices.

If the previous spelling game had three levels, the five words at each level could be stored in a separate row of the table and the table could be visualised as follows.

So you can see we've now added two more rows to our table, and the words get more complicated as the levels go on.

In two dimensional or 2D arrays, each row of data can be accessed using a row index.

In this example, row index position one holds the string values "Put," "Ask," "Says," "Red" and "Any." Single elements of a 2D array can be accessed using the index positions of the relevant row and column.

For example, to access the fifth word in the third level, you would use the indices two and four.

This value would be class.

Okay, we've come to the first task of today's lesson and you are doing a fantastic job, so well done.

Aisha has used a table to represent an array of her favourite meals.

Sam would like to know how the elements of the array can be accessed.

Describe how Sam could access the string values "Pasta" and "Fajitas." Pause the video here whiles you have a go at the activity.

How did you get on? Did you manage to do an explanation? Great work.

Let's have a look at a sample answer from Aisha.

Elements in a 1D array can be accessed by their index position.

The string value "Pasta" can be accessed at index position two, and the string value "Fajitas" can be accessed at index position four.

Aisha's added a row to her table to represent a 2D array.

The new role holds the values of her favourite desserts.

So you can see the second row reads, "Ice cream, apple pie, custard, cake, and fruit salad." For part two, describe how Sam could access the string value "Ice cream." And then for part three, Sam would like to access the whole row of dessert data.

Describe how this could be done.

Pause the video whilst you complete the activities.

How did you get on? Let's have a look at another sample answer from Aisha.

For part two, Aisha says, "Elements in a 2D array can be accessed by the index position of the relevant row and then column.

The string value 'Ice cream' can be accessed at row index position one and the column index zero.

For part three, Aisha says, "It's easy to access the data of a whole row in 2D arrays.

To access a whole row of dessert data, just use the row index position one.

This holds the string values 'Ice cream,' 'Apple pie,' 'Custard,' 'Cake' and 'Fruit salad.

'" Well done, Aisha, there's some great responses there.

Okay, we are now moving on to the second part of today's lesson, and you've done a fantastic job so far, so well done.

We are now going to compare data structures.

There is no single best data structure that should be used for all situations.

Different types of data structures come with their own unique set of strengths and weaknesses.

Programmers must carefully select the most suitable data structure for each specific problem that they're aiming to solve.

The data structure a programmer selects will depend on a number of factors, such as the type of data that will be stored and used, how the data needs to be accessed, and what operations will need to be on the data.

One dimensional arrays have a number of advantages and disadvantages, as outlined below.

So the advantages of one dimensional arrays are that they're easy to understand and implement, you have direct access to any element using its index, and they can be used as a building block for more complex data structures.

Some disadvantages though are that they have a fixed size once they're declared, they can be inefficient to insert and delete elements, and they usually are limited to storing the same data type.

Two dimensional arrays share many of the same advantages and disadvantages as one dimensional arrays, but do have their specific characteristics as outlined in the table below.

Two dimensional arrays have the advantage that they're a useful way to store data that naturally fits into a grid-like structure.

They also allow data to be organised into two dimensions, making it easier to represent relationships.

Disadvantages of two dimensional arrays include they can consume significant memory, especially for large arrays potentially impacting performance.

They can also be more complex to work with than one dimensional arrays.

Another type of data structure commonly used is lists.

Lists are similar to arrays but have several key differences.

In a list, it's easy to add or remove elements dynamically.

A list can hold data of different types and memory allocation is more flexible and can be adjusted as a programme is executed.

Time to check your understanding.

A 2D array is A, able to store data of multiple types, B, a useful way to store data that naturally fits into a grid-like structure, or C, easy to extend and can be changed dynamically.

Pause the video whilst you have a think.

Did you select B? Great work.

A 2D array is a useful way to store data that naturally fits into a grid-like structure.

True or false, the size of an array is fixed when it is declared.

Pause the video whilst you have a think.

That's right, it's true.

A list is A, not extendable once declared, B, limited to storing data of one type or C, able to store data of different types? Pause the video whilst you think about the answer.

That's right, the correct answer is C.

A list is able to store data of different types.

There are many reasons to choose a list data structure.

One reason may be the flexibility they offer to be extended once implemented.

Real life examples may include a class list of names.

Somebody new may join the class, so we may need to add them to our list, a playlist of favourite songs, you might decide to add more songs to your playlist, or a collection of social media posts, the social media posts will get bigger over time.

There are many other suitable applications of lists.

Can you think of any? A 1D data structure may be chosen when only simple data of the same type needs to be stored and the number of data elements needed is known.

Some real life examples of this may be logging the maximum temperature for the days of the week, representing a series of scores for a test.

There are many other suitable applications of 1D arrays.

Again, can you think of any? A 2D data structure may be chosen when the data to be stored naturally suits the grid-like structure of a 2D array.

Some real life examples may include images where elements represent a pixel, maps where elements represent coordinates, or game boards where elements represent a square.

Again, there are many other suitable applications of 2D arrays, these are just some examples.

A static data structure has a fixed size and memory allocation that is set before the programme runs.

Both one dimensional and two dimensional arrays are static data structures because the size and memory allocation is set when they're declared.

A dynamic data structure is a data structure where the size and memory allocation can change as the programme runs.

The size and memory allocation of lists can change as the programme runs.

This makes them an example of a dynamic data structure.

True or false, arrays are dynamic data structures? Pause the video and have a think about your answer.

That's right, this is false.

Both one dimensional and two dimensional arrays are static data structures because the size and memory allocation is set when they're declared.

Okay, we are now moving on to the final set of tasks for today's lesson, and you've done a fantastic job so far, so well done.

Aisha is thinking about storing the names of web pages that have been visited from a web browser's history.

She's considering whether a 1D, 2D array or a list data structure would be the most suitable for storing the names of the web pages.

Explain which data structure you think would be the most suitable to solve the problem and justify your answer.

Pause the video whilst you complete the activity.

How did you get on? Great work.

Let's have a look at a sample answer together.

"I think the list data structure would be more suitable for storing the webpage names than either a 1D or 2D array.

Although it would be possible to store the names of webpages in an array, it would be hard to add extra elements because they are static data structures.

This means only a fixed number of webpage names could be stored in an array.

Also, if a large array was declared and the elements weren't used, it would be a waste of memory.

I think a list would be a great data structure to use because lists of dynamic data structures that can be easily extended as well as being indexed just like arrays.

This means that the names of the webpages can be easily added to the list as they are visited and the webpage names can be still accessed by their index." Remember, if you need to revisit your answer or add any more detail, you can pause the video now.

We've come to the end of today's lesson and you've done a great job, so well done.

Let's summarise what we have learned together.

Data structures are used to help store, organise and manipulate data to solve problems efficiently.

Arrays are static data structures that can store data of a single type in indexed elements.

Lists are dynamic data structures that can store data of different types in indexed elements.

The choice of data structure depends on the specific needs of the algorithm or problem.

I hope you've enjoyed today's lesson and I hope you'll join me again soon, bye.