001 - Linked List and Doubly Linked List

Linked List

Linked list is a method to store information dynamically and also efficiently. It's dynamic because of the fact that we don't reserve a spot in our memory to store our data, but instead reserve a new spot whenever we want to store an information. The reason we would use this structure instead of a static one like an array list, is because it's simply more efficient to reserve a new spot in the memory when adding a new data rather than reserving spots that might not suffice or use more memory than needed.

Visualization:

source: https://www.geeksforgeeks.org/data-structures/linked-list/

How it works:

A head stores the address of the first node in the list. In the pointed address, there is something that we call a node which consists of the data that is going to be stored first and a "next" value. A "next" holds the address of the next data that is going to be stored in the list. This would mean that every node stores an address to the next node that is added into the list. This would then create a line as shown in the image above with each node pointing at the next node in the list.

This is why we need a head to store the address of the first node. Because of that, we can search through the list from the head and go to the next value of each node to get to the end of the linked list.

When deleting a node, all we have to do is direct the previous node from the one we're trying to delete to point at the next node after it. However, do keep in mind to free the memory after the next value has been adjusted to clear the memory that was used to store the deleted node. Another thing to remember is to change the address value stored in the head to the next node after the first node when deleting a head so that the start of the linked list is not lost.

Double Linked List

Double linked list has the same concept as the normal linked list. It's called a double linked list due to the fact that instead of storing a single "next" value in a node, we store a "next" value and a "prev"(previous) value in a every single node.

"prev" holds the address of the previous node. This allows the list to be searched through in 2 different directions instead of a single one like the normal linked list.

visualization:

source: https://www.geeksforgeeks.org/doubly-linked-list/

Double linked list have a head and a tail. Tail holds the address of the last node in the linked list. This makes it possible to know do an operation from the back of the linked list instead of being forced to always start from the head like the normal linked list.

P.S:

Operations work similarly with normal linked list. However, always keep in mind to also adjust the value of "prev" when doing operations.