Original subtitles

1 1

(upbeat music) 2

2

If you've been working with Java 3

3

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

4

It's pretty much the go to class 5

5

when it comes to storing a collection of objects 6

6

that you'll want to iterate over sequentially. 7

7

So let's take a closer look at them 8

8

by going over to the Java doc. 9

9

If we scroll down and we read the documentation 10

10

written by the developers of this class, 11

11

we'll notice that it says this is 12

12

a resizable array implementation of the list interface. 13

13

Meaning that the data in the list 14

14

is being stored in an array. 15

15

And this array is called the backing array. 16

16

Now this tells us a few things based 17

17

on what we learned about arrays. 18

18

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

19

accessing will be efficient. 20

20

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

21

because we know that if we have the index 22

22

of the item that we want, 23

23

then accessing the array element is all of one. 24

24

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

25

is iterate over them. 26

26

Because in that case you're always going from 27

27

index zero to the end of the list. 28

28

So you know the indices of 29

29

the items that you want to retrieve. 30

30

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

31

this will be slow if the size of the list 32

32

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

33

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

34

and you wanna add more items to the list, 35

35

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

36

Well, you won't but the implementation 37

37

of the array list class will. 38

38

And also, removing items will be slow 39

39

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

40

to remove any empty space. 41

41

So if you're going to be adding 42

42

a lot of items into an array list, 43

43

you want to have some idea of how many items 44

44

are ultimately going to be on the list 45

45

so you can create an array list instance with 46

46

a capacity that will accommodate all the items. 47

47

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

48

that's actually storing the items, 49

49

will have to be resized when it gets full 50

50

and you wanna add more items to the list. 51

51

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

52

will be large enough by specifying the capacity. 53

53

And if we go down to the constructors, 54

54

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

55

specify the initial capacity. 56

56

And it says it constructs an empty list 57

57

with the specified capacity. 58

58

What it's actually doing is 59

59

the backing array that it creates 60

60

will be of length initial capacity. 61

61

Now when it comes to array lists, 62

62

it's important to understand the difference 63

63

between size and capacity. 64

64

Capacity is the maximum number of items 65

65

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

66

the backing array. 67

67

The size is the number of items 68

68

that are actually in the list. 69

69

So if you create an array list 70

70

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

71

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

72

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

73

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

74

which isn't a whole lot. 75

75

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

76

you're better off specifying the capacity. 77

77

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

78

and play around with array lists. 79

79

So I've created a project 80

80

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

81

academy.programming.arraylists. 82

82

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

83

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

84

our lists that isn't just integers. 85

85

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

86

and I'll call it employee. 87

87

And we'll add a 88

88

first name field, 89

89

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

90

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

91

all the boiler plate code. 92

92

So if I right click anywhere 93

93

or where I want the code to go 94

94

and I click generate, 95

95

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

96

So first of all, add a constructor. 97

97

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

98

so I'll select them and click OK. 99

99

And now we have our standard constructor 100

100

that just takes the parameters it's passed 101

101

and assigns them into the number fields. 102

102

And of course we want sets and gets for these 103

103

'cause they're private. 104

104

So once again, we'll right click, 105

105

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

106

And once again, I want getters and setters 107

107

generated for all the fields. 108

108

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

109

And now we have the standard sets and gets. 110

110

And finally, 111

111

I'd like a two string method generated. 112

112

I wanna override the default because when we print 113

113

an employee instance, I'd like to see 114

114

first name, last name, and ID. 115

115

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

116

So I'll right click, 117

117

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

118

I want all the fields and here we go. 119

119

We have a nice two string method. 120

120

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

121

Just by right clicking and go to generate 122

122

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

123

So now that we have this class, 124

124

let's go back to our main method. 125

125

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

126

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

127

is by using list, if I decide later 128

128

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

129

it's easy to change the specific implementation 130

130

of list that I'm using. 131

131

So I'm gonna call this employee list 132

132

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

133

And I'm not going to specify capacity 134

134

because I'm only gonna add four employees 135

135

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

136

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

137

So I got a couple of errors here. 138

138

First of all, there are multiple possibilities for list 139

139

because there's more than one list class. 140

140

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

141

and I want java.util. 142

142

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

143

at language level 1.6. 144

144

And if you get something like that, 145

145

it means that right now for some reason, 146

146

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

147

the JVK is Java nine, 148

148

it thinks I'm using Java 1.6. 149

149

So to get rid of that, 150

150

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

151

'cause that supports the diamond. 152

152

And so now all the errors are gone. 153

153

So if you get something like that, 154

154

just wait for the light bulb to come up 155

155

and then have it set the language level 156

156

to a higher language level. 157

157

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

158

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

159

I could just replace the specific class 160

160

that I'm using when I create the instance 161

161

and this will still work. 162

162

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

163

implements the list interface, the compilers happy. 164

164

Okay, so now that we have our list, 165

165

let's add a few employees. 166

166

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

167

an item into our list. 168

168

And I'll say new employee. 169

169

Our first employee will be Jane Jones. 170

170

And she'll have an ID of 123. 171

171

Let's add another one. 172

172

And we'll say John Doe. 173

173

And his ID is 4567. 174

174

We'll add 175

175

Mary Smith. 176

176

And her ID will be 22. 177

177

And finally we'll add 178

178

Mike Wilson. 179

179

And he'll have an ID of 3245. 180

180

And I think I'm missing a parenthesis here 181

181

so I'll just add that. 182

182

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

183

when we call the array list constructor 184

184

is creating a backing array of 10. 185

185

'Cause we saw that the default capacity, 186

186

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

187

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

188

It means that when we added our employees, 189

189

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

190

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

191

I'm gonna select it, right click 192

192

and say go to the declaration. 193

193

And this is actually on the interface. 194

194

I want to go to the implementation 195

195

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

196

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

197

because that's what we're using. 198

198

And so here we are in the actual code. 199

199

And now let's go to that implementation. 200

200

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

201

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

202

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

203

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

204

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

205

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

206

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

207

And then after it's done that, 208

208

it'll assign the item 209

209

and then of course, it gonna increase the size 210

210

because as I discussed earlier, 211

211

the capacity is the maximum number of items 212

212

that can be stored in the array, 213

213

basically the array's length, 214

214

and the size is the actual number 215

215

of items we've added to it. 216

216

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

217

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

218

Why are we using array list? 219

219

Well, because array list has a bunch of methods 220

220

that let you work with the list items. 221

221

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

222

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

223

Also, array list implements the list interface 224

224

and so as I mentioned earlier, 225

225

you can swap to another type of list 226

226

that uses the list interface 227

227

without too much disruption of the existing code. 228

228

So let's go back to our main method 229

229

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

230

We've seen how we can add items, 231

231

let's print the items on the list. 232

232

So we can say employeelist.foreach 233

233

and then we'll say employee 234

234

system.out.printlineemployee. 235

235

And now it wants, I have to move up 236

236

to language level eight because it wants lambdas. 237

237

We need Java eight for lambdas. 238

238

So this is a lambda expression 239

239

and for each employee in the list, 240

240

we're going to print that employee out. 241

241

Now I could've just used a loop 242

242

and loop through the list 243

243

but this is more concise. 244

244

So if we run now. 245

245

Here are employees 246

246

and we're getting the nice print out 247

247

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

248

So here are our employees 249

249

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

250

call one method and iterate through the list. 251

251

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

252

And so just like with arrays, 253

253

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

254

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

255

is backed by array. 256

256

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

257

we just say employeelist.get1 258

258

because the second employee will be at index one. 259

259

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

260

and John Doe does. 261

261

These four are from the four each col 262

262

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

263

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

264

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

265

is done in constant time. 266

266

Because an array is backing the list, 267

267

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

268

is done in constant time. 269

269

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

270

So array lists are great when you want to load 271

271

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

272

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

273

So we can say 274

274

system.out.printline 275

275

employeelist.isempty. 276

276

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

277

so let's run, 278

278

and sure enough, we get false. 279

279

Okay now another thing we can do 280

280

is we can replace the employee at a specific position 281

281

with another employee. 282

282

So lets replace John Doe with John Adams. 283

283

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

284

so we're not gonna use add here. 285

285

And the first parameter is the index 286

286

of the employee that we want to replace 287

287

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

288

Adams. 289

289

And John Adams has an ID of 4568. 290

290

And now if I comment out, 291

291

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

292

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

293

And let's run. 294

294

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

295

it's no long John Doe. 296

296

So if you wanna add an employee to the list 297

297

or add an item to the list 298

298

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

299

you use the add method. 300

300

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

301

you use the set method. 302

302

Now because random access is all of one setting, 303

303

an employee will happen in constant time. 304

304

As long as you're providing the index, 305

305

whatever operation you're performing will perform 306

306

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

307

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

308

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

309

So we'll just say employeelist.size. 310

310

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

311

the capacity is the total number of items this list 312

312

can currently hold. 313

313

That's the length of the backing array. 314

314

This will tell us how many employees 315

315

we've actually added to the list. 316

316

So let's run. 317

317

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

318

'Cause we have four employees on the list. 319

319

Now as I just said, the add method 320

320

adds items to the end of the list. 321

321

What if you don't want that? 322

322

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

323

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

324

but you have provide more parameters. 325

325

So if we wanted to add John Doe back in 326

326

but we wanted to add him at index three, 327

327

so we wanted him to be the fourth employee, 328

328

we'll say employeelist.add 329

329

and this time we need to provide an index 330

330

as well as the instance we want to add. 331

331

So we'll say John 332

332

Doe and 4567. 333

333

And if we now print our list again, 334

334

so I'll grab this. 335

335

And copy it here, let's run. 336

336

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

337

Now you've provided an index 338

338

but because in this case you're sticking him 339

339

in the middle of values, 340

340

some values are gonna have to be shifted up. 341

341

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

342

because the worst case would be 343

343

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

344

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

345

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

346

So we'll saw go to 347

347

the declaration and I want the implementation 348

348

for array list. 349

349

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

350

this is the shifting. 351

351

So depending on where you want to put him, 352

352

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

353

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

354

a linear time operation. 355

355

Alright, back in our code, 356

356

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

357

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

358

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

359

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

360

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

361

We'll get an object array. 362

362

So we'll say object 363

363

employee array equals employeelist.toarray. 364

364

Now if we want an employee array, 365

365

we can get it but then we have to tell 366

366

the compiler that that's what we want. 367

367

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

368

So instead of just calling the to array method 369

369

and not passing anything, we would change this call 370

370

to say new employee and the length that we want 371

371

is employeelist.size because the size method 372

372

will return how many employees we actually added. 373

373

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

374

And then when we get that array back, 375

375

let's print out 376

376

the element. 377

377

So we'll say for employee, 378

378

employee in the employee's array, 379

379

or employee array, rather. 380

380

And I'll change this to employee now 381

381

'cause we can do that. 382

382

We'll just print the employee. 383

383

So let me comment out the other print 384

384

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

385

And let's run this. 386

386

And I think there must be one more print, 387

387

yep, here it is. 388

388

Let me comment that out, run again. 389

389

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

390

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

391

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

392

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

393

you can call the contains method 394

394

to check whether the list contains an employee. 395

395

So let's go ahead and do that. 396

396

So that's system.out.printline 397

397

and we wanna check employeelist.contains 398

398

and we have to pass 399

399

the object we're looking for. 400

400

Now we don't have that instance because 401

401

we didn't save Mary anywhere 402

402

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

403

And her ID was 22. 404

404

And let's run. 405

405

And you'll see that we get false. 406

406

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

407

And the reason you get false is because 408

408

we haven't implemented the equals method 409

409

in the employee class. 410

410

So because there's no equals method, 411

411

what this method is doing is actually checking 412

412

to see if they're the exact same instance 413

413

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

414

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

415

And they're not the exact same instance. 416

416

We created an instance here 417

417

and we created an instance here. 418

418

So there are two distinct instances. 419

419

Now they're structurally the same, 420

420

meaning that all their fields contain the same values 421

421

and so we think they should be equal. 422

422

That if we're looking for an employee 423

423

with the first name Mary, the last name Smith 424

424

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

425

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

426

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

427

the individual fields against each other. 428

428

So let's go to our employee class 429

429

and I'll just put the code here. 430

430

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

431

So I'll say generate. 432

432

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

433

because whenever you override the equals method, 434

434

you should really be overriding hash code as well. 435

435

So that's fine. 436

436

We can just accept all the defaults here. 437

437

I'm gonna select these two 438

438

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

439

And now we have an equals method. 440

440

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

441

we should see true. 442

442

And we do. 443

443

Because now the equals method in the employee class 444

444

is actually looking at the values in the fields. 445

445

Now that we have the equals method, 446

446

we can make use of the index of method. 447

447

And this will look up an employee in the list 448

448

and tell us what index that employee is occupying. 449

449

So let's look at for John Doe. 450

450

So let's say system.out.printline 451

451

employeelist.indexof and once again, 452

452

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

453

we'll just create an instance with the values 454

454

and his ID is 4567. 455

455

And because we implemented the equals method, 456

456

this should find John Doe. 457

457

It'll find the employee that has 458

458

the same values in the fields. 459

459

And it does. 460

460

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

461

because we specifically added him at index three. 462

462

Now the contains and index of methods 463

463

are only as good as the search algorithm 464

464

being used to search the array. 465

465

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

466

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

467

And the way it's searching the list 468

468

will determine whether the index of 469

469

and contains method are fast or slow. 470

470

And we'll be looking at search algorithms 471

471

later in the course. 472

472

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

473

is how to remove items from the list. 474

474

Let's remove the third employee, 475

475

that's gonna be Mary. 476

476

So we'll say employeelist.remove 477

477

and we're gonna pass two 478

478

because we wanna remove the third employee. 479

479

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

480

but this is actually faster 481

481

because we're providing the index. 482

482

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

483

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

484

a bunch of stuff from the array. 485

485

And I'm gonna copy this line, 486

486

that prints out our list. 487

487

And let's run. 488

488

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

489

We just have four employees now. 490

490

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

491

remove can be expensive because elements 492

492

after the one we removed have 493

493

to be shifted down one position. 494

494

So if we take a look at that, 495

495

if we go to the source code 496

496

and I want the source code for array list, 497

497

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

498

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

499

If it has shift elements down to occupy 500

500

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

501

Okay, so there are a few more methods 502

502

in the array list class 503

503

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

504

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

505

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

506

and operations you can do on array lists. 507

507

So array list is good for random access 508

508

if you have the index 509

509

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

510

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

511

the list in any position other than the end. 512

512

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

513

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

514

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

515

So remember, it's backed by an array 516

516

and so if you have the index, 517

517

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

518

but if you don't have the index 519

519

or if you're inserting or removing elements 520

520

from somewhere in the middle of the array 521

521

or at the beginning of the array, 522

522

elements are gonna have to be shifted around. 523

523

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

524

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

525

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

526

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

527

I'll see you there.