Linked List

We are moving forward in learning data structures.

While learning Python bases, you met list structure.

Elements in this structure are not connected.

Imagine the line of people who stay next to each other. They are in one line, but they aren’t connected.

The linked list is a data structure where every person in this line exists and shows that they also have a person next to them.

Every element in the linked list is called a node. Each node stores data and the address of the next node (a finger:)).

The first person in this line has to have an address too. This element is called the Head.

The last person in the line shows some node address, but there is no node here, so the last element of the linked list is NULL.

Do you recall we were learning types of the queue?

There are similar types of the linked list:

• Singly linked list (we are going to implement this type);
• Doubly linked list (can be composed in both directions);
• Circular linked list (the last element is linked to the first element).

We can perform some operations with the linked list:

• Search: when we want to search for an element in the linked list;
• Insertion: when we want to add a new element to the linked list;
• Deletion: when we want to find an element and then delete it from the linked list;
• Sorting: when we want to order our elements in ascending or descending order.

In the following chapters, we will implement the search, insertion, and deletion operations, but now it is time to implement the linked list!