Original subtitles

1 1

(upbeat music) 2

2

(keyboard clicking) 3

3

In this video, we'll implement the doubly linked lists. 4

4

To start us off, I've created a new project. 5

5

I'm going to put the code into 6

6

academy.learnProgramming.doublyLinkedLists, 7

7

and what I've done is I've copied the classes from the 8

8

singly linked list implementations. 9

9

So in the main method, 10

10

I've created the usual four employee instances. 11

11

The employee class is exactly the same 12

12

as we've been using in the previous videos. 13

13

The employee node is what we implemented 14

14

when we did the implementation of a singly linked list, 15

15

and the same goes for employee doubly linked list. 16

16

I've renamed the class, 17

17

but right now it's a singly link list implementation. 18

18

So the first thing we're going to do 19

19

is add a previous field to our employee node class 20

20

because now that we have a doubly linked list, 21

21

every node is gonna have two references. 22

22

So I'll say, private EmployeeNode previous, 23

23

and I'll add sets and gets. 24

24

I'll let the I to E do this for me. 25

25

I'll right click, say generate. 26

26

I want a setter and getter. 27

27

It's only gonna offer me previous 28

28

because it's smart enough to know 29

29

that we already have sets and gets for everything else. 30

30

And there we go. 31

31

And so now our nodes are going to contain 32

32

two references which we can also say two links, 33

33

one to the next node, and one to the previous node. 34

34

So now we need to update our link list implementation. 35

35

We're going to add a field for the tail 36

36

because in a doubly linked list, 37

37

we have a field that points to the head, 38

38

or the first node in the list, 39

39

any field that points to the tail, 40

40

or the last node in the list. 41

41

So we'll say private, employee node, 42

42

tail, and just like the head, 43

43

this will be initialised to null so we don't need 44

44

to create a constructor that does that. 45

45

So when it comes to the add to front method, 46

46

when we add a node to the front of the list, 47

47

it's going to become the first node in the list, 48

48

and so its previous field will always point to null, 49

49

so we don't have to handle the previous field 50

50

because the previous field in the employee node instance 51

51

will always be initialised to null, 52

52

so there's no need for us to set the previous field in here, 53

53

but we're gonna have to change the previous field 54

54

of the node that's currently at the head of the list 55

55

because the previous field of the current head node 56

56

will have to point to the node that we're adding 57

57

because whatever's at the head of the list right now 58

58

is going to become the second node in the list, 59

59

and its previous field is going to point back 60

60

to the node that we're adding. 61

61

The other thing we have to handle in add to front 62

62

is the case of when we're starting with an empty list 63

63

because when we're starting with an empty list, 64

64

both the head and the tail point to null, 65

65

and when we add a node to an empty list when we're done, 66

66

both the head and the tail should be pointing to the node. 67

67

Now normally we wouldn't have to worry about the tail. 68

68

If there's already one or more nodes in the list 69

69

and we add a node to the front, 70

70

the tail isn't going to change because we're growing 71

71

the list from the head not from the tail. 72

72

So the only time that we have to worry 73

73

about setting the tail is if we're adding a node 74

74

into an empty list, if this is the first node we're adding. 75

75

So we need to make a couple of changes here. 76

76

We have to check whether we're adding a node 77

77

to an empty list, and if we are, 78

78

we need to set the tail to that new node, 79

79

and also if we're not adding into an empty list, 80

80

then we need to change the current head's previous field 81

81

to the node we're adding. 82

82

So before we set the head, we're going to say, 83

83

if head equals null, 84

84

and we could call our is empty method two, 85

85

but I'm gonna say head equals null to make 86

86

it clear what we're doing here. 87

87

If we're adding this node into an empty list, 88

88

then we need to set the tail. 89

89

So we'll say tail equals node. 90

90

If we're not adding the node into an empty list, 91

91

we don't need to worry about the tail. 92

92

The tail isn't going to change. 93

93

Okay, so if we're adding the node to an empty list, 94

94

we set the tail to node. 95

95

If the list is not empty, then we need to set 96

96

the current head node's previous field to the new node. 97

97

So we'll say else, head.setPrevious 98

98

to the node that we're adding, and that's it. 99

99

That's the only changes we have to make. 100

100

Now up here, we're setting the next field of the new node 101

101

to whatever head is, and if head is null, that's fine. 102

102

If we're adding into an empty list, 103

103

we want the next field to be null because the node 104

104

we're adding is gonna be the only node in the list, 105

105

and so there's nothing coming after it, 106

106

and so its next field will be null. 107

107

And as I mentioned earlier, we don't have to worry 108

108

about setting the previous field of the node we're adding 109

109

because that's always going to be null 110

110

because it's being added as the first item in the list, 111

111

so there's nothing before it. 112

112

Okay, so add to front is done. 113

113

Let me update our print list, 114

114

and what I'm going to do is I'm gonna change 115

115

this arrow to sort of like a double arrow 116

116

so we know that there are two links, 117

117

just to make that a little clearer, 118

118

and now let's go to our main method, 119

119

and let's add some employees to our doubly linked list. 120

120

So we'll say EmployeeDoublyLinkedList, list 121

121

equals new EmployeeDoublyLinkedList, 122

122

and we'll say list.addToFront. 123

123

There's nothing new here. 124

124

We did this with the singly linked list. 125

125

So we'll add Jane Jones, 126

126

John Doe, 127

127

Mary Smith, and 128

128

Mike Wilson, 129

129

and then we'll print our list, 130

130

and let's get the size too 131

131

just to make sure we're incrementing that size correctly, 132

132

so we'll print list.getSize. 133

133

All right, let's run. 134

134

And we'll see that we have four employees, 135

135

and just as before, 136

136

because we're always adding to the front, 137

137

we have Mike in the front position 138

138

followed by Mary, followed by John, followed by Jane. 139

139

That double arrow there is a single arrow. 140

140

I could add a test here to see when we're looking 141

141

at the last node, but I think you understand 142

142

that null isn't pointing back. 143

143

Jane Jones is just pointing to null. 144

144

Okay, let me close this off, 145

145

and now let's add a add to end, or add to tail method. 146

146

I'll call it add to end. 147

147

Now for this method, we have to set 148

148

the previous field to point to the node 149

149

that's currently at the end of the list. 150

150

Remember, we're gonna have a node that's pointed 151

151

to by tail, and we wanna insert a node at the end, 152

152

so we want tail to point to the new node, 153

153

and we want the new node's previous field 154

154

to point to whatever the current tail is. 155

155

Now, once again, we also have to worry about 156

156

whether we're trying to add to the end of an empty list 157

157

because if we are, we're gonna want to set the head 158

158

to the new node just like in the add to front 159

159

if we were inserting into an empty list 160

160

we wanted to set the tail to the new node. 161

161

So we'll say public void addToEnd, 162

162

and again, we want the employee, 163

163

and so we'll create a new node as we've done before. 164

164

And now we want to test whether we have an empty list or not 165

165

so we'll say if, and it doesn't really matter here 166

166

if we test head or tail. 167

167

Since we're in the add to end method, we'll test tail. 168

168

So if tail equals null, 169

169

we want to set the head to the new node, and don't worry, 170

170

we'll take care of the tail field in a minute. 171

171

Otherwise, we wanna set the current tail's next field 172

172

to the node we're adding, and we wanna set 173

173

the previous field of the node we're adding 174

174

to what used to be the tail. 175

175

So if we have let's say just Jane in the list, 176

176

and we're adding John, and we're adding John to the end, 177

177

we're gonna want Jane, the current tail, 178

178

we're gonna want her next field 179

179

to point to John who is the new node, 180

180

and we're gonna want John's previous field 181

181

to point to Jane, and she's currently the tail 182

182

'cause we haven't changed the tail yet, 183

183

and that's what we're gonna do now. 184

184

So our final step is to set the tail to node, 185

185

and of course we need to increment the size. 186

186

And so this adds an employee to the end. 187

187

So let's go back to the main method, 188

188

and let's add Bill to the end of our list. 189

189

Let me create the employee instance separately 190

190

so I'll say Employee billEnd to show that we want him 191

191

at the end, equals new Employee Bill, End, 192

192

and we'll give him an ID of 78, 193

193

and then we'll say list.addToEnd, billEnd, 194

194

and I'll call copy these two lines. 195

195

We'll print our list, and we'll print the size 196

196

just to make that we're incrementing the size correctly. 197

197

All right, let's run. 198

198

And now we'll see we have five employees, 199

199

and this time, Bill is not at the front of the list 200

200

because that's not where we've added him. 201

201

So we've got Mike, Mary. 202

202

So far, our list is the same. 203

203

John Doe, 204

204

Jane Jones, and finally we have Bill end at the very end, 205

205

so he's where he's supposed to be. 206

206

I'll just close this down, 207

207

and let's go back to our link list class. 208

208

Now just as in the add to front method, 209

209

we didn't have to worry about setting the new nodes 210

210

previous field 'cause it would be initialised to null. 211

211

In the add to end method, we don't have to worry 212

212

about setting the new node's next field 213

213

because it's initialised to null. 214

214

Okay, so now let's look at removing items. 215

215

So we have a remove from front method at the moment, 216

216

and now we have to do a bit more work 217

217

because we have to worry about the tail, 218

218

and we have to worry about the previous field 219

219

in whatever node comes after the head. 220

220

Now it's possible we're going to be removing the only node 221

221

in the list, so we have to handle that special case. 222

222

So basically what do we wanna do? 223

223

Let's suppose that we just have John and Jane in the list, 224

224

and John is at the front. 225

225

So when we take John away, Jane's next field 226

226

will not change, so we don't have to worry about that, 227

227

but her previous field has to change, 228

228

and she wants to point to whatever came before John, 229

229

and so she'll wanna point to John's previous field 230

230

because we're gonna take John out, 231

231

so whatever was previously before John 232

232

will now be before Jane. 233

233

Now, if we're removing from the front, that'll be null, 234

234

so we could explicitly set her field to null, or we 235

235

could just set her to whatever John's previous field has. 236

236

And then we want to move the head, 237

237

and so we'll set the head to Jane, and that's it. 238

238

If we want, we can clean up the references. 239

239

In John's nodes, we could set his next reference to null 240

240

just like we're already doing, 241

241

but essentially what we really have to handle here 242

242

on top of what we're already doing is Jane's previous field. 243

243

Now, if John is the only node in the list, 244

244

then we're gonna have to worry about updating the tail 245

245

because the tail will now become null. 246

246

If John isn't the only node in the list, 247

247

we don't have to change the tail. 248

248

The tail's gonna stay the same 'cause we're taking 249

249

the front node off the list, 250

250

and so if he isn't the only node in the list, 251

251

the tail isn't gonna change. 252

252

It's still gonna be pointing to the last node in the list. 253

253

Okay, so after we've saved off the node we're removing 254

254

into remove node, we're gonna test 255

255

to see if we're removing the only node in the list, 256

256

and we'll do that by saying if head.getNext equals null 257

257

because if the head node, if the next field in the head node 258

258

is null, it means we've only got one node in the list 259

259

so we're removing the only node, and so in that case, 260

260

we have to worry setting the tail to null. 261

261

If we're not removing the only node in the list, 262

262

then we're going to handle Jane's previous field, 263

263

and so we're gonna say head.getNext 264

264

because if Jane's the second node in the list, 265

265

John's next field is pointing to her, 266

266

so that's head.getNext, so this will return Jane, 267

267

and we wanna set her previous field to null. 268

268

We could set this to head.getPrevious 269

269

but because we know we're removing from the front, 270

270

we'll just ahead and set it to null, 271

271

and then we do what we did before. 272

272

We set the head to head.getNext 'cause that's Jane, 273

273

and we decrement the size, 274

274

and here we're just cleaning up a reference. 275

275

We don't have to do that but we're cleaning it up, 276

276

and then we return the node. 277

277

So let's go back to our main method, 278

278

and let's remove from the front of the list, 279

279

so we'll say list.removeFromFront. 280

280

We don't have to pass anything 281

281

'cause we're taking off the first person in the list. 282

282

And we'll print out our list, and the size again. 283

283

So let's run. 284

284

So we're back to four employees, 285

285

and now Mary is the first employee on the list. 286

286

Mike is gone. 287

287

And so if we go to the end, Bill's still at the end. 288

288

We didn't touch him, 289

289

and we have one fewer employees than we did before. 290

290

Okay, so we have methods for adding to the front 291

291

of the list, adding to the end of the list, 292

292

removing from the front, so I guess we need 293

293

a remove from end method, so let's write that now. 294

294

Public EmployeeNode, removeFromEnd. 295

295

We don't need to pass anything 296

296

'cause we're always removing the last node. 297

297

What do we wanna do when we remove from the end? 298

298

Well, right now we have Jane at the end, let's say, 299

299

and then Bill, and we wanna remove Bill, 300

300

so we're gonna have to change the tail 301

301

because the tail is now going to become Jane, 302

302

so in this case, we do have to worry 303

303

about changing the tail, 304

304

and we're gonna want to set Jane's next field to null 305

305

because now she'll be the end of list. 306

306

And if we wanted to, 307

307

we can clean up Bill's previous field. 308

308

Now if Bill is the only one in the list, 309

309

we also have to worry about setting head to null 310

310

because if Bill is the only node in the list, 311

311

so we remove him and there's an empty list, 312

312

then we have to set head back to null, 313

313

so we're gonna have to check for that case, 314

314

but the very first thing we're gonna do 315

315

is check for an empty list. 316

316

I'll just copy this code. 317

317

So if you have an empty list, 318

318

we obviously don't have to do anything, 319

319

nothing to remove. 320

320

If we don't have an empty list, 321

321

we'll say EmployeeNode, removedNode equals tail. 322

322

So up here, the removed node was the head, 323

323

but in remove from end, the remove node 324

324

will obviously be the tail. 325

325

And then we'll do the same thing we did up here, 326

326

but this time I'll use if tail.getNext equals null because 327

327

that would mean that this is the only node in the list. 328

328

Now when we only have one node in the list, 329

329

the head and the tail are both pointing to the same node. 330

330

I used head here because we're removing from the front. 331

331

I'll use tail here 'cause we're removing from the back, 332

332

but essentially we're doing the same thing. 333

333

So if tail.getNext equals null, 334

334

then we only have one node in the list, and so in that case, 335

335

we have to worry about setting the head to null. 336

336

So you can kinda see we're doing the mirror image here. 337

337

Here we had to worry about setting the tail to null 338

338

'cause we set the head, we take care of the head here, 339

339

and here we have to worry about setting the head to null. 340

340

So if we have more than one node in the list, 341

341

then what we wanna do here is the node that's becoming 342

342

the new tail, we want to set their next field to null, 343

343

and we can do that the same way we did up here. 344

344

So we get tail.previousNode 'cause that's going 345

345

to become the new tail, 346

346

and then we'll set its next field to null. 347

347

So we'll say tail.getPrevious.setNext to null. 348

348

And so if we have the situation where we're removing Bill, 349

349

and Jane is gonna become the new tail, 350

350

well Bill is currently the tail 351

351

'cause we haven't changed that yet. 352

352

His previous field is pointing to Jane, 353

353

and so her next field will now become null 354

354

because she'll be the last node in the list. 355

355

And then finally, we're gonna set the tail to 356

356

tail.getPrevious 357

357

because the new tail is now going to be Jane, 358

358

and so right now, tail is pointing to Bill. 359

359

His previous is pointing to Jane, 360

360

and so the new tail becomes Bill, basically, .getPrevious. 361

361

And now we'll do what did here, 362

362

so I'll copy these lines of code. 363

363

We wanna decrement the size. 364

364

This time, we want to remove node's previous 365

365

field to be set to null to clean that up, 366

366

and then we return the remove node. 367

367

So these two methods 368

368

are kind of mirror images of each other. 369

369

In one case, we're more concerned with what's going 370

370

on at the head obviously, and in the other case, 371

371

we're more concerned with what's going on at the tail. 372

372

In this case, we have to worry about the tail 373

373

only when we're removing the only node in the list, 374

374

and in this case, we have to worry about the head 375

375

if we're removing the only node in the list. 376

376

Otherwise, we're just worrying about the tail. 377

377

when we're removing from end, and we're just worrying 378

378

about the head when we're removing from front. 379

379

And if you look at these two methods, 380

380

it's kind of the same thing. 381

381

They're a little bit different 382

382

but we could have written them similarly. 383

383

In this case, in the add to front, 384

384

we're always setting the next field of the node 385

385

to whatever's at the head, 386

386

and in the add to end, we're only doing that 387

387

if we're dealing with a list that's not empty, 388

388

so if we're adding the node into a list that isn't empty, 389

389

because when you think about it, 390

390

if the list is empty, this statement here 391

391

is just gonna set the next field to null, 392

392

and we don't really need to do that because the node's 393

393

next field is initialised so we could do this. 394

394

We could take this statement here 395

395

and do the same thing that we're doing here, 396

396

and only worry about setting the next field 397

397

if we're dealing with a list that isn't empty 398

398

so that there's already nodes in it, and so yeah, 399

399

when we add the new node into the list, 400

400

we'll worry about setting the next field. 401

401

Otherwise the next field is already set. 402

402

So now they're mirror images of each other. 403

403

And let's run to see if everything's working. 404

404

Before we do that, let's go back to main, 405

405

and let's remove an item from the end of the list. 406

406

So I'm gonna copy these three lines. 407

407

I'm gonna say remove from end, 408

408

and let's run. 409

409

All right, so we started off with adding four employees, 410

410

and we have Mike Wilson, Mary Smith, John Doe, 411

411

and Jane Jones, and we have four employees in the list, 412

412

then we added up here. 413

413

We added Bill to the end, so now we have five employees, 414

414

and we have Bill right at the end, 415

415

and then we removed the first employee from the front 416

416

so we're back down to four employees, and Mike is gone, 417

417

and now finally, we removed an employee from the end, 418

418

so we're down to three employees, 419

419

and obviously something went wrong here. 420

420

So let's go back to our code. 421

421

Let me shut this down. 422

422

Can you spot the error? 423

423

Right here, we said if tail.getNext equals null. 424

424

Well, the next field of the tail is always going to be null, 425

425

and so what happened is we set the head to null, 426

426

and that's why if I go back to thing here, 427

427

our head basically blew away our list here. 428

428

So this should be if tail.getPrevious equals null, 429

429

then we know we only have one node in the list. 430

430

Let's run that again. 431

431

All right, this time we didn't blow our list away. 432

432

So we went through the first results, 433

433

and then finally back here, 434

434

we wanted to remove Bill from the end, 435

435

so we have Mary Smith, John Doe, and Jane Jones, 436

436

and we removed Bill from the end, 437

437

and we have three employees. 438

438

And so our code is working once we fixed that bug. 439

439

If you only have one node in the list, 440

440

then tail and head are pointing at the same thing, 441

441

but obviously if you don't have just one node in the list, 442

442

then we wanna be testing the previous field for the tail 443

443

'cause we wanna know if there's anything before the tail 444

444

because there's never going to be anything after the tail, 445

445

so that's why we blew our list away here. 446

446

Here we wanna use get next because, in that case, 447

447

there's never anything before the head, 448

448

so we've gotta check what comes after. 449

449

Okay, so that's it for a simple implementation 450

450

of a doubly linked list. 451

451

I just wanted to give you some idea 452

452

of what's going on under the covers. 453

453

Now, as I mentioned a few videos ago, 454

454

the JDK has a link-list class, 455

455

so if you wanna use a link list, 456

456

you're probably going to use the class in the JDK, 457

457

and so in the next video, 458

458

we'll take a quick look at that class. 459

459

I'll see you there.