All language subtitles for 3. Array Lists

(upbeat music)
2

If you've been working with Java
3

for any length of time, you'll be familiar with array list.
4

It's pretty much the go to class
5

when it comes to storing a collection of objects
6

that you'll want to iterate over sequentially.
7

So let's take a closer look at them
8

by going over to the Java doc.
9

If we scroll down and we read the documentation
10

written by the developers of this class,
11

we'll notice that it says this is
12

a resizable array implementation of the list interface.
13

Meaning that the data in the list
14

is being stored in an array.
15

And this array is called the backing array.
16

Now this tells us a few things based
17

on what we learned about arrays.
18

If we know the position of an item in the list,
19

accessing will be efficient.
20

In fact, it'll be all of one or constant time
21

because we know that if we have the index
22

of the item that we want,
23

then accessing the array element is all of one.
24

So array lists are great if all you're going to do
25

is iterate over them.
26

Because in that case you're always going from
27

index zero to the end of the list.
28

So you know the indices of
29

the items that you want to retrieve.
30

But if you want to add a lot of items to an existing list,
31

this will be slow if the size of the list
32

isn't large enough to accommodate the new items.
33

In other words, if the backing array is already full
34

and you wanna add more items to the list,
35

then you're going to have to resize that backing array.
36

Well, you won't but the implementation
37

of the array list class will.
38

And also, removing items will be slow
39

because we're gonna have to shift the remaining items
40

to remove any empty space.
41

So if you're going to be adding
42

a lot of items into an array list,
43

you want to have some idea of how many items
44

are ultimately going to be on the list
45

so you can create an array list instance with
46

a capacity that will accommodate all the items.
47

Otherwise, the array that's backing the list,
48

that's actually storing the items,
49

will have to be resized when it gets full
50

and you wanna add more items to the list.
51

Now as I said, you can ensure that the array
52

will be large enough by specifying the capacity.
53

And if we go down to the constructors,
54

you'll see there's one that lets you
55

specify the initial capacity.
56

And it says it constructs an empty list
57

with the specified capacity.
58

What it's actually doing is
59

the backing array that it creates
60

will be of length initial capacity.
61

Now when it comes to array lists,
62

it's important to understand the difference
63

between size and capacity.
64

Capacity is the maximum number of items
65

that the list can hold before it's gonna have to be resized,
66

the backing array.
67

The size is the number of items
68

that are actually in the list.
69

So if you create an array list
70

with the capacity of 20 and you add three items to it,
71

then the capacity is 20 and the size is three.
72

And you'll notice up here, if you don't pass a capacity,
73

you're gonna get an initial capacity of 10,
74

which isn't a whole lot.
75

So if you're gonna have more that 10 items on the list,
76

you're better off specifying the capacity.
77

Okay, so let's go over to the IDE
78

and play around with array lists.
79

So I've created a project
80

and I'm putting, or I've put the code into
81

academy.programming.arraylists.
82

And I'm going to create an employee class,
83

employee, so that we have something interesting to add to
84

our lists that isn't just integers.
85

So under the same package, I'll create a new java class
86

and I'll call it employee.
87

And we'll add a
88

first name field,
89

a last name field and we'll throw in an ID field as well.
90

And now we can get the IDE to help us generate
91

all the boiler plate code.
92

So if I right click anywhere
93

or where I want the code to go
94

and I click generate,
95

you'll see there's lot of choices here.
96

So first of all, add a constructor.
97

And I want all three fields to be handled by the constructor
98

so I'll select them and click OK.
99

And now we have our standard constructor
100

that just takes the parameters it's passed
101

and assigns them into the number fields.
102

And of course we want sets and gets for these
103

'cause they're private.
104

So once again, we'll right click,
105

we'll say generate and we want getter and setter.
106

And once again, I want getters and setters
107

generated for all the fields.
108

So I'll select all of them and click OK.
109

And now we have the standard sets and gets.
110

And finally,
111

I'd like a two string method generated.
112

I wanna override the default because when we print
113

an employee instance, I'd like to see
114

first name, last name, and ID.
115

I don't just wanna see the object reference.
116

So I'll right click,
117

go to generate, and I wanna a two string method.
118

I want all the fields and here we go.
119

We have a nice two string method.
120

And so the IDE gave us quite a bit of help there.
121

Just by right clicking and go to generate
122

we can get all the boiler plate code that we need.
123

So now that we have this class,
124

let's go back to our main method.
125

So we want a list so I'm gonna say list employee.
126

Now the reason I'm saying list rather than array list
127

is by using list, if I decide later
128

that I want to use a different type of list,
129

it's easy to change the specific implementation
130

of list that I'm using.
131

So I'm gonna call this employee list
132

and I'm going to create a new array list.
133

And I'm not going to specify capacity
134

because I'm only gonna add four employees
135

and as we saw, the default capacity is 10.
136

So I'm not gonna worry about the array having to be resized.
137

So I got a couple of errors here.
138

First of all, there are multiple possibilities for list
139

because there's more than one list class.
140

So IntelliJ wants me to tell it which one I want
141

and I want java.util.
142

And here it's telling me that diamond types aren't supported
143

at language level 1.6.
144

And if you get something like that,
145

it means that right now for some reason,
146

I'm not sure why it does this because I've specified
147

the JVK is Java nine,
148

it thinks I'm using Java 1.6.
149

So to get rid of that,
150

click here and say set my language level to seven,
151

'cause that supports the diamond.
152

And so now all the errors are gone.
153

So if you get something like that,
154

just wait for the light bulb to come up
155

and then have it set the language level
156

to a higher language level.
157

Okay, so getting back to why I use list here,
158

if I decided I wanted to use a different type of list,
159

I could just replace the specific class
160

that I'm using when I create the instance
161

and this will still work.
162

Because as long as the class that I'm using
163

implements the list interface, the compilers happy.
164

Okay, so now that we have our list,
165

let's add a few employees.
166

So I'll say employee.add, this is how we add
167

an item into our list.
168

And I'll say new employee.
169

Our first employee will be Jane Jones.
170

And she'll have an ID of 123.
171

Let's add another one.
172

And we'll say John Doe.
173

And his ID is 4567.
174

We'll add
175

Mary Smith.
176

And her ID will be 22.
177

And finally we'll add
178

Mike Wilson.
179

And he'll have an ID of 3245.
180

And I think I'm missing a parenthesis here
181

so I'll just add that.
182

So as I said, what's happening under the covers
183

when we call the array list constructor
184

is creating a backing array of 10.
185

'Cause we saw that the default capacity,
186

if we don't specify one, is 10.
187

So we only have four employees so that's okay.
188

It means that when we added our employees,
189

the backing array didn't have to be resized.
190

And let's go look at the add methods.
191

I'm gonna select it, right click
192

and say go to the declaration.
193

And this is actually on the interface.
194

I want to go to the implementation
195

so I'm going to come here and click on the I
196

and I'm going to select the arraylist.add implementation,
197

because that's what we're using.
198

And so here we are in the actual code.
199

And now let's go to that implementation.
200

And so this is where the work's actually done
201

and we'll see that the first thing it does
202

is checks to see whether the backing array is full.
203

And so it checks to see whether the number of items, S,
204

that's in the array are equal to the array's lengths.
205

Because if that's true then the array is full
206

and so it needs to grow the array, it has to resize it.
207

And then after it's done that,
208

it'll assign the item
209

and then of course, it gonna increase the size
210

because as I discussed earlier,
211

the capacity is the maximum number of items
212

that can be stored in the array,
213

basically the array's length,
214

and the size is the actual number
215

of items we've added to it.
216

Okay, so an array list is backed by an array.
217

So why don't we just use an array?
218

Why are we using array list?
219

Well, because array list has a bunch of methods
220

that let you work with the list items.
221

And so the code to do this has been written for you.
222

You don't have to directly work on the array.
223

Also, array list implements the list interface
224

and so as I mentioned earlier,
225

you can swap to another type of list
226

that uses the list interface
227

without too much disruption of the existing code.
228

So let's go back to our main method
229

and look at some of the methods that array list offers.
230

We've seen how we can add items,
231

let's print the items on the list.
232

So we can say employeelist.foreach
233

and then we'll say employee
234

system.out.printlineemployee.
235

And now it wants, I have to move up
236

to language level eight because it wants lambdas.
237

We need Java eight for lambdas.
238

So this is a lambda expression
239

and for each employee in the list,
240

we're going to print that employee out.
241

Now I could've just used a loop
242

and loop through the list
243

but this is more concise.
244

So if we run now.
245

Here are employees
246

and we're getting the nice print out
247

because remember we used the IDE to override the two string.
248

So here are our employees
249

and it was easy for us to just go ahead,
250

call one method and iterate through the list.
251

So let's now get the second employee in the list.
252

And so just like with arrays,
253

the index is zero based when we're working with array lists.
254

And that's surprising because we now know array list
255

is backed by array.
256

So if we want to print out the second employee,
257

we just say employeelist.get1
258

because the second employee will be at index one.
259

So we'll run and we should see John Doe come up
260

and John Doe does.
261

These four are from the four each col
262

and then we have John Doe being printed out from here.
263

And as we know, because an array is backing the array list,
264

this get col, when we actually access the employee,
265

is done in constant time.
266

Because an array is backing the list,
267

random access like this, where we just provide an index,
268

is done in constant time.
269

The time complexity doesn't depend on the size of the list.
270

So array lists are great when you want to load
271

a bunch of data and then access it like this.
272

Now we also can check to see if a list is empty.
273

So we can say
274

system.out.printline
275

employeelist.isempty.
276

Now we expect false because the list isn't empty
277

so let's run,
278

and sure enough, we get false.
279

Okay now another thing we can do
280

is we can replace the employee at a specific position
281

with another employee.
282

So lets replace John Doe with John Adams.
283

So to do that we just have to say employeelist.set,
284

so we're not gonna use add here.
285

And the first parameter is the index
286

of the employee that we want to replace
287

and we're gonna replace John Doe with a new employee John
288

Adams.
289

And John Adams has an ID of 4568.
290

And now if I comment out,
291

I'm gonna comment out all of the prints we've done so far.
292

And I'm going to copy the print that prints the entire list.
293

And let's run.
294

And we'll see for the second employee is now John Adams,
295

it's no long John Doe.
296

So if you wanna add an employee to the list
297

or add an item to the list
298

and it's always added to the end of the list,
299

you use the add method.
300

If you want to replace an item in the list,
301

you use the set method.
302

Now because random access is all of one setting,
303

an employee will happen in constant time.
304

As long as you're providing the index,
305

whatever operation you're performing will perform
306

with a time complexity of constant time over the one.
307

Now if you want to get the number of items in the list,
308

that would be the size, we can do that.
309

So we'll just say employeelist.size.
310

And remember, this won't give us the capacity,
311

the capacity is the total number of items this list
312

can currently hold.
313

That's the length of the backing array.
314

This will tell us how many employees
315

we've actually added to the list.
316

So let's run.
317

And we'll see four, which is what we expect.
318

'Cause we have four employees on the list.
319

Now as I just said, the add method
320

adds items to the end of the list.
321

What if you don't want that?
322

What if you want to add an employee at a specific position?
323

Well, if you wanna do that you can also use the add method
324

but you have provide more parameters.
325

So if we wanted to add John Doe back in
326

but we wanted to add him at index three,
327

so we wanted him to be the fourth employee,
328

we'll say employeelist.add
329

and this time we need to provide an index
330

as well as the instance we want to add.
331

So we'll say John
332

Doe and 4567.
333

And if we now print our list again,
334

so I'll grab this.
335

And copy it here, let's run.
336

And we'll see that John Doe has been added at index three.
337

Now you've provided an index
338

but because in this case you're sticking him
339

in the middle of values,
340

some values are gonna have to be shifted up.
341

So the worst case for this would actually be o of n
342

because the worst case would be
343

you'd want to put him right at the beginning of the array
344

and then all the other elements have to be shifted.
345

And let's go to the source code to look at that.
346

So we'll saw go to
347

the declaration and I want the implementation
348

for array list.
349

And you'll see here, this is the array copy,
350

this is the shifting.
351

So depending on where you want to put him,
352

elements are gonna have to be shifted in the array.
353

And that's what causes this particular operation to be
354

a linear time operation.
355

Alright, back in our code,
356

if we want the array, let's say we have a list
357

and we're saying okay, well give us that backing array.
358

Give us the array that's holding the employees,
359

we can get that by calling the to array method.
360

But we're not going to get an employee array.
361

We'll get an object array.
362

So we'll say object
363

employee array equals employeelist.toarray.
364

Now if we want an employee array,
365

we can get it but then we have to tell
366

the compiler that that's what we want.
367

And to do that, we pass an array of the type we want.
368

So instead of just calling the to array method
369

and not passing anything, we would change this call
370

to say new employee and the length that we want
371

is employeelist.size because the size method
372

will return how many employees we actually added.
373

And so we just needed an array of that length.
374

And then when we get that array back,
375

let's print out
376

the element.
377

So we'll say for employee,
378

employee in the employee's array,
379

or employee array, rather.
380

And I'll change this to employee now
381

'cause we can do that.
382

We'll just print the employee.
383

So let me comment out the other print
384

so we don't get confused with what we're looking at.
385

And let's run this.
386

And I think there must be one more print,
387

yep, here it is.
388

Let me comment that out, run again.
389

And now here's the print coming from the employee array.
390

And so we get the five employees that we had in the list
391

but we now have them in an employee array instead.
392

Now if you want to know if the list contains an instance,
393

you can call the contains method
394

to check whether the list contains an employee.
395

So let's go ahead and do that.
396

So that's system.out.printline
397

and we wanna check employeelist.contains
398

and we have to pass
399

the object we're looking for.
400

Now we don't have that instance because
401

we didn't save Mary anywhere
402

so we'll have to ask for Mary again.
403

And her ID was 22.
404

And let's run.
405

And you'll see that we get false.
406

Now maybe we're expecting true, maybe you weren't.
407

And the reason you get false is because
408

we haven't implemented the equals method
409

in the employee class.
410

So because there's no equals method,
411

what this method is doing is actually checking
412

to see if they're the exact same instance
413

because that's what the default equals method does.
414

The one that's all the way back in object.
415

And they're not the exact same instance.
416

We created an instance here
417

and we created an instance here.
418

So there are two distinct instances.
419

Now they're structurally the same,
420

meaning that all their fields contain the same values
421

and so we think they should be equal.
422

That if we're looking for an employee
423

with the first name Mary, the last name Smith
424

and the ID 22, we know we have an employee like that
425

in the list but we have to implement the equals method
426

in the employees class so that it's going to compare
427

the individual fields against each other.
428

So let's go to our employee class
429

and I'll just put the code here.
430

And once again, we can get the IDE to do this for us.
431

So I'll say generate.
432

Now it's going to create the hash code method for us too
433

because whenever you override the equals method,
434

you should really be overriding hash code as well.
435

So that's fine.
436

We can just accept all the defaults here.
437

I'm gonna select these two
438

and say first name and last name should never be null.
439

And now we have an equals method.
440

So if we go back to our main method and run again,
441

we should see true.
442

And we do.
443

Because now the equals method in the employee class
444

is actually looking at the values in the fields.
445

Now that we have the equals method,
446

we can make use of the index of method.
447

And this will look up an employee in the list
448

and tell us what index that employee is occupying.
449

So let's look at for John Doe.
450

So let's say system.out.printline
451

employeelist.indexof and once again,
452

because we didn't save a reference to John Doe,
453

we'll just create an instance with the values
454

and his ID is 4567.
455

And because we implemented the equals method,
456

this should find John Doe.
457

It'll find the employee that has
458

the same values in the fields.
459

And it does.
460

It says he's at index three and we know that's true
461

because we specifically added him at index three.
462

Now the contains and index of methods
463

are only as good as the search algorithm
464

being used to search the array.
465

In other words, when we're looking something up in the list,
466

the method that we're using has to search the list.
467

And the way it's searching the list
468

will determine whether the index of
469

and contains method are fast or slow.
470

And we'll be looking at search algorithms
471

later in the course.
472

Alright, so the last thing I want to show you
473

is how to remove items from the list.
474

Let's remove the third employee,
475

that's gonna be Mary.
476

So we'll say employeelist.remove
477

and we're gonna pass two
478

because we wanna remove the third employee.
479

We could also pass an instance of her if we wanted to
480

but this is actually faster
481

because we're providing the index.
482

And once we've done that, let's print out the list.
483

I'll comment this out so we're not printing out
484

a bunch of stuff from the array.
485

And I'm gonna copy this line,
486

that prints out our list.
487

And let's run.
488

And we'll see that Mary is no longer in our list.
489

We just have four employees now.
490

Now because we're dealing with an array in the background,
491

remove can be expensive because elements
492

after the one we removed have
493

to be shifted down one position.
494

So if we take a look at that,
495

if we go to the source code
496

and I want the source code for array list,
497

we'll see here that this is an array copy
498

and that's what's doing the shifting.
499

If it has shift elements down to occupy
500

the empty space left by the one that we removed.
501

Okay, so there are a few more methods
502

in the array list class
503

but I'm going to leave you to explore them on your own.
504

For a lot of you, this may have been a review
505

but I just wanted to show some of you the methods
506

and operations you can do on array lists.
507

So array list is good for random access
508

if you have the index
509

and it's good for iterating over the items in the list
510

but it's not so good for inserting items into
511

the list in any position other than the end.
512

It's not so good for deletions, removals.
513

And it's not so good for accessing an item in the list
514

when you don't have it's index.
515

So remember, it's backed by an array
516

and so if you have the index,
517

the operation will be able to be performed in constant time
518

but if you don't have the index
519

or if you're inserting or removing elements
520

from somewhere in the middle of the array
521

or at the beginning of the array,
522

elements are gonna have to be shifted around.
523

And so because an array list is backed by an array,
524

it has the same problems and advantages that arrays have.
525

Okay, that's it for array lists and in the next video
526

we're gonna take a quick look at vector, the vector class.
527

I'll see you there.