All language subtitles for 8. Doubly Linked Lists (Implementation)

(upbeat music)
2

(keyboard clicking)
3

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

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

I'm going to put the code into
6

academy.learnProgramming.doublyLinkedLists,
7

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

singly linked list implementations.
9

So in the main method,
10

I've created the usual four employee instances.
11

The employee class is exactly the same
12

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

The employee node is what we implemented
14

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

and the same goes for employee doubly linked list.
16

I've renamed the class,
17

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

So the first thing we're going to do
19

is add a previous field to our employee node class
20

because now that we have a doubly linked list,
21

every node is gonna have two references.
22

So I'll say, private EmployeeNode previous,
23

and I'll add sets and gets.
24

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

I'll right click, say generate.
26

I want a setter and getter.
27

It's only gonna offer me previous
28

because it's smart enough to know
29

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

And there we go.
31

And so now our nodes are going to contain
32

two references which we can also say two links,
33

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

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

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

because in a doubly linked list,
37

we have a field that points to the head,
38

or the first node in the list,
39

any field that points to the tail,
40

or the last node in the list.
41

So we'll say private, employee node,
42

tail, and just like the head,
43

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

to create a constructor that does that.
45

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

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

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

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

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

because the previous field in the employee node instance
51

will always be initialised to null,
52

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

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

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

because the previous field of the current head node
56

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

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

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

and its previous field is going to point back
60

to the node that we're adding.
61

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

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

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

both the head and the tail point to null,
65

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

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

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

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

and we add a node to the front,
70

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

the list from the head not from the tail.
72

So the only time that we have to worry
73

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

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

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

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

to an empty list, and if we are,
78

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

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

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

to the node we're adding.
82

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

if head equals null,
84

and we could call our is empty method two,
85

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

it clear what we're doing here.
87

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

then we need to set the tail.
89

So we'll say tail equals node.
90

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

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

The tail isn't going to change.
93

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

we set the tail to node.
95

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

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

So we'll say else, head.setPrevious
98

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

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

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

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

If we're adding into an empty list,
103

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

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

and so there's nothing coming after it,
106

and so its next field will be null.
107

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

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

because that's always going to be null
110

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

so there's nothing before it.
112

Okay, so add to front is done.
113

Let me update our print list,
114

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

this arrow to sort of like a double arrow
116

so we know that there are two links,
117

just to make that a little clearer,
118

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

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

So we'll say EmployeeDoublyLinkedList, list
121

equals new EmployeeDoublyLinkedList,
122

and we'll say list.addToFront.
123

There's nothing new here.
124

We did this with the singly linked list.
125

So we'll add Jane Jones,
126

John Doe,
127

Mary Smith, and
128

Mike Wilson,
129

and then we'll print our list,
130

and let's get the size too
131

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

so we'll print list.getSize.
133

All right, let's run.
134

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

and just as before,
136

because we're always adding to the front,
137

we have Mike in the front position
138

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

That double arrow there is a single arrow.
140

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

at the last node, but I think you understand
142

that null isn't pointing back.
143

Jane Jones is just pointing to null.
144

Okay, let me close this off,
145

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

I'll call it add to end.
147

Now for this method, we have to set
148

the previous field to point to the node
149

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

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

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

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

and we want the new node's previous field
154

to point to whatever the current tail is.
155

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

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

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

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

if we were inserting into an empty list
160

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

So we'll say public void addToEnd,
162

and again, we want the employee,
163

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

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

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

if we test head or tail.
167

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

So if tail equals null,
169

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

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

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

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

the previous field of the node we're adding
174

to what used to be the tail.
175

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

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

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

we're gonna want her next field
179

to point to John who is the new node,
180

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

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

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

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

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

and of course we need to increment the size.
186

And so this adds an employee to the end.
187

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

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

Let me create the employee instance separately
190

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

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

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

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

and I'll call copy these two lines.
195

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

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

All right, let's run.
198

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

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

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

So we've got Mike, Mary.
202

So far, our list is the same.
203

John Doe,
204

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

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

I'll just close this down,
207

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

Now just as in the add to front method,
209

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

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

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

about setting the new node's next field
213

because it's initialised to null.
214

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

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

and now we have to do a bit more work
217

because we have to worry about the tail,
218

and we have to worry about the previous field
219

in whatever node comes after the head.
220

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

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

So basically what do we wanna do?
223

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

and John is at the front.
225

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

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

but her previous field has to change,
228

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

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

because we're gonna take John out,
231

so whatever was previously before John
232

will now be before Jane.
233

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

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

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

And then we want to move the head,
237

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

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

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

just like we're already doing,
241

but essentially what we really have to handle here
242

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

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

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

because the tail will now become null.
246

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

we don't have to change the tail.
248

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

the front node off the list,
250

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

the tail isn't gonna change.
252

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

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

into remove node, we're gonna test
255

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

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

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

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

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

we have to worry setting the tail to null.
261

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

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

and so we're gonna say head.getNext
264

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

John's next field is pointing to her,
266

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

and we wanna set her previous field to null.
268

We could set this to head.getPrevious
269

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

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

and then we do what we did before.
272

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

and we decrement the size,
274

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

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

and then we return the node.
277

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

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

so we'll say list.removeFromFront.
280

We don't have to pass anything
281

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

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

So let's run.
284

So we're back to four employees,
285

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

Mike is gone.
287

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

We didn't touch him,
289

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

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

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

removing from the front, so I guess we need
293

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

Public EmployeeNode, removeFromEnd.
295

We don't need to pass anything
296

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

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

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

and then Bill, and we wanna remove Bill,
300

so we're gonna have to change the tail
301

because the tail is now going to become Jane,
302

so in this case, we do have to worry
303

about changing the tail,
304

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

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

And if we wanted to,
307

we can clean up Bill's previous field.
308

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

we also have to worry about setting head to null
310

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

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

then we have to set head back to null,
313

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

but the very first thing we're gonna do
315

is check for an empty list.
316

I'll just copy this code.
317

So if you have an empty list,
318

we obviously don't have to do anything,
319

nothing to remove.
320

If we don't have an empty list,
321

we'll say EmployeeNode, removedNode equals tail.
322

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

but in remove from end, the remove node
324

will obviously be the tail.
325

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

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

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

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

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

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

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

but essentially we're doing the same thing.
333

So if tail.getNext equals null,
334

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

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

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

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

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

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

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

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

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

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

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

to become the new tail,
346

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

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

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

and Jane is gonna become the new tail,
350

well Bill is currently the tail
351

'cause we haven't changed that yet.
352

His previous field is pointing to Jane,
353

and so her next field will now become null
354

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

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

tail.getPrevious
357

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

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

His previous is pointing to Jane,
360

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

And now we'll do what did here,
362

so I'll copy these lines of code.
363

We wanna decrement the size.
364

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

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

and then we return the remove node.
367

So these two methods
368

are kind of mirror images of each other.
369

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

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

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

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

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

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

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

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

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

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

And if you look at these two methods,
380

it's kind of the same thing.
381

They're a little bit different
382

but we could have written them similarly.
383

In this case, in the add to front,
384

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

to whatever's at the head,
386

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

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

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

because when you think about it,
390

if the list is empty, this statement here
391

is just gonna set the next field to null,
392

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

next field is initialised so we could do this.
394

We could take this statement here
395

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

and only worry about setting the next field
397

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

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

when we add the new node into the list,
400

we'll worry about setting the next field.
401

Otherwise the next field is already set.
402

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

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

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

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

So I'm gonna copy these three lines.
407

I'm gonna say remove from end,
408

and let's run.
409

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

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

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

then we added up here.
413

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

and we have Bill right at the end,
415

and then we removed the first employee from the front
416

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

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

so we're down to three employees,
419

and obviously something went wrong here.
420

So let's go back to our code.
421

Let me shut this down.
422

Can you spot the error?
423

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

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

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

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

our head basically blew away our list here.
428

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

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

Let's run that again.
431

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

So we went through the first results,
433

and then finally back here,
434

we wanted to remove Bill from the end,
435

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

and we removed Bill from the end,
437

and we have three employees.
438

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

If you only have one node in the list,
440

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

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

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

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

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

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

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

there's never anything before the head,
448

so we've gotta check what comes after.
449

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

of a doubly linked list.
451

I just wanted to give you some idea
452

of what's going on under the covers.
453

Now, as I mentioned a few videos ago,
454

the JDK has a link-list class,
455

so if you wanna use a link list,
456

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

and so in the next video,
458

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

I'll see you there.