Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

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

3

I've created a project, 4

4

I'm putting the code into package 5

5

academy.learnprogramming.linkedlists. 6

6

I've created our four employees that we used 7

7

in the array list video. 8

8

This time I've assigned them to employee variables 9

9

and I've also added the employee class 10

10

and all I did was copied and pasted the class 11

11

over from the array list project, 12

12

so it's a straightforward class. 13

13

We have three fields 14

14

and we just have the usual boilerplate code. 15

15

We have our equals method 16

16

and we have our override toString. 17

17

So, the first class we'll work on 18

18

is the node class and this class 19

19

is going to need two variables, 20

20

one for the employee instance 21

21

and one for the next node in the list 22

22

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

23

every node knows about the next node in the list 24

24

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

25

to the next node in the list 26

26

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

27

if you hadn't already figured that out. 28

28

In Java, by contains a link, 29

29

we mean that it stores the object reference 30

30

of the next node. 31

31

So, let's add a node class, 32

32

so I'll say New, Java Class. 33

33

And I'm going to call this EmployeeNode 34

34

rather than just plain old Node 35

35

because I'm not going to use generics 36

36

to write this linked list, 37

37

I want us to just focus 38

38

on the linked list implementation 39

39

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

40

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

41

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

42

for your application, 43

43

you'd probably make it specific 44

44

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

45

The only reason that you would need to use generics 46

46

is if you're going to write a class 47

47

that's going to be released publicly 48

48

and so that many, many applications 49

49

are going to use it 50

50

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

51

'cause you'd want it to be usable 52

52

with a variety of object types. 53

53

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

54

on the implementation of the linked list 55

55

and so, I'm not gonna use generics 56

56

and so, I'm calling this EmployeeNode 57

57

to make it clear that this node 58

58

will only work with employee instances. 59

59

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

60

we're gonna need one for the employee 61

61

and we're going to need a field 62

62

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

63

So, we'll call that next. 64

64

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

65

so I'll say public EmployeeNode 66

66

and we just need the employee for that. 67

67

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

68

And to make things quick and easy, 69

69

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

70

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

71

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

72

click OK and there we go. 73

73

We have our sets and gets. 74

74

So, the constructor only takes employee 75

75

because when we construct an instance, 76

76

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

77

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

78

the insert method, we create the node first 79

79

and then we figure out which node 80

80

is supposed to be assigned to it next field. 81

81

Now, as we saw in the slides, 82

82

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

83

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

84

then its next field will be set to null 85

85

and so, when we traverse the list, 86

86

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

87

We don't have to set next to null 88

88

in the constructor because that's the default value 89

89

for object fields. 90

90

So, we have a class for the node, 91

91

what about the linked list itself? 92

92

Well, as we saw from the slides, 93

93

all we need to know for the linked list 94

94

is the head node, that's it. 95

95

From there we can traverse the entire list 96

96

because every node in the list contains a link 97

97

to the next node 98

98

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

99

And I'm gonna call this EmployeeLinkedList once again 100

100

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

101

And this just needs one field. 102

102

It needs a field for the head node, 103

103

so private EmployeeNode 104

104

head, that's it. 105

105

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

106

For the best performance, we should add items 107

107

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

108

looking for an insertion point 109

109

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

110

So, we'll say public void addToFront 111

111

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

112

so we'll say EmployeeNode node equals new EmployeeNode 113

113

and we just have to pass the employee 114

114

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

115

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

116

at whatever head it's currently pointing at 117

117

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

118

the current head of the list 119

119

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

120

and so, this new node 121

121

is going to point to the current head 122

122

as we saw in the slides. 123

123

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

124

And then of course the last thing we wanna do 125

125

is set head to the new node. 126

126

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

127

go back to the slides 128

128

but essentially, we're inserting the node right 129

129

at the front of the list, 130

130

so let's say our list contains employee Jane 131

131

and we're inserting John. 132

132

When we come in, the head field 133

133

will be pointing to Jane. 134

134

When we've finished inserting John, 135

135

we want John to be pointing to Jane 136

136

and the head field to be pointing to John. 137

137

So, first we create the new node 138

138

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

139

John's next field to Jane 140

140

because that's currently the one 141

141

being pointed to by head 142

142

and then we set head to John 143

143

and so, we end up with a head field 144

144

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

145

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

146

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

147

and let's create a linked list 148

148

and add some employees to it. 149

149

So, we'll say EmployeeLinkedList 150

150

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

151

and then we'll say list.addToFront 152

152

and we'll add janeJones, 153

153

list.addToFront johnDoe, 154

154

list.addTofront marySmith 155

155

and list.addToFront mikeWilson. 156

156

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

157

so let's go back to our LinkedList class 158

158

and add a printList method. 159

159

So, we'll say public void printList 160

160

and we'll say EmployeeNode current 161

161

equals the head of the list 162

162

'cause we're gonna start at the head 163

163

and I'm gonna print out something here 164

164

that says HEAD 165

165

and then we wanna keep traversing the list 166

166

until current hits null, 167

167

so while current is not equal to null 168

168

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

169

we'll say System.out.print current 170

170

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

171

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

172

And then I'll print an arrow 173

173

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

174

so current equals current.getNext. 175

175

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

176

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

177

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

178

This will work fine 179

179

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

180

is a bunch of object references 181

181

because we've overridden employee, 182

182

we've overridden the toString method and employee 183

183

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

184

So, let's do that now. 185

185

And what I actually wanna print out 186

186

is the employee information when we print a node, 187

187

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

188

so I'll say public String toString 189

189

and I want to return employee.toString 190

190

and so, when we print a node, 191

191

what will actually be printing 192

192

is the result of this toString method. 193

193

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

194

So, we have the head of our list 195

195

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

196

We added Jane first 197

197

but we're constantly adding new employees 198

198

to the front of the list, 199

199

so every time we add a new employee, 200

200

the existing employees gets bumped down the list. 201

201

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

202

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

203

followed by Mary Smith 204

204

followed by John Doe 205

205

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

206

because she's the last node in the list 207

207

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

208

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

209

We could write a method 210

210

that adds employees to the end of the list 211

211

or that looks very specific employee in the list 212

212

and adds an employee after that employee 213

213

or before the employee 214

214

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

215

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

216

and the worst case will always be 217

217

that we have to traverse the entire list. 218

218

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

219

to the end. 220

220

Now, some implementations of linked list 221

221

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

222

the last node in the list 223

223

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

224

it's a variation on them 225

225

but you could do that 226

226

if you thought you were constantly gonna be wanting 227

227

to add items to the end of the list, 228

228

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

229

which is called the tail 230

230

but for a linked list implementation 231

231

that's only keeping reference to the head, 232

232

if you wanted to insert items at the end, 233

233

you'd have to traverse the entire list 234

234

and in either way whether you kept a reference 235

235

to the tail or not, 236

236

if you wanted to insert items 237

237

at a specific point in the list, 238

238

like before or after a specific employee, 239

239

you gonna have to traverse the list looking 240

240

for that employee and so, a singly linked list 241

241

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

242

from the front of the list. 243

243

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

244

can continue to grow 245

245

without having to be resized. 246

246

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

247

if we wanna add more items to it, 248

248

we have to resize the array 249

249

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

250

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

251

by the memory you have. 252

252

Now, talking about memory, 253

253

one disadvantage to a linked list 254

254

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

255

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

256

so is memory's really tight, 257

257

that could be one disadvantage to using a linked list 258

258

even if you will only wanna be adding 259

259

and deleting items from the front 260

260

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

261

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

262

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

263

the platform you're running on, 264

264

what the application's gonna wanna do 265

265

with the data, et cetera. 266

266

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

267

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

268

are in the linked list. 269

269

We could traverse the list 270

270

and count how many items there are 271

271

but another way to do it 272

272

would be to just keep a running count 273

273

of how many nodes are in the list 274

274

and we're gonna do it that way. 275

275

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

276

and we're gonna add a size field, 277

277

so we'll say private int size 278

278

and that will be initialised to zero by default 279

279

when the list is created 280

280

and then whenever we add an employee of course, 281

281

we want to increment the size 282

282

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

283

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

284

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

285

Let's go back to our main method 286

286

and call our getSize method 287

287

after we've added these employees, 288

288

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

289

and we should get four. 290

290

Let's run. 291

291

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

292

So, we could now add an isEmpty method 293

293

that tells us whether the linked list is empty. 294

294

We could just call the getSize method 295

295

and test whether the number of items 296

296

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

297

to test whether a list is empty. 298

298

Can you think about what that way is 299

299

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

300

Can you come up with another way, 301

301

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

302

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

303

'Cause head is null. 304

304

It's not pointing to any nodes. 305

305

So, one way we could write an isEmpty method 306

306

is to say public boolean isEmpty 307

307

and we return head equals null 308

308

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

309

and we call this right at the top, 310

310

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

311

list.isEmpty we should get true here. 312

312

Let's run. 313

313

And sure enough we get true. 314

314

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

315

So, the last method we'll look at 316

316

is how do we remove items from the front? 317

317

And we saw that in the slides. 318

318

Let's go to our LinkedList class 319

319

and let's write the method, 320

320

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

321

that we removed in case the caller wants 322

322

to do anything with it 323

323

and we'll same removeFromFront. 324

324

We don't need to pass anything 325

325

'cause we're always gonna remove the node 326

326

that's right at the front. 327

327

So, the first thing we do 328

328

is we need to test if the list is empty 329

329

because if the list is empty, 330

330

there's nothing to remove, 331

331

so we'll say if isEmpty, 332

332

we'll just return null. 333

333

We don't have anything to do. 334

334

If the list isn't empty, 335

335

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

336

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

337

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

338

is the head node, right? 339

339

So, the node that we're gonna remove 340

340

is pointed to by the head node, 341

341

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

342

So, we'll assign that to removeNode 343

343

and then we want to move the head. 344

344

The head will equal head.getNext. 345

345

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

346

at Mike, head is pointing to Mike 347

347

and we want Mike to be removed, 348

348

we want the head field to point 349

349

to whatever Mike's next field is pointing to 350

350

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

351

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

352

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

353

Of course we have to decrement the size 354

354

because now we'll have one less item 355

355

and finally we return the removedNode. 356

356

Now, if we wanted to be really diligent, 357

357

we could say removedNode.setNext null 358

358

and that would completely remove Mike 359

359

or whoever we're moving from the list 360

360

and that's gonna be an isolated node again 361

361

but we don't really have to do that 362

362

because the fact that the next field is still set 363

363

to a node in the list doesn't mean 364

364

that we can reach the node we're removing 365

365

because the head field now points 366

366

to the node after the node we're removing 367

367

but we could do that just to be really clean 368

368

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

369

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

370

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

371

So, after we've added our four employees 372

372

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

373

and let's print the size again, 374

374

System.out.print line list.getSize 375

375

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

376

and then we'll print our list again. 377

377

And so, let's run. 378

378

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

379

and we'll see that Mike 380

380

is the first item on the list 381

381

and then after we've called removeFromFront, 382

382

our size goes down to three 383

383

and we'll see that Mary 384

384

is now the first employee on the list. 385

385

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

386

is one employee shorter. 387

387

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

388

an array or a list will depend 389

389

on what your application wants to do. 390

390

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

391

then a linked list would be a bad choice 392

392

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

393

to get to whatever you want to access 394

394

but if you want to load a bunch of data 395

395

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

396

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

397

then that could be a really good choice, 398

398

a linked list could be a good choice 399

399

for data structure depending 400

400

on what else your application 401

401

is going to wanna do with the data. 402

402

So, this is a simple implementation 403

403

of a singly linked list 404

404

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

405

under the covers in a linked list implementation. 406

406

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

407

at doubly linked lists. 408

408

I'll see you there.