I want to use a linked list arrays a factor

What's the point of reading this and so I was sort of thinking about is that well actually "Are arrays

faster than the linked list or are the linked lists faster than an array, how do we go about finding out?"

Which one's faster, so let's have a shoot out arrays versus linked list

First question to start is

I should just remind ourselves what the difference is between a linked list and

An array so let's start with the array so probably the simplest

To understand so an array is just a way of storing

several

values

in memory so we start off with the first value and

for the purposes of this demonstration, I'm going to use a

Structure containing multiple values. We did talk about objects a while ago structures are what you had before

We saw this object which is a collection of values in memories and store to integer values

So this is array element zero and it's got two numbers. We then got array element one

And it's got two numbers

Looks like I'm playing break out got a great element

To and it's got two numbers and so we can refer to any of these

by

reference to the Index starts at 0 3 4 5 6

7 10 so you can have an array of any size we have to know how big it is if you wanted to be when

You create so you allocate the memory for all the things and then?

You can store some values so we can write 42 in this one. We can put 21 in here

I'm going to put 3 in that one and we can store them or we can put different values in here as

Well as we need them so that's how an array works. Which is one big block of memory each thing stored one after the other

linked list works slightly different we start off at the beginning of

the linked list and it points at nothing but then as we add things to the list we

Allocate the memory for it. We're going to store two things so the first thing we'll label these things inside it p

And Q so it's a lot p here

And we've got q but we also have an extra thing that tells us where the next they will be and that's empty, too

So it's all put 42 and 16 so we just allocate space for that one

Structure that one thing that we're going to store and we connect it up

So we point this at the first thing so we often call this something like first

And we see Alex videos to see how that have done

So when we want to store the next thing we allocate explai for another one

And we can store the value, so we've still got 8

21 in it now the difference between this could be anywhere else in memory, and we connect to the next pointer

to point in

To the next thing so we have some known starting point

which points to the first thing and the first thing 22 the second thing and the second thing would point to the third thing and

So on and that would point down and these could be all over

anywhere

In the computer's memory and then at the end you normally point it at some known value

Which is often referred to as null and is often the number zero?

So you can then walk through your list

And when you find at the next point of zero or null you know you've come to the end of it

There are two different ways of storing data the best or the same amount of data now

He's got some differences this one as I says it's fixed inside, and you create it you can store

How many things you know I've actually filled in but as soon as you get more than eleven since final top array?

You can't go past eleven if you can see yeah the numbers all go to

11 on this however if we wanted to put something else thing we can just get rid of this thing

And update this to point

To a new thing so we can make this grow

Quite easily, and we can also be really clever

We can add things in the middle and the beginning very very simply, but we're going to go into that today

So creating them. We're probably only going to do once but which one is actually faster

Well, let's think about what actually to do. Let's define a very very simple problem

We've created the structure here, and it's got two things in it

It's got an integer called p and an integer called Q so saving the linked list and in

The array let's consider an operation where we're just going to go through all the elements in our array

Or all the elements in our linked list and sum the value of p are going to add up all the value

So we're going to add up. What's in array

Element Zeroes P in array of them at once P and so on so we're going to effectively do

Something's going to add them all up. We'll do the same with the linked list as well

So we're going to set what the first thing is to point to p

Now that one. No. There's no time out of its value of p the next one and so on and we'll add them all up

Why are we using missiles they want to the unique thing about this is

That it's going to visit every single element in either the array or every single element in the linked list

so we're going to visit every single element if you only have to visit one element then the very nature of

Random access into array means as we fast

There's no way you can make any difference unless it's the first element if you only one to ever access the first element

Then look at the same speed we fuel directly to random element

Then the array or win hands down you can just think about how it works that will be the case. We're going to consider

We want to access every single element and do something to it and in this case

You're just going to sum up the values, but it could be if things were representing say windows on the screen

We want to move them around we want to redraw them

Whatever it is will then do something to every single wall so we sort of set out the problem?

I'm going to go over an array of values and a linked list of values

I'm going to in sum in the visits all and we do actually add up all the numbers

Stored in the element P. Which is part of the structure so what I've done is I've written

To see poems which are more or less identical

I'm going to create

125,000 elements in my array

or mailing list and in the linked list I've got a structure which contains an integer p and an integer Q and

in the array version

I've got a structure which contains an integer p and interested Q in the array item

The only difference is that the linked list has one extra item which is the next pointer to the next thing?

So very listen see so hopefully we'll go as fast as we possibly can most of the rest of the program

is

identical

so I have my main Routine here which creates a

List or an array of random number generator?

125,000 random numbers which is a slowest part of the program you'll see and then store them

So allocate memory for each element in the linked list and then we set the value

Everything else will just leave with 0 and we do the same with the array just as we did on the paper

We then run the program

100 times and all going to here is time

How long it takes to run a function which adds afforda numbers either in the list or in the array?

I will do that 100 times

And then we can work out the average time it takes to calculate one and we'll print out the values as we go

So we're just using the built-in clock function in C. Which should be accurate accurate enough for what we want to do

so the real meat the body of the program is this function here some list or

Some array

Let's start with the array one because possibly the simplest we said a variable to be zero that's going to be asked some

You have another variable

I which is going to be our index through the array and we go from I equals zero

I first element until we get to the end the number of elements in there

and we just say this sum equals the value that was already in sum plus the value in the ice element in the array a

P element

Remember we said the array had a p and a Q in it we want the value stored in the p space within the structure

in our array, so I'm just going to add get them together the list version very very similar we set the someone to be 0

We say while p does not equal null

So why we haven't reached the end of the list and we set p initially to be the first thing in the linked list?

So pointing out that first thing sum equals sum plus

P inside p. We using P inside p

Confusing variable names, but then I'm asleep programmer, and then we set p ir pointer to point to the next thing

So we follow the link to the next thing in the linked list and we keep doing that until we come to the end

There are two programs as simple as you get in terms of implementing a linked list or on array

so we're going to do is run them and

We should get some values output

But we're not going to run them on the I max we're not going to run them on the raspberry Pi

we're actually going to run them on the atari behind me which means I need a very high Peak high-tech piece of

Equipment, so I need a floppy disk to transfer other programs from the iMac

Go topping them off the iMac, and then we can run them on the AtAri

so go over to the Atari and

Assurance that it's cameras and spot. We can see it. So what I'm gonna do at first is they got to run

the list first also going to generate

125,000

linked list values to let it Run

Right while it loads off the floppy disk

that's what it used to be like back in the 80s and 90s you had to wait one you crave them ran a

While a

long While

And this is just a simple program

So there is good

So it's not

Initializing the link list it's allocating all the memory for the different elements and then putting a random number

In the P value of each one, so we'll let that run

In the words of the old Hobbit computer game time passes or in the words of every apple of this

secret short

How long does this take?

A while lots of oil, I don't know another time this bit

125,000 times however long it takes to allocate a random number and allocate some memory

On the clock speed of what this is actually an 8 MegAhertz cPU

So it's a takes a while the computer loaded off all the code for the program and off the floppy disk into memory

And it's now running it to generate the data set that we need then Gonna sum all the values

So everything is happening now will happen off memory

It's just taking a while to process it

But we are recording it in 4k which is a slight overkill. I hope you're getting into that

extra bit

So the programs going through now and we'll let it run 400 times

We'll get an average, but actually looking at the values of the coming up

I think we can safely assume that the average is going to end up being

166 clock ticks now when I say qwop takes each of the machines. We're going to look at are going to have

Different clocks perms that they use the time things so we can't compare the values directly what we could come read with the seconds

But we can certainly see the relative patterns between it will call that

166 clock ticks over to run the linked list version of the program it takes

166 clock ticks

So let's now run the array version of the program

So now we're going to do exactly the same thing

we're going to allocate an array every time tWenty-five thousand elements and

populate them with random values because of the way

I've written the program

It will actually be the same pSeudo random number sequence that the sum should be the same and then we're going to fill

each of them up and time how long that takes and we'll they'll see whether an array actually is faster than the linked list or

Whether a linked list will be b. Array

So that to me looks like that little spinny thing is going faster

Yeah, well so and I haven't just upgraded the processor while they're off camera

What's actually happening is?

When we allocate the space for the linked list we have to allocate space for each element and then for the gym there

We allocate space for the next element. We could do that in a different way and speed things up, but we did it

That's the classic way with the array. We allocate the whole lot in one go, so we all take one

Huge block of memory under 25,000 times eight is about one meg's worth of memory

So allocate all that in one go, and then we're just going through it filling in all the values setting all the values

So that should be quicker

and it seems and spinning wheel is going slightly faster what why would that Spin wheel very fast can you just learn how that

You can read it if you've heard this thing you it yeah?

So to give some nice sort of visual Feedback while this is running

Well, I'm just a plain white screen what I'm doing is I'm printing every hundred element ideals