Original subtitles

1 1

(gentle music) 2

2

(keys clacking) 3

3

In this video, 4

4

we're going to begin our look at linked lists. 5

5

A linked list is a data structure. 6

6

It's a sequential list of objects, 7

7

but this time, arrays aren't involved. 8

8

In a linked list, each item in the list 9

9

is aware of another item in the list, 10

10

because each item in the list 11

11

contains a link to the next item in the list. 12

12

Now this is different from arrays 13

13

and lists that are backed by arrays. 14

14

With an array, each item in the list is completely unaware 15

15

of other items in the array, but items in a linked list 16

16

know which item comes after them, 17

17

and that means that we have to store 18

18

some extra information with each item. 19

19

When we have an array of integers, 20

20

we just have to store the integer value in each position, 21

21

but when it comes to a linked list, 22

22

we have to store the integer value 23

23

and we have to store a reference 24

24

to the next integer in the list. 25

25

So when we get to the implementation, 26

26

I'm going to use the employee class we used 27

27

when we looked at array lists, 28

28

and so on the screen here, I have a linked list, 29

29

and this would be Jane, John, Mary, and Mike. 30

30

And as we can see, this blue block 31

31

would be the employee object, 32

32

and then there'll be a field 33

33

that contains a reference to the next item in the list. 34

34

Each of these items is referred to as a node, 35

35

and the first item in the list is the head of the list, 36

36

and the last item in the list always points to null, 37

37

because nothing comes after it. 38

38

And so what we'll have is a node class 39

39

that contains a field for 40

40

whatever data you're holding in the node. 41

41

In our case, we'll have an employee field. 42

42

And then we'll have a next field, 43

43

and that next field will be of type node, 44

44

because each node points to the node that comes after it. 45

45

Now I'm going to insert a spoiler here. 46

46

In Java, you wouldn't implement a linked list yourself. 47

47

There's a linked list class, but to help us understand 48

48

what a linked list is and what its advantages are, 49

49

we will code a simple implementation. 50

50

So as I said, when it comes to a linked list, 51

51

there will be a head field, 52

52

and the head will point to the first item in the list. 53

53

So if you have a reference to the head, 54

54

you can traverse the entire list. 55

55

You would start at the head 56

56

and then you'd go to head.next, 57

57

and then you'd go to that next field, that next one, 58

58

until you hit null. 59

59

So for a linked list, the only thing you have to store 60

60

is a reference to the head or the first node in the list. 61

61

And from that, you can get to every item in the list. 62

62

So let's talk about what we'd have to do 63

63

to insert an item into this list. 64

64

So let's say we wanted to insert Bill. 65

65

Well, the first thing we're gonna have to do 66

66

is create a new node for Bill. 67

67

So we'd have a box somewhere that has Bill in it. 68

68

When it comes to linked lists, 69

69

you always insert a new element at the front of the list. 70

70

And you can understand why. 71

71

We only ever store a reference to the first element, 72

72

and so if we wanted to insert an item 73

73

anywhere other than the front, 74

74

then we'd have to traverse the list to get there. 75

75

And one of the advantages of using a linked list 76

76

is that if you insert items at the front of the list, 77

77

you can do it in constant time complexity, 78

78

because the steps you have to do 79

79

don't depend on the number of items in the list. 80

80

You're always gonna do the same number of steps. 81

81

So we create a new node for Bill, 82

82

and we're gonna wanna put Bill here, or up here in front. 83

83

Bill is gonna wanna point to Jane. 84

84

So after we've created the new node, 85

85

we'll assign the next field Jane, 86

86

and then we're gonna assign head to Bill, 87

87

because Bill will be the new head of the list, 88

88

and so that's all we have to do to insert a node. 89

89

We create the actual node instance. 90

90

We point the next field at the current head of the list 91

91

because the new node is gonna become the new head, 92

92

and then we point the head field at the new node. 93

93

And that's gonna always be constant time complexity, 94

94

because it doesn't matter. 95

95

You could have three items in the list 96

96

or a million items in the list, 97

97

and you're just gonna do the same number of steps, 98

98

as long as you're inserting at the front of the list. 99

99

And so after the insertion, 100

100

this is what the list would look like. 101

101

Bill's next field points to Jane, 102

102

and the head field now points to Bill 103

103

because he's at the front of the list. 104

104

So how about deleting? 105

105

Now what if we wanted to pull Bill off? 106

106

And once again, we'll want to delete 107

107

from the front of the list. 108

108

Otherwise, we're gonna have to traverse the list 109

109

looking for the node we want to delete. 110

110

Now in the implementation, I'll show you, 111

111

when we do a deletion, we return the node that we deleted. 112

112

So we're first gonna assign Bill to a temporary variable 113

113

called removedNode, and then what do we wanna do? 114

114

Well, all we're gonna do is move the head to Jane, 115

115

because that effectively removes Bill from the list. 116

116

Because for a linked list, the only sort of information 117

117

that we're holding is this head field. 118

118

And so if we break this link to Bill 119

119

and we change heads so it's pointing to Jane, 120

120

Bill has effectively been removed from the list. 121

121

There's no way we can get from head to Bill. 122

122

And then at that point, we would return the removedNode, 123

123

which we previously stored Bill into that field. 124

124

And that's all we have to do to delete a node 125

125

from the front of the list. 126

126

Once again, this will be constant time complexity, 127

127

because it doesn't matter how many items are in the list. 128

128

You're gonna do the same number of steps. 129

129

So after we've deleted Bill, this is the situation. 130

130

We have, Bill will be hanging off here. 131

131

He'll still be pointing to Jane, 132

132

but there's no way for us to reach him 133

133

from the head of the list. 134

134

And if we wanted to do clean out, 135

135

we could set Bill's next field to null if we wanted to. 136

136

And so that's it for sort of the theory for linked lists. 137

137

They're not that complicated. 138

138

They're the second data structure we've looked at, 139

139

the first one being arrays, 140

140

and they differ from arrays in that, 141

141

as long as you're inserting and deleting 142

142

from the front of the list, 143

143

the insertions and deletions are done in constant time, 144

144

and that's because there's no shifting involved. 145

145

And this type of list is called a singly linked list 146

146

because we have one link between every node. 147

147

In a little while, we're going to look at a list 148

148

that's called a doubly linked list. 149

149

But we're starting out with a singly linked list, 150

150

and when you're working with a singly linked list, 151

151

you want to insert and delete items at the front of the list 152

152

because you only have a reference to the head of the list, 153

153

and so if you want to insert and delete items anywhere else, 154

154

you'd have to start at head 155

155

and you've got to traverse the entire list 156

156

to find what you're looking for. 157

157

All right, so now that we know a little bit 158

158

about singly linked lists, let's implement one. 159

159

I'll see you in the next video.