1
00:00:00,095 --> 00:00:04,688
For the search operation we're going to
define a method that takes a value to

2
00:00:04,688 --> 00:00:08,420
search for and returns either
the node containing the value,

3
00:00:08,420 --> 00:00:10,951
if the value is found or none if it isn't.

4
00:00:10,951 --> 00:00:17,581
So right after, actually you know what
we'll make sure repr is the last function,

5
00:00:17,581 --> 00:00:21,949
or last method in our class,
so we'll add it above it.

6
00:00:21,949 --> 00:00:24,519
So here we'll say def search self and
then key.

7
00:00:26,090 --> 00:00:26,890
In the last video,

8
00:00:26,890 --> 00:00:31,120
we implemented the repr method to provide
a string representation of the list.

9
00:00:31,120 --> 00:00:36,030
So we're going to use similar logic
here to implement the search function.

10
00:00:36,030 --> 00:00:42,360
We'll start by setting a local variable
current to point to the head of the list.

11
00:00:42,360 --> 00:00:47,719
While the value assigned to current is
a valid node, that is, it isn't none,

12
00:00:47,719 --> 00:00:53,182
we'll check if the data on that node
matches the key that we're searching for.

13
00:00:53,182 --> 00:00:58,191
So while current we'll say if current.data

14
00:00:58,191 --> 00:01:02,551
is the key then we'll return current.

15
00:01:02,551 --> 00:01:06,774
If it does match, we'll go ahead and
return it like we've done here.

16
00:01:06,774 --> 00:01:11,386
But if it doesn't, we'll assign the next
node in the list to current and

17
00:01:11,386 --> 00:01:12,303
check again.

18
00:01:12,303 --> 00:01:15,305
So we'll say, else,

19
00:01:15,305 --> 00:01:20,048
current = current.next_node.

20
00:01:20,048 --> 00:01:23,644
Once we hit the tail node and
haven't found the key,

21
00:01:23,644 --> 00:01:27,094
current gets set to none and
the while loop exits.

22
00:01:27,094 --> 00:01:31,653
At this point we know the list
doesn't contain the key so

23
00:01:31,653 --> 00:01:33,886
we can return none, okay?

24
00:01:33,886 --> 00:01:36,599
That completes the body of our method.

25
00:01:36,599 --> 00:01:39,291
Let's add a doc string to document this.

26
00:01:39,291 --> 00:01:44,514
So up at the top, we'll say, search for

27
00:01:44,514 --> 00:01:51,443
the first node containing
data that matches the key.

28
00:01:51,443 --> 00:01:55,745
Now this is important because if our
linked list contains more than one node

29
00:01:55,745 --> 00:01:58,080
with the same value it doesn't matter.

30
00:01:58,080 --> 00:02:01,533
We're going to return the first
one with this implementation.

31
00:02:01,533 --> 00:02:09,240
We'll also say here that it returns
the node or 'None' if not found.

32
00:02:09,240 --> 00:02:13,880
In the worst case scenario, we'll need to
check every single node in the list before

33
00:02:13,880 --> 00:02:19,200
we find the key or fail, and as a result
this operation runs in linear time.

34
00:02:19,200 --> 00:02:24,170
So I'll say, takes 0(n) or linear time.

35
00:02:26,370 --> 00:02:30,080
So far we haven't seen anything
that indicates this data structure

36
00:02:30,080 --> 00:02:35,170
has any advantage over an array or
a python list, but we knew that.

37
00:02:35,170 --> 00:02:39,030
I mentioned, the strength of
linked lists comes in inserts and

38
00:02:39,030 --> 00:02:40,908
deletes at specific positions.

39
00:02:40,908 --> 00:02:43,090
We'll check that out in the next video,
but

40
00:02:43,090 --> 00:02:48,620
as always, before we end this one,
let's make sure everything works.

41
00:02:48,620 --> 00:02:54,622
So we'll load the contents
of the file again.

42
00:02:54,622 --> 00:02:57,606
l = LinkedList().

43
00:02:57,606 --> 00:03:04,665
And then we'll say l.add(10),
1.add 20, 2, doesn't matter.

44
00:03:04,665 --> 00:03:08,954
l.add(45), and one more.

45
00:03:08,954 --> 00:03:10,950
l.add(15).

46
00:03:10,950 --> 00:03:15,700
Now, we can say l.search, and we need
to give it a value, so we'll say 45.

47
00:03:15,700 --> 00:03:22,892
And this returns a node or none, so
we'll say n =, and then we'll hit Enter.

48
00:03:22,892 --> 00:03:26,116
If this works, n should be a node.

49
00:03:26,116 --> 00:03:30,842
Okay, weirdly, n does not work here,
at least, it says it's not a node,

50
00:03:30,842 --> 00:03:34,086
which means I made a mistake
in typing out our code.

51
00:03:34,086 --> 00:03:36,616
And looking at it immediately,
it's fairly obvious.

52
00:03:36,616 --> 00:03:41,070
So this return None needs to
be outside of the while loop.

53
00:03:41,070 --> 00:03:42,645
Okay, so I'm gonna hit save now.

54
00:03:42,645 --> 00:03:45,248
So make sure it's on
the same indentation here,

55
00:03:45,248 --> 00:03:47,542
which means it's outside the while loop.

56
00:03:47,542 --> 00:03:49,662
And then we'll run through this again.

57
00:03:51,574 --> 00:03:56,826
Okay, so l = linked list, l.add(10),

58
00:03:56,826 --> 00:04:03,705
l.add(2), l.add 45 and
what was the last one we did?

59
00:04:03,705 --> 00:04:06,022
I believe it was 15.

60
00:04:06,022 --> 00:04:09,107
And now we should be able to say l.search.

61
00:04:09,107 --> 00:04:12,293
Remember we're assigning this to a node,
to a variable.

62
00:04:12,293 --> 00:04:17,229
So l.search(45).

63
00:04:17,229 --> 00:04:18,294
And there you go.

64
00:04:18,294 --> 00:04:21,230
We get that node back and we can hit l.

65
00:04:21,230 --> 00:04:24,060
And we'll see
a representation of our list.

66
00:04:24,060 --> 00:04:28,180
Okay, so again, in the next video,
inserts and deletes at specific positions.