Original subtitles

1 1

(upbeat music) 2

2

(computer keys clicking) 3

3

Alright, so, let's get cracking on this solution. 4

4

I'm in the Integer Linked Lists class 5

5

that was included with the starter project. 6

6

And here's the insert sorted method. 7

7

So I'll just delete this comment 8

8

and as we can see, it accepts an integer value. 9

9

The first thing we need to do is check 10

10

whether the list is empty, because if the list is empty 11

11

we can obviously just insert the node. 12

12

And the other thing that we're going to check 13

13

is whether the first node in the list 14

14

so if the list isn't empty, we're gonna check whether 15

15

the first node in the list is greater than or equal to 16

16

the value we're inserting because in that case 17

17

we can just insert the new node 18

18

at the head of the list. 19

19

And so, we're gonna say if head equals null 20

20

because that means that the list is empty 21

21

or head.getvalue 22

22

is greater than or equal to the value we want 23

23

to insert in both of these cases 24

24

we wanna just go ahead and just add the new value 25

25

at the front. 26

26

We'll just call our add to front method 27

27

with the value 28

28

and we're done 29

29

and then of course we wanna return. 30

30

And so if the list is empty, we just 31

31

need to add this new value at the front 32

32

cause it'll be in sorted order by default 33

33

or if the head value is greater than or equal to the value 34

34

then we also know that the correct, sorted position 35

35

is right at the front of the list 36

36

cause in the main method, we're always calling insert sorted 37

37

so the assumption that we're making here 38

38

and I'll put this in here assumption 39

39

the list is sorted 40

40

this wouldn't work, this part wouldn't work 41

41

if the list was not sorted. 42

42

Obviously, if the list wasn't sorted 43

43

we wouldn't even call this method 44

44

it wouldn't make a lot of sense. 45

45

Okay, so assuming that we don't have one of those two cases 46

46

so we're not going to be inserting the new value 47

47

at the front of the list we then need 48

48

to find the insertion point. 49

49

So, let's find the insertion point. 50

50

Now, one wrinkle here is that we have a singly linked list. 51

51

So what we're gonna do is we're going 52

52

to traverse the list looking for the first node 53

53

with a value that's greater than or equal 54

54

to the value that we want to insert. 55

55

So let's say we find that node and so let's say 56

56

we have a current node and that node 57

57

is pointing to the node that has a value greater than 58

58

or equal to the value we want to insert. 59

59

Well, it's easy for us to create a new node 60

60

and point that new node's next field to the current node 61

61

but what about the previous node's next field? 62

62

It's currently pointing to the current node 63

63

and we need to change it's next field so that 64

64

it can point to the node with the new value. 65

65

But it's a singly linked list, so 66

66

if we only have a pointer to current, 67

67

there's no way for us to get back 68

68

to the previous node in the list. 69

69

So we're gonna have to have two fields 70

70

one for traversing the list and then another field 71

71

that's going to be one position behind the current field. 72

72

And so, when we finally hit a node that has a value 73

73

greater than or equal to the one we're inserting 74

74

the previous field will be pointing to the node before that. 75

75

We'll say integer node current 76

76

this is the one we're gonna use to traverse the list 77

77

it's gonna equal head.getNext 78

78

we don't have to check head cause we already did that here. 79

79

And so, if we're down here, we know that 80

80

the value in head is less than the value we're inserting. 81

81

So we don't need to check it again. 82

82

But 83

83

we're gonna have a previous and that's 84

84

going to point to head. 85

85

So when we start out, our current node is gonna start 86

86

at the head, at head.getNext, that's the first 87

87

value we're gonna check and our previous node 88

88

is at head, our previous node is always going to be 89

89

one behind the current node. 90

90

And then we're gonna say while current is not equal to null 91

91

and current.getValue 92

92

is less than the value we're inserting 93

93

because the moment we hit a value that's greater than 94

94

or equal we wanna stop. 95

95

While that's true, we're gonna set previous to current 96

96

and we're gonna set current to current.getNext. 97

97

And so by doing this, we're constantly keeping previous 98

98

one back from where current is. 99

99

And so when we drop out of the loop, 100

100

there are two possibilities here. 101

101

Current is null or current isn't null 102

102

meaning that we've hit a node with a value that's 103

103

greater than or equal to the value we want to insert. 104

104

Now, we don't have to handle the special case 105

105

of current being null, because 106

106

we're not going to change anything in current. 107

107

So we don't have to worry that oh, we've hit 108

108

the end of the list. 109

109

If we have hit the end of the list, 110

110

that means that we're going to be inserting 111

111

the new value as the last node in the list 112

112

and that's fine. 113

113

We don't have to worry about oh, if we're at the end 114

114

of the list and we've gotta do something differently. 115

115

We don't have to worry about that, as you'll see. 116

116

We now need to create a node for the new value. 117

117

We need to set that node's next field 118

118

and we need to set the next field 119

119

of whatever previous is pointing to 120

120

to point to the new node. 121

121

And so we'll say integerNode newNode equals 122

122

new IntegerNode for the value 123

123

and then we're gonna say newNode.setnext 124

124

current 125

125

because we're inserting the new node before 126

126

the current node because we wanna insert in sorted order 127

127

and we know that current has a value 128

128

it's the first node we've seen that has a value 129

129

that's greater than or equal to 130

130

the value we wanna insert. 131

131

So we're gonna insert the new node in front of current so 132

132

its next field will point to current 133

133

and now we have to handle the previous' next field. 134

134

Because whatever previous is pointing to 135

135

it now wants to point to the new node. 136

136

So our previous.setNext newNode. 137

137

And finally, we need to update the size. 138

138

And that's it. 139

139

If we were inserting this at the end of the list 140

140

while current will be null, so it's perfectly fine 141

141

for us to say, you know, newNode.setNext null 142

142

it's sort of a redundant operation 143

143

but it's not expensive so we'll just go ahead 144

144

and do that. 145

145

Let's go to our main method and in here 146

146

we've created four integers, one, two, three and four 147

147

and we're gonna insert three, two, one and four 148

148

so let's run. 149

149

And we'll see that we start out by inserting three 150

150

and then we insert two so now we'll have two, three. 151

151

We insert one so we'll have one, two, three 152

152

and finally, we insert four. 153

153

And so we have one, two, three, four 154

154

that's exactly what we want. 155

155

And you'll see that in the last case 156

156

we were inserting at the end of the list. 157

157

And we didn't run into any problems. 158

158

So I think the only tricky part for this one 159

159

which is why I wanted to use a single linked list 160

160

was to realise that 161

161

we need to have two fields now you might have come up 162

162

with a different implementation 163

163

there may be a way to do this without using two fields. 164

164

You may be able to somehow be a couple of nodes back 165

165

and be using .getNext .getNext but I like 166

166

to write really clear code so I've done it this way 167

167

using two fields. 168

168

Alright, that's it for this challenge.