Original subtitles

1 1

(futuristic electronic music) 2

2

(keyboard keys clack) 3

3

All right, so this is a data structures 4

4

and algorithms for Java course, 5

5

and if you wanna use a linked list in Java, 6

6

you're probably going to use 7

7

the LinkedList class in the JDK. 8

8

So here we are at the Java doc for the LinkedList class, 9

9

and the first thing we'll notice 10

10

is it says this is a doubly linked list implementation, 11

11

and so, if you use this class, 12

12

you're actually getting a doubly linked list, 13

13

not a singly linked list. 14

14

We'll also notice that it implements the List interface 15

15

and the Deque interface. 16

16

We're gonna look at queues later. 17

17

Now because it implements the List interface, 18

18

all the methods in the List interface 19

19

are in the LinkedList class, so, 20

20

we have methods like add, 21

21

indexOf, 22

22

size, toArray, 23

23

remove. 24

24

Now, this class uses generics, 25

25

so you can use this LinkedList class 26

26

with any type of object, 27

27

including our Employee object. 28

28

Now what about the Node class? 29

29

Well, the LinkedList class has its own implementation 30

30

of the Node class, 31

31

so we don't have to write a Node class ourselves. 32

32

Now it's important to note 33

33

that this class is not synchronised. 34

34

This implementation is not synchronised, 35

35

so if you wanna use a LinkedList instance 36

36

from multiple threads, 37

37

you'll have to synchronise the calls 38

38

to any of the LinkedList methods. 39

39

You'll have to do that yourself. 40

40

All right, let's go over to the IDE. 41

41

So I've created a new project. 42

42

I've put the code into package 43

43

academy.learnprogramming.jdklinkedlists, 44

44

and I've created the usual Employee instances. 45

45

To do that, I've obviously copied over the Employee class 46

46

that we've been using, 47

47

and it's the exact same class. 48

48

I just copied and pasted the code over from 49

49

one of the other projects. 50

50

So let's create a linked list for our Employee 51

51

so we'll say LinkedList, 52

52

Employee, 53

53

list equals 54

54

new LinkedList, 55

55

and it's gonna ask me to raise my language level 56

56

'cause the default language level is 1.6, 57

57

and I believe this needs 1.7. 58

58

So I want that light bulb to come up, 59

59

not that one, the red one. 60

60

There it is, and I'll just say Set language level to seven. 61

61

Okay, so let's do what we did before. 62

62

We'll add a bunch of employees to the front of the list, 63

63

so I'll say list.addFirst. 64

64

So this is the method you call 65

65

if you want to add an item to the front of the LinkedList, 66

66

and we'll add janeJones. 67

67

list.addFirst 68

68

johnDoe. 69

69

list.addFirst 70

70

marySmith, 71

71

and list.addFirst 72

72

mikeWilson. 73

73

The LinkedList class doesn't have a handy printList method, 74

74

but it does have an iterator, 75

75

so that's how we're going to print what's in the list. 76

76

So we'll say Iterator, 77

77

and I'll call it iter, equals, 78

78

and you'll notice there's multiple choices here for Iterator 79

79

so I'm gonna press Alt + Enter, 80

80

and I want the java.util iterator, 81

81

equals list.iterator, 82

82

and then, while iter.hasNext. 83

83

We'll just print out 84

84

iter.next. 85

85

We could also use a for loop to print out the list. 86

86

I'll put that as a comment, so we could say for 87

87

Employee employee 88

88

in the list, 89

89

System.out.println employee, 90

90

so we could do that, 91

91

and I'll put this in a comment just so that you can see. 92

92

So both of these will print the list. 93

93

Now obviously, it's not gonna have 94

94

the nice arrow that we had. 95

95

We're gonna be printing each employee on a single line. 96

96

Well I suppose I could add that in myself, so, 97

97

I'll say System.out.print, 98

98

HEAD. 99

99

Pretty much do the same thing we did before, 100

100

and then, I'll change that to print, 101

101

and then, I'll say System.out.print, 102

102

and we'll do the double arrow 103

103

'cause this is a doubly linked list, 104

104

and then, at the very end, we'll print null. 105

105

So now, we're doing the same thing 106

106

that we did in our printList 107

107

except we're an iterator to print out the items. 108

108

So let's run, 109

109

and we'll see that we have the same thing we had before. 110

110

We've got our head and then we've got Mike Wilson, 111

111

Mary Smith, John Doe, and Jane Jones. 112

112

So let's say we wanna add Bill End to the end of the list. 113

113

So right now, we've got addFirst, 114

114

and so, let me create a Bill End employee. 115

115

I'll add him up here, so Employee 116

116

billEnd equals new Employee Bill, 117

117

End, 118

118

and I think his ID 119

119

that we gave him in the last video was 78. 120

120

Now we can't use addFirst 121

121

because addFirst adds to the front of the list, 122

122

and so, instead, we use the add method. 123

123

So for LinkedList, the add methods adds 124

124

an item to the end of the list. 125

125

It adds it at the tail, 126

126

and so, we wanna add billEnd at the tail, 127

127

and then, copy this code. 128

128

I suppose I could put this in a method, 129

129

but we'll just go with this for now. 130

130

Don't need to declare the iterator again, and let's run, 131

131

and so, Mike's still at the front of the list. 132

132

Everybody's in the same position 133

133

except at the end, we have Bill End. 134

134

So this is important to remember 135

135

when you're working with the JDK LinkedList class. 136

136

The add method, the implementation of the add method 137

137

from the List interface, 138

138

adds the item to the end of the linked list. 139

139

If you want an item added to the front, 140

140

you have to use the addFirst method. 141

141

So it's important to read the description 142

142

of the method you wanna use 143

143

to make sure it's adding the item where you want it added. 144

144

Now, we could also use addLast. 145

145

So if I change this addLast and run, 146

146

we'll get the same thing. 147

147

So we'll see that Bill's been added to the end. 148

148

So you can use add, or if you wanna be really clear 149

149

that you're adding the item to the end of the list, 150

150

you can use addLast. 151

151

Okay, and I'll close this down again, 152

152

and let's go look at the code for LinkedList. 153

153

So I'm gonna right-click and say go to the Declaration, 154

154

and we'll see that it is using a Node class, 155

155

first and last. 156

156

So first is basically the head and last is the tail. 157

157

It's got a size and so this looks familiar, doesn't it? 158

158

Now what's the underlying data structure 159

159

being used for the LinkedList? 160

160

Remember when we looked at ArrayList and Vector, 161

161

we discovered that it was an array. 162

162

Well, we'll see that the class 163

163

extends AbstractSequentialList, 164

164

and if we take a look at that, 165

165

we'll see that this kind of provides 166

166

a skeletal implementation of the List interface 167

167

to reduce the amount of work required 168

168

for classes that wanna implement List. 169

169

So basically, if you wanna implement the List interface 170

170

and you don't wanna start from scratch 171

171

and have to implement every single method, 172

172

instead of just implementing List, 173

173

you can extend this class if you want a sequential list, 174

174

and you get a bunch of stuff for free, 175

175

and then, you can just override what you wanna override, 176

176

and that's all fine and dandy, 177

177

but how is a linked list being stored? 178

178

Well, you can see how it's being stored. 179

179

It's exactly similar to the way that we implemented our, 180

180

our simple, single, singly linked list 181

181

and doubly linked list. 182

182

The linked list itself is the data structure, 183

183

so it's not being backed by anything. 184

184

The linked list is just containing 185

185

references to a head and a tail, 186

186

and this Node class, let's have a look at it, 187

187

has the item which is, 188

188

in our case, would be the employee, 189

189

and then, it's got next and previous. 190

190

So the linked list itself is the data structure. 191

191

There's nothing that's backing it, 192

192

and since we went through 193

193

a simple implementation of a linked list, 194

194

this should look familiar, 195

195

and that's why we went through those simple implementations, 196

196

so you have some idea of what's going on 197

197

underneath the covers 198

198

when you're working with a linked list. 199

199

Okay, so let's go back to the main method. 200

200

So we've added employees. 201

201

How do we remove them? 202

202

Well, if you guessed that there are removeFirst 203

203

and removeLast methods, you're right. 204

204

So let's go ahead here. 205

205

I'm just gonna copy this whole thing. 206

206

Instead of adding last, let's remove the first, 207

207

and we don't have to pass anything 208

208

'cause we're always gonna remove the first item here, 209

209

and let's run, 210

210

and we'll see that Mike is gone. 211

211

Because we called removeFirst, 212

212

Mary is now the first item in the list, 213

213

and if we go to the end, Bill's still there, 214

214

but if I 215

215

copy this code again 216

216

and say list.removeLast, 217

217

Bill should now be taken from the list, 218

218

and let's check it out. 219

219

So Mary's still first on the list, 220

220

but we go to the end, we'll see that Bill is now gone, 221

221

and so, that's how you remove items from the front 222

222

and the end of the list. 223

223

You have to be careful, though, 224

224

because, let me just close this down, 225

225

when we were talking about add, 226

226

I said if you just call the add method, 227

227

it will add an item to the end of the list. 228

228

Well, in the remove case, if you just call remove like this, 229

229

it will remove the first item on the list, 230

230

so as I said, make sure that you always, 231

231

let me just undo that, 232

232

make sure that you always read the 233

233

description of the method you're using 234

234

to make sure that it's gonna be operating 235

235

at the end of the list that you want it to be operating at. 236

236

So there are other removal methods. 237

237

For example, you could remove a specific employee. 238

238

Of course, that would mean that 239

239

the method has to search the list for that employee, 240

240

and so, it's gonna be slower operation. 241

241

There are also methods that let you insert an employee 242

242

or a node at a specific point in the list. 243

243

You know, you can say something like 244

244

insert Joan as the sixth employee in the list, 245

245

but again, if you do that, 246

246

those operations are gonna be slower. 247

247

The quickest operations are gonna be those 248

248

that are working at the head or at the tail. 249

249

Anyway, I encourage you to take a look 250

250

at the LinkedList class and see what's available. 251

251

The important point here 252

252

is that if you wanna use a linked list in Java, 253

253

you can use the LinkedList class 254

254

as long as you don't mind the extra memory overhead 255

255

due to the next and previous fields. 256

256

If you're going to need a lot of nodes and memory is tight, 257

257

you might want to consider another type of data structure, 258

258

or if it makes sense, 259

259

you might want to implement a singly linked list, 260

260

but most of the time, memory won't be an issue. 261

261

Now before we leave linked lists, 262

262

I'll just mention that there's another type of linked list 263

263

called a circular linked list, 264

264

and this is a variation on the singly linked list, 265

265

and in this variation, 266

266

the last node in the list doesn't point to null. 267

267

Instead, it loops back, 268

268

and it points to the head of the list, 269

269

and one advantage to this 270

270

is that you can traverse the entire list 271

271

starting at any node. 272

272

So if for some reason, 273

273

that feature is important to your application, 274

274

then a circular linked list might work for you. 275

275

So I just wanted to mention that to you. 276

276

We're not gonna implement it, 277

277

but there is a variation called circular linked list 278

278

where the last node in the list points to the head node. 279

279

Okay, that's all for linked lists. 280

280

I'll see you in the next video.