Original subtitles

1 1

(upbeat music) 2

2

All right so in the last couple of videos 3

3

we looked at singly linked lists. 4

4

And now we're going to look at a double linked list, 5

5

or a doubly linked list. 6

6

With a doubly linked list we have nodes. 7

7

We have a head, we have a tail, 8

8

and each node in the list points to the next item 9

9

in the list and to the previous item in the list. 10

10

And so this time we have two reference fields, 11

11

this would be the next field, 12

12

and this would be the previous field. 13

13

And as you can see, for the first item in the list 14

14

the previous field will point to null 15

15

and the last item in the list, 16

16

the next field, will point to null. 17

17

Just like it does with singly linked lists. 18

18

And so as I said, this time we have references 19

19

to the head and the tail. 20

20

So in this list, Jane would be the head node 21

21

and Mike would be the tail node. 22

22

And so we can traverse the list from front to back. 23

23

From front to tail. 24

24

Or from tail to head. 25

25

And this time if we want to insert or remove a node 26

26

from the end of the list we can do it in constant time 27

27

because we have a pointer, or a reference, 28

28

to the tail of the list. 29

29

And so the advantage of using a doubly linked list 30

30

is you can work with the node at the front of the list 31

31

or the node at the end of the list in constant time. 32

32

But if you want to work with nodes in the middle of the list 33

33

you're gonna have the same problem 34

34

that a singly linked list had. 35

35

You're gonna have to traverse 36

36

from the head or from the tail, 37

37

find the node you wanna work with, 38

38

and in the worst case, that could be a linear operation. 39

39

So let's look at inserting and deleting nodes 40

40

into a doubly linked list. 41

41

So we have a little more work to do now 42

42

because we have two references that we have to manage, 43

43

the next and the previous. 44

44

And so if we wanted to insert Bill at the head 45

45

we'd start out the same way that we did 46

46

for inserting a node in a singly linked list. 47

47

We're gonna create a new node 48

48

for the new information. 49

49

And now we need to set Bill's next and previous fields. 50

50

So his next field is going to be whatever 51

51

is currently being pointed to by head. 52

52

So this is the same as when we did singly linked lists. 53

53

And his previous field is going to point to 54

54

whatever Jane's previous field is, 55

55

because if, if we're inserting Bill in front of Jane, 56

56

which is what we're doing, then Jane's previous field 57

57

is now going to become Bill. 58

58

And Bill's previous field will become whatever 59

59

Jane was pointing to. 60

60

Now if we're always inserting at the head, 61

61

that would mean that Bill's previous field 62

62

is going to point to null. 63

63

And now we have to fix Jane's previous field 64

64

because Bill is being inserted in front of her. 65

65

And so we want her previous field to now point to Bill. 66

66

And then we're going to assign the head field to Bill 67

67

because Bill becomes the new node 68

68

that's at the front of the list. 69

69

And so essentially when we insert a node 70

70

it's all about setting the references of the node 71

71

we're inserting and also updating the previous field 72

72

of the current head node. 73

73

And so after we've done all of that 74

74

this is what the list will look like. 75

75

So we didn't have to change Jane's next field 76

76

because when we're inserting in front of the list 77

77

what comes after Jane isn't going to change. 78

78

We had to update the previous field 79

79

because the previous field would have been pointing to null 80

80

but now it's going to point to the new node. 81

81

Because this previous field used to point here. 82

82

We're dropping a node in front of it. 83

83

And so we need to update the previous field. 84

84

And so we need to update Bill's previous field 85

85

to point to whatever Jane's previous field was pointing to. 86

86

And then on the final step we just set the head to Bill. 87

87

We go through the same steps if we were to insert 88

88

Bill somewhere else. 89

89

In that case we'd have more references to update. 90

90

But we'd go through a bunch of similar steps. 91

91

We basically would have to set Bill's previous and next 92

92

and then we'd have to update the next field 93

93

on the node in front and the previous field 94

94

of the node that comes after the one we inserted. 95

95

But as I said, when you're working with linked lists 96

96

you mainly wanna be focusing on working with 97

97

items that are at the front of the list, 98

98

or in the case of doubly linked lists 99

99

at the tail of the list. 100

100

If you start playing around with items in the middle 101

101

you're gonna lose the advantage of a linked list, 102

102

which is that inserting and deleting items from the front, 103

103

and in the case of a doubly linked list from the end, 104

104

you can do that in constant time. 105

105

Once you start playing with other nodes 106

106

you're getting up into potentially linear time. 107

107

Okay, so that's inserting a node at the head. 108

108

So let's go back to pour original list 109

109

just to remind ourselves of what it looked like. 110

110

So we're back to before we inserted Bill. 111

111

Now we're going to insert at the tail. 112

112

So once again, if we want to insert Bill at the tail 113

113

we'll create a new node called Bill. 114

114

And we want to assign the tail's next field 115

115

to Bill's next field. 116

116

Because if we go back to the previous slide, 117

117

if we're gonna drop Bill in here, 118

118

then whatever this guy is currently pointing to is next, 119

119

we're gonna want Bill to point to as next. 120

120

And so we're gonna assign the current tail's next field 121

121

to Bill's next field. 122

122

We're going to assign whatever, the current tail 123

123

to Bill's previous field because Mike is currently the tail. 124

124

And so if we put Bill in here we're gonna want 125

125

Bill's previous field to point to Mike. 126

126

So we want to point the previous field 127

127

to the current tail. 128

128

And then we're gonna assign, want to assign the tail's 129

129

next field to Bill. 130

130

And so Mike is the current tail. 131

131

And after the insertion, his next field, 132

132

we want him to point to Bill. 133

133

And finally we're gonna assign the tail to Bill. 134

134

And we can do that in constant time complexity. 135

135

It doesn't matter how many items are in the list. 136

136

You're gonna go through the same number of steps 137

137

to insert a new item at the tail. 138

138

And so after the insertion this is the situation we'll have. 139

139

So Mike's next field has been updated to Bill. 140

140

Bill's previous field has been set to Mike. 141

141

And his next field has been set to null. 142

142

Which is what Mike's next field used to be. 143

143

And the tail has now been set to Bill. 144

144

So let's say we want to delete from the head of the list. 145

145

So we wanna delete Jane. 146

146

Well let's look first at what we'd have to do. 147

147

Well we're gonna assign Jane to a remove node. 148

148

And then we wanna assign John's previous field 149

149

to whatever Jane's previous field is pointing at 150

150

because we're removing her. 151

151

So we wanna take that reference and go here. 152

152

And then we just need to move the head reference to John. 153

153

And that effectively moves, removes Jane from the list. 154

154

So we're gonna assign Jane to remove node. 155

155

We're gonna assign John's previous field 156

156

to Jane's previous field. 157

157

We're gonna assign head to whatever is at Jane's next field. 158

158

Because Jane's next field is pointing to John 159

159

so we're gonna assign John to head. 160

160

And then we're gonna return, remove node from the method. 161

161

And if we wanted to we could clean up Jane's next field 162

162

by setting it to null. 163

163

We don't have to but we could. 164

164

And once again, that'll be constant time complexity. 165

165

And so once we've gone through that, Jane will be gone. 166

166

And John will be the new head of the list. 167

167

So let's put Jane back in. 168

168

And let's look at removing the tail instead. 169

169

So this time we're gonna remove Bill. 170

170

And so how would we do that? 171

171

Well we're gonna wanna take Mike's next field 172

172

and point it to null. 173

173

And we're gonna wanna move the tail to Mike's. 174

174

So the tail will be moved 175

175

to the current tail's previous node. 176

176

And so we'll assign Bill to remove node. 177

177

We'll assign Mike's next field to Bill's next field. 178

178

We'll assign the tail to Bill's previous field, 179

179

which is Mike. 180

180

And then we'll return remove node from the method. 181

181

And once again we can do this in constant time. 182

182

It doesn't matter how many items are in the list. 183

183

If we wanna delete an item from the tail 184

184

we can do it using the same number of steps. 185

185

And so after the deletion, we'll have this situation 186

186

where Mike is now the tail. 187

187

And Bill is gone. 188

188

So in general to insert a node A 189

189

between nodes B and C, we want to plop A 190

190

between B and C. 191

191

And we're gonna assign A's next field to B's next field 192

192

because B's next field will be pointing to C. 193

193

And we're gonna put A between them. 194

194

So we want A's next field to point to C. 195

195

We're gonna assign A's previous field to C's previous field 196

196

because C's previous field will be B. 197

197

And we want A, we're gonna drop A in between them, 198

198

so we're gonna want A's previous field to be B. 199

199

And then we assign B's next field to A. 200

200

And C's previous field to A. 201

201

Now to do those four steps is constant time but, 202

202

unless we're doing this 203

203

at the beginning or the end of the list 204

204

we have to find nodes B and C first. 205

205

And we're gonna have to traverse the list to do that. 206

206

And so, the worst case for this is actually linear time. 207

207

O to the n. 208

208

Now to remove a node A from between B and C, 209

209

so this time we have nodes B followed by A followed by C, 210

210

we assign A to remove node. 211

211

We want C's previous field to now point to B 212

212

because we're removing A. 213

213

So we'll assign C's previous field to A's previous field. 214

214

Because A's previous field is pointing to B. 215

215

We want B's next field to point to C. 216

216

So we'll assign B's next field with whatever A's next field 217

217

is pointing at because A's next field 218

218

is currently pointing to C because it's in between them. 219

219

And then we just return A from the method. 220

220

Once again, these steps are constant time. 221

221

But, we have to find A first in the list. 222

222

So unless A is at the head or the tail, 223

223

we're gonna have to find it. 224

224

And so this, the worst case for this 225

225

would actually be linear time. 226

226

And that's it for looking at how doubly linked lists work. 227

227

Once again we're gonna do a simple implementation 228

228

of a doubly linked list. 229

229

We're gonna update our singly linked list implementation 230

230

to turn it into a doubly linked list. 231

231

So let's go ahead and do that. 232

232

I'll see you in the next video.