In this lesson we will cover a topic that is considered a sort of compulsory subject - linked lists. That isn't to say it isn't an important topic, it is. Only, it has lost a bit of favor over other data structures.
A linked list is a data structure that is used for organizing and storing a collection of data. A linked list consists of a sequence of nodes.
A node is an object that consists of a value and a pointer. In relation to a linked list, this pointer refers to the next node in the linked list.
How is this helpful, and how is it different than a a regular list? A linked list is the building block for trees, a data structure that has branches in it, something not well supported with regular list. Additionally, it has better performance with frequent insertions and deletions. Lets take a look at what a node looks like.
The very first node in a linked list is often referred to as the head. Similarly, the last node in a linked list is often referred to as the tail. The string formatting is optional, it's sometimes helpful to be able to pretty print a node.
Let's see how we can iterate through a linked list now. We are given a node in the linked list, typically the head. Then we use a while loop to update the reference to the current node until there are no more nodes in the linked list.
In the nearby code, the definition of a node has been imported for you, as well as a main function that initializes nodes and calls the shown function.
Iterate through the nodes until you find one that matches
target. Please return a reference to this node.