Linked list is our first data structure that is different from arrays.

Linked lists are fastest than arrays when we're talking about inserting and/or removing an element. But slower on accessing a specific element. To access nth element of a linked list, time complexity is O(n). For comparison, on arrays the time complexity is O(1). Also, on linked lists, our size is variable. It grows at runtime, as more nodes are added to it. So, memory is allocated at runtime, as and when a new node is added. It's also known as Dynamic Memory Allocation.

Let's split our linked list into 3 different groups.

Linear linked list

On linear linked lists, each element (called node or data node) is connected to the next data node, hence forming a chain.

As you can see in our example image, each node/element has, necessarily, two properties:

• The data property: responsible for storing our element's data
• The next property: responsible for the link with the next element
  • In languages like C and C++, we need to store the next element memory address, using a pointer. In more modern languages, we can store the next element by reference (in a practical way, the outcome is the same, changing only the syntax).

The last element of a linked list is going to always have an empty next property. This is how we know when we're at the end of the linked list (and there's nothing after it).

In the same way, our first node is going to be stored in a HEAD variable (because we call the first node "head", duh). This is how we know where to start when dealing with the linked list.

The reason of being so fast to add or remove an element from a linked list, is because we only need to generate a new node and, then, change the next property value in both our new node and the node in the position that we want to add our new element.

If we would like to insert the node in the beginning of our linked list, then we only need to create our new node and set the value of the next property of it pointing to our first node. In the same way, if we want to add a new node in the end of our linked list, then we only need to create a new node with it's next property empty/null and, then, set the value of the next property of our linked list last node to point to our recently created node.

This is why we don't have a specific size limitation on linked lists (beside our computer's memory). And, also, this is why is so fast to add and/or remove a node from it.

This logic of playing around with the next property is also used for removing and reordering our linked list.

Doubly Linked List

Doubly linked list is a type of linked list in which each node has two links. The first link points to the next node in the list. The second link points to the previous node in the list.

Similarly to the linear linked list, the last node is going to have the next property value equals null. And, for our doubly linked list, the first node is going to have the previous property value equals null.