All language subtitles for 6. Singly Linked Lists (Implementation)

(lively music)
(keyboard clacking)
2

So, let's implement a simple singly linked class.
3

I've created a project,
4

I'm putting the code into package
5

academy.learnprogramming.linkedlists.
6

I've created our four employees that we used
7

in the array list video.
8

This time I've assigned them to employee variables
9

and I've also added the employee class
10

and all I did was copied and pasted the class
11

over from the array list project,
12

so it's a straightforward class.
13

We have three fields
14

and we just have the usual boilerplate code.
15

We have our equals method
16

and we have our override toString.
17

So, the first class we'll work on
18

is the node class and this class
19

is going to need two variables,
20

one for the employee instance
21

and one for the next node in the list
22

because remember, when we're working with a linked list,
23

every node knows about the next node in the list
24

and so, we need a field that contains a reference
25

to the next node in the list
26

and that's why the data structure is called a linked list
27

if you hadn't already figured that out.
28

In Java, by contains a link,
29

we mean that it stores the object reference
30

of the next node.
31

So, let's add a node class,
32

so I'll say New, Java Class.
33

And I'm going to call this EmployeeNode
34

rather than just plain old Node
35

because I'm not going to use generics
36

to write this linked list,
37

I want us to just focus
38

on the linked list implementation
39

and on top of that you're not going to write
40

your own linked list, you'll end up using the one
41

in the JDK and even if you did write a linked link class
42

for your application,
43

you'd probably make it specific
44

to the type of data you're dealing with.
45

The only reason that you would need to use generics
46

is if you're going to write a class
47

that's going to be released publicly
48

and so that many, many applications
49

are going to use it
50

and in that case, you'd wanna use generics
51

'cause you'd want it to be usable
52

with a variety of object types.
53

But for our purposes, we're just gonna focus
54

on the implementation of the linked list
55

and so, I'm not gonna use generics
56

and so, I'm calling this EmployeeNode
57

to make it clear that this node
58

will only work with employee instances.
59

So, as I said, we're gonna need two fields,
60

we're gonna need one for the employee
61

and we're going to need a field
62

that stores a reference to the next node in the list.
63

So, we'll call that next.
64

So, for the constructor, we just need the employee,
65

so I'll say public EmployeeNode
66

and we just need the employee for that.
67

And so, we'll just say this.employee equals employee.
68

And to make things quick and easy,
69

I'll have the IDE just create me a bunch
70

of sets and gets, so I'll say Generate,
71

Getter and Setter, I want it for both fields,
72

click OK and there we go.
73

We have our sets and gets.
74

So, the constructor only takes employee
75

because when we construct an instance,
76

we don't know yet what the next node will be.
77

We'll add that later, you'll see when we implement
78

the insert method, we create the node first
79

and then we figure out which node
80

is supposed to be assigned to it next field.
81

Now, as we saw in the slides,
82

if a node is the last node in the list,
83

meaning that there isn't any node following it,
84

then its next field will be set to null
85

and so, when we traverse the list,
86

that's how we'll know we've reached the end.
87

We don't have to set next to null
88

in the constructor because that's the default value
89

for object fields.
90

So, we have a class for the node,
91

what about the linked list itself?
92

Well, as we saw from the slides,
93

all we need to know for the linked list
94

is the head node, that's it.
95

From there we can traverse the entire list
96

because every node in the list contains a link
97

to the next node
98

and so, let's create a class for a linked list.
99

And I'm gonna call this EmployeeLinkedList once again
100

to make it clear that this only works with employee nodes.
101

And this just needs one field.
102

It needs a field for the head node,
103

so private EmployeeNode
104

head, that's it.
105

So, let's say we wanna add an item to the linked list.
106

For the best performance, we should add items
107

to the beginning, so we don't have to traverse the list
108

looking for an insertion point
109

and so, we're going to code an addToFront method.
110

So, we'll say public void addToFront
111

and we need the employee instance that we wanna add,
112

so we'll say EmployeeNode node equals new EmployeeNode
113

and we just have to pass the employee
114

and then we need to set this new node's next field.
115

Its new node's next field is going to point
116

at whatever head it's currently pointing at
117

because when we add a new node to the front of the list,
118

the current head of the list
119

is now going to become the second node in the list
120

and so, this new node
121

is going to point to the current head
122

as we saw in the slides.
123

So, we'll say node.setNext head.
124

And then of course the last thing we wanna do
125

is set head to the new node.
126

So, if you're having trouble understanding this,
127

go back to the slides
128

but essentially, we're inserting the node right
129

at the front of the list,
130

so let's say our list contains employee Jane
131

and we're inserting John.
132

When we come in, the head field
133

will be pointing to Jane.
134

When we've finished inserting John,
135

we want John to be pointing to Jane
136

and the head field to be pointing to John.
137

So, first we create the new node
138

and then we set John which is the new node,
139

John's next field to Jane
140

because that's currently the one
141

being pointed to by head
142

and then we set head to John
143

and so, we end up with a head field
144

that points to John and John's next field points
145

to Jane, I'll just delete this blank line here
146

and now let's go back to our main method
147

and let's create a linked list
148

and add some employees to it.
149

So, we'll say EmployeeLinkedList
150

and I'll just call it list equals new EmployeeLinkedList
151

and then we'll say list.addToFront
152

and we'll add janeJones,
153

list.addToFront johnDoe,
154

list.addTofront marySmith
155

and list.addToFront mikeWilson.
156

And we're gonna need a way to print our list,
157

so let's go back to our LinkedList class
158

and add a printList method.
159

So, we'll say public void printList
160

and we'll say EmployeeNode current
161

equals the head of the list
162

'cause we're gonna start at the head
163

and I'm gonna print out something here
164

that says HEAD
165

and then we wanna keep traversing the list
166

until current hits null,
167

so while current is not equal to null
168

because when it hits null, we've hit the end of the list,
169

we'll say System.out.print current
170

and I'm gonna change this to print as well
171

because I don't want that to be printed on its own line.
172

And then I'll print an arrow
173

and then we want to move to the next node,
174

so current equals current.getNext.
175

This isn't perfect, we're gonna end up with an arrow after
176

but I can say System.out.print line null
177

and so, the last item in the list will be null.
178

This will work fine
179

but what we'll see right now if we were to call this
180

is a bunch of object references
181

because we've overridden employee,
182

we've overridden the toString method and employee
183

but we haven't overridden it in our node class.
184

So, let's do that now.
185

And what I actually wanna print out
186

is the employee information when we print a node,
187

so I'll just call the employees toString method,
188

so I'll say public String toString
189

and I want to return employee.toString
190

and so, when we print a node,
191

what will actually be printing
192

is the result of this toString method.
193

So, let's call our printList method now and let's run.
194

So, we have the head of our list
195

and then you'll see that Mike Wilson comes first.
196

We added Jane first
197

but we're constantly adding new employees
198

to the front of the list,
199

so every time we add a new employee,
200

the existing employees gets bumped down the list.
201

So, we added Mike last, so he's gonna be the head
202

of the list 'cause we're always adding to the front,
203

followed by Mary Smith
204

followed by John Doe
205

and followed by Jane Jones and she'll be pointing to null
206

because she's the last node in the list
207

and so, that's all there is to inserting a node
208

into the linked list at the front of the list.
209

We could write a method
210

that adds employees to the end of the list
211

or that looks very specific employee in the list
212

and adds an employee after that employee
213

or before the employee
214

but those methods will be on the order of O of n,
215

they'll be linear because then we have to traverse the list
216

and the worst case will always be
217

that we have to traverse the entire list.
218

That would be true if we wanted to add a node
219

to the end.
220

Now, some implementations of linked list
221

will have a pointer to the tail of the list,
222

the last node in the list
223

but that's not really a true singly linked list,
224

it's a variation on them
225

but you could do that
226

if you thought you were constantly gonna be wanting
227

to add items to the end of the list,
228

you could keep a reference to the last node in the list
229

which is called the tail
230

but for a linked list implementation
231

that's only keeping reference to the head,
232

if you wanted to insert items at the end,
233

you'd have to traverse the entire list
234

and in either way whether you kept a reference
235

to the tail or not,
236

if you wanted to insert items
237

at a specific point in the list,
238

like before or after a specific employee,
239

you gonna have to traverse the list looking
240

for that employee and so, a singly linked list
241

is best used when you want to insert and remove items
242

from the front of the list.
243

Now, the other things to note is is that a linked list
244

can continue to grow
245

without having to be resized.
246

Remember, with arrays, once the array is full,
247

if we wanna add more items to it,
248

we have to resize the array
249

but that's not true of a linked list.
250

With a linked list, you're pretty much only bounded
251

by the memory you have.
252

Now, talking about memory,
253

one disadvantage to a linked list
254

is you have to store that extra field with every value.
255

You don't have to do that with arrays,
256

so is memory's really tight,
257

that could be one disadvantage to using a linked list
258

even if you will only wanna be adding
259

and deleting items from the front
260

if memory is tight and you're gonna have a lot of items,
261

maybe a linked list wouldn't be your best choice.
262

So, as usual, it's going to depend on your application,
263

the platform you're running on,
264

what the application's gonna wanna do
265

with the data, et cetera.
266

There isn't a one-size-fits-all answer.
267

So, let's say that we wanted to know how many items
268

are in the linked list.
269

We could traverse the list
270

and count how many items there are
271

but another way to do it
272

would be to just keep a running count
273

of how many nodes are in the list
274

and we're gonna do it that way.
275

So, let's go back to our LinkedList class
276

and we're gonna add a size field,
277

so we'll say private int size
278

and that will be initialised to zero by default
279

when the list is created
280

and then whenever we add an employee of course,
281

we want to increment the size
282

and it would be nice for us to have a get,
283

I'll just type this out 'cause it's quick,
284

so public int getSize and we just return the size.
285

Let's go back to our main method
286

and call our getSize method
287

after we've added these employees,
288

so we'll say System.out.print line list.getSize
289

and we should get four.
290

Let's run.
291

And sure enough we get four employees in our list.
292

So, we could now add an isEmpty method
293

that tells us whether the linked list is empty.
294

We could just call the getSize method
295

and test whether the number of items
296

in the list is zero but there's another way
297

to test whether a list is empty.
298

Can you think about what that way is
299

if we looked at the linked list implementation for a minute?
300

Can you come up with another way,
301

a quick way of testing whether a linked list is empty?
302

If head is null, that means the list is empty, right?
303

'Cause head is null.
304

It's not pointing to any nodes.
305

So, one way we could write an isEmpty method
306

is to say public boolean isEmpty
307

and we return head equals null
308

and so, if we go back to main now,
309

and we call this right at the top,
310

before we add anything and we say System.out.print line
311

list.isEmpty we should get true here.
312

Let's run.
313

And sure enough we get true.
314

Our list is empty before we've added anything to it.
315

So, the last method we'll look at
316

is how do we remove items from the front?
317

And we saw that in the slides.
318

Let's go to our LinkedList class
319

and let's write the method,
320

so we'll say public and we're gonna return the node
321

that we removed in case the caller wants
322

to do anything with it
323

and we'll same removeFromFront.
324

We don't need to pass anything
325

'cause we're always gonna remove the node
326

that's right at the front.
327

So, the first thing we do
328

is we need to test if the list is empty
329

because if the list is empty,
330

there's nothing to remove,
331

so we'll say if isEmpty,
332

we'll just return null.
333

We don't have anything to do.
334

If the list isn't empty,
335

what we're gonna do is store the first node
336

on the list, I'll call this removeNode,
337

that's what I called it in the slides,
338

is the head node, right?
339

So, the node that we're gonna remove
340

is pointed to by the head node,
341

that's the object reference that's stored in the head field.
342

So, we'll assign that to removeNode
343

and then we want to move the head.
344

The head will equal head.getNext.
345

So, if we have the situation where we're pointing
346

at Mike, head is pointing to Mike
347

and we want Mike to be removed,
348

we want the head field to point
349

to whatever Mike's next field is pointing to
350

because right now that's the second item in the list
351

and that's going to become the front of the list
352

when Mike is removed, so that's all we're doing here.
353

Of course we have to decrement the size
354

because now we'll have one less item
355

and finally we return the removedNode.
356

Now, if we wanted to be really diligent,
357

we could say removedNode.setNext null
358

and that would completely remove Mike
359

or whoever we're moving from the list
360

and that's gonna be an isolated node again
361

but we don't really have to do that
362

because the fact that the next field is still set
363

to a node in the list doesn't mean
364

that we can reach the node we're removing
365

because the head field now points
366

to the node after the node we're removing
367

but we could do that just to be really clean
368

and make sure that we're cleaning up all of the references.
369

So, let's go to the main method now
370

and we'll remove the item at the front of the list.
371

So, after we've added our four employees
372

and printed them, we'll say list.removeFromFront
373

and let's print the size again,
374

System.out.print line list.getSize
375

just to make sure we're decrementing the size correctly
376

and then we'll print our list again.
377

And so, let's run.
378

Here's our list after we've add four employees
379

and we'll see that Mike
380

is the first item on the list
381

and then after we've called removeFromFront,
382

our size goes down to three
383

and we'll see that Mary
384

is now the first employee on the list.
385

And if we go to the end, we'll see that our list
386

is one employee shorter.
387

So, once again, whether to use a linked list,
388

an array or a list will depend
389

on what your application wants to do.
390

If it wants to do a bunch of random accesses,
391

then a linked list would be a bad choice
392

'cause you're always gonna have to be traversing the list
393

to get to whatever you want to access
394

but if you want to load a bunch of data
395

into the list and you're always gonna be most interested
396

in whatever's at the front of the linked list,
397

then that could be a really good choice,
398

a linked list could be a good choice
399

for data structure depending
400

on what else your application
401

is going to wanna do with the data.
402

So, this is a simple implementation
403

of a singly linked list
404

just to give you an idea of what would be going on
405

under the covers in a linked list implementation.
406

In the next video, we'll take a look
407

at doubly linked lists.
408

I'll see you there.