Original subtitles

1 1

(bright, uptempo music) 2

2

(whooshing) 3

3

(keyboard clacking) 4

4

(mouse clicking) 5

5

So, in this video, 6

6

we're going to look at arrays as a data structure. 7

7

So, the most important thing to understand 8

8

about arrays is how they're stored in memory. 9

9

And, essentially, they're stored 10

10

as one contiguous block in memory. 11

11

And what I mean by that is you don't have the items 12

12

or elements in an array scattered throughout memory. 13

13

All of the elements, items, whatever you want to call them, 14

14

in an array, they're all stored as one contiguous block. 15

15

So, let's say an array starts at memory address 100. 16

16

That's a bogus memory address. 17

17

You wouldn't have a memory address like that, 18

18

but to keep things simple, let's pretend 19

19

that we have an array that starts at memory address 100. 20

20

And let's say that array is 200 bytes long. 21

21

Well, then, what happens is, starting at memory address 100, 22

22

the following 200 bytes are the contents of the array. 23

23

So, the array is just one huge block 24

24

and that's why we have to specify 25

25

the length of the array when we create the array 26

26

because that tells the JVM how much memory 27

27

it has to allocate for that array. 28

28

And it's one reason why arrays can't be resized, 29

29

because, if they could be resized, 30

30

then there'd be no guarantee after that 31

31

that whatever, when we added extra space on, 32

32

that that extra space would be in 33

33

that same contiguous block of memory. 34

34

So, arrays have a static length 35

35

and when you create an array, 36

36

there's one huge block of memory allocated for that array. 37

37

So, the elements of an array are not 38

38

scattered all over the place in memory. 39

39

Now, the second important thing about arrays 40

40

is every element in the array occupies 41

41

the same amount of space in memory. 42

42

For example, when we created our int array, 43

43

every item that we put into that array will an integer, 44

44

and in Java, an integer is four bytes, 45

45

so every value in our int array 46

46

was occupying four bytes in memory. 47

47

You can't have an array element that occupies four bytes 48

48

and then the second array element occupies 12 bytes 49

49

and the third array element occupies 300 bytes. 50

50

That doesn't work. 51

51

Now, at this point, you might be thinking about objects 52

52

and thinking, well, wait a minute, 53

53

what if I create an array of strings? 54

54

I mean the strings in the array 55

55

could be of different lengths, so, you know, they're gonna 56

56

be taking up different amounts of memory. 57

57

What's important to understand when 58

58

you're working with objects, 59

59

not primitives like when you're working with ints, 60

60

but when you're working with objects, 61

61

what's stored in the variables is an object reference. 62

62

So, when you create an array of objects, 63

63

what's stored in the array elements 64

64

is a reference to those objects. 65

65

And object references are always the same size, 66

66

regardless of the type of object they're referring to. 67

67

So if you create an array of string 68

68

what you're actually storing in the array 69

69

is a bunch of object references to the string instances. 70

70

And those object references are all gonna be the same size. 71

71

And that's why you can have an object array 72

72

and store any type of object in there. 73

73

It's because the object references 74

74

to the different instances are always the same size. 75

75

So arrays occupy one contiguous block in memory 76

76

and every element in the array 77

77

occupies the same amount of space in memory. 78

78

So, because of that, we can easily calculate 79

79

the memory address of an array element based on its index. 80

80

So, if an array starts at memory address x 81

81

and the size of each element in the array is y, 82

82

then we can calculate the memory address of the ith element, 83

83

so array i, by using the following expression, 84

84

x plus i times y, and we're gonna look 85

85

at an example of this in couple of slides. 86

86

So you'll see an illustration of this. 87

87

So, basically, what that means is 88

88

if we know the index of an element in the array, 89

89

then the time or the number of steps 90

90

we have to do to retrieve the element will be the same, 91

91

no matter where it is in the array, 92

92

because all we have to do to get 93

93

the memory address of that element is x plus i times y, 94

94

and that works whether we want 95

95

the first element in the array 96

96

or the 5,000th element in the array 97

97

or the one millionth element in the array. 98

98

All we ever have to do to get really quickly to that element 99

99

is do that simple calculation to get the memory address. 100

100

And this is made possible because of the first two points, 101

101

because arrays are one large contiguous block in memory 102

102

and because every element in the array 103

103

occupies the same amount of space in memory. 104

104

So, let's have a look at this for the array we just created. 105

105

So, we created an array of length seven, 106

106

so the value indices are zero to six 107

107

and the values are 20, 35, minus 15, 108

108

seven, 55, one and minus 22. 109

109

Now, for this example, we're gonna pretend 110

110

the start address of the array is 12. 111

111

As I said, that's a bogus memory address. 112

112

You know, it doesn't matter what the number is. 113

113

And because these are integers, 114

114

the element size is four bytes. 115

115

So, if we wanted to get the element at array zero, 116

116

well that's equal to the start address of the array, right, 117

117

because the array starts here at 12 118

118

and so the first element of the array 119

119

is actually going to have the same address 120

120

as the beginning of the array. 121

121

So if we want the address of array zero, we get 12. 122

122

If we want the 35, we need to jump past the 20 123

123

and so, if we want array one, we're gonna start at 12 124

124

and then we're gonna add four bytes 125

125

because we know that the size 126

126

of each of these elements is four bytes, 127

127

and, so, if we want the second element in the array, 128

128

we start at the memory address, which is 12, 129

129

and we add four bytes, and now we're at 130

130

the start address for the 35. 131

131

So, that's 12 plus one times four equals 16 132

132

and if we go back to our calculation here, 133

133

that's the x plus i times y. 134

134

So, x is the 12, i is the index, 135

135

which in this case is one, 136

136

and y is the size of each element 137

137

in the array, which is four. 138

138

So that's how we're doing this calculation. 139

139

So, if we want minus 15, we've gotta jump over two elements, 140

140

so we're gonna start at 12 141

141

and this time we're gonna add 142

142

two times four to it to get 20. 143

143

So the 15 will start at 20. 144

144

If we want to get to the seven, 145

145

we've gotta jump over three elements to get to the seven, 146

146

so that's gonna be 12 plus three times four 147

147

and that'll give us 24 and so on. 148

148

And this is possible because the array 149

149

is one contiguous block in memory, 150

150

so all the elements are stored in one block in order 151

151

and also because every element 152

152

occupies the same space in memory. 153

153

If that wasn't true, if either of those two requirements 154

154

weren't true, we would not be able to use 155

155

this simple formula to quickly go 156

156

to an element in the array. 157

157

So, what this means is that, if we know 158

158

the index of an element in the array, 159

159

we can get to it really quickly, 160

160

and it doesn't matter where it is in the array. 161

161

I mean, if you look at array one versus array six, 162

162

we're doing the same calculation 163

163

and we're actually doing the calculation here as well. 164

164

I didn't show it, but this is actually 165

165

12 plus zero times four, 166

166

which is 12 plus zero, which is 12. 167

167

And now, maybe you can understand why 168

168

array indices are zero based, 169

169

because if they weren't zero based, 170

170

if they started at one, we'd have to subtract one here 171

171

because then we'd have 12 plus one times four, 172

172

that would be wrong 'cause then 173

173

we'd get 16 for the first one, 174

174

so we'd have to always subtract one 175

175

before we did the multiplication. 176

176

Starting the indices at zero means we don't have to do that. 177

177

So we can just substitute the array index in here. 178

178

'Cause, remember, this is zero times four. 179

179

I probably should have written that out, but I didn't. 180

180

So, one of the things that arrays are really good at doing 181

181

is retrieving elements if you know the index. 182

182

So, if we know the index of the element we want, 183

183

we can get to that element very quickly 184

184

regardless of where the element is in the array. 185

185

Okay, so and we understand how arrays 186

186

are stored under the covers 187

187

and we understand why, when we have an index of an array, 188

188

we can get to the element really, really quickly. 189

189

Doesn't matter where the element is in the array. 190

190

We do the same calculation. 191

191

So with that in mind, let's move on 192

192

and look the Big O values for array operations. 193

193

I'll see you in the next video.