A Tale of Two Pointers: How Linked Lists Work 🖇️

Release .4

What is a Linked list 🤨?
A linked list is a data structure that consists of a collection of nodes which together represent a sequence. Each node contains data and a reference (or link) to the next node in the sequence.
The first node in the sequence is called the head and the last node is called the tail 🚃.

Example:
The history of visited web pages in a web browser can be represented as a linked list. Each node in the linked list represents a web page, and the next pointer points to the next web page in the history 🌐.

Arrays and linked lists are both data structures that can be used to store data. However, they have different characteristics and are suited for different tasks ⛷️.

Arrays:

• Arrays store data in contiguous memory locations. This means that the elements of an array are stored next to each other in memory.
• Accessing an element in an array is very fast because the element's address can be calculated directly from its index.
• Arrays have a fixed size. This means that the size of an array cannot be changed after it is created.
• Arrays are good for storing data that will be accessed frequently.

Linked lists:

• Linked lists store data in non-contiguous memory locations. This means that the elements of a linked list are not stored next to each other in memory.
• Accessing an element in a linked list is slower than accessing an element in an array because the element's address cannot be calculated directly from its index.
• Linked lists can grow and shrink dynamically. This means that the size of a linked list can be changed at runtime.
• Linked lists are good for storing data that will be accessed infrequently or that needs to be inserted or deleted frequently.

Structure of a Linked List:
Every element in a linked list is called a node and consists of two parts, the data part, and the pointer part. The data part stores the value, while the pointer part stores the pointer pointing to the address of the next node.

head -> node1 -> node2 -> node3 -> node4 -> tail

In this example, head is the first node in the linked list and tail is the last node. Each node contains a piece of data and a reference to the next node in the list.

Both of these structures (arrays and linked lists) are linear data structures.

Operations:

• Traversal: To traverse a linked list, we can use a loop to iterate through each node in the list.
• Insertion: To insert a new node into a linked list, we can create a new node and then set the next pointer of the new node to the next pointer of the current node.
• Deletion: To delete a node from a linked list, we can first find the node to be deleted. Then, we can set the next pointer of the previous node to the next pointer of the node to be deleted.
• Search: To search for a node in a linked list, we can use a loop to iterate through each node in the list and compare the value of the node to the value we are searching for.
• Merging: This operation merges two linked lists into one linked list.
• Splitting: This operation splits a linked list into two linked lists.

Circular Linked list 🛞:
A circular linked list is a linked list where the last element points to the first element (head) hence forming a circular chain. There is no node pointing to the NULL, since a circle has no end. In circular linked lists, we have a head pointer but no starting of this list.

Here is an example of a circular linked list:

head -> node1 -> node2 -> node3 -> node4 -> head

In this example, head is the first node in the circular linked list and node4 is the last node. The next pointer of node4 points back to head, which completes the circle.

Operations:

• Traversal: To traverse a circular linked list, we can use a loop to iterate through the nodes in the list until we reach the beginning of the list again.
• Insertion: To traverse a circular linked list, we can use a loop to iterate through the nodes in the list until we reach the beginning of the list again.
• Deletion: To delete a node from a circular linked list, we can first find the node to be deleted. Then, we can set the next pointer of the previous node to the next pointer of the node to be deleted.
• Search: To search for a node in a circular linked list, we can use a loop to iterate through the nodes in the list and compare the value of the node to the value we are searching for.
• Merging: This operation merges two circular linked lists into one circular linked list.
• Splitting: This operation splits a circular linked list into two circular linked lists.

Doubly Linked list ⏸️:
A doubly linked list is a data structure that consists of a collection of nodes which together represent a sequence.
Each node contains data and two references (or links) to the next and previous nodes in the sequence.
The first node in the sequence is called the head and the last node is called the tail.

Here is an example of a doubly linked list:

head -> node1 -> node2 -> node3 -> node4 -> tail

In this example, head is the first node in the doubly linked list and tail is the last node. Each node contains a piece of data and two references to the next and previous nodes in the list.

The two references in a doubly linked list allow for efficient traversal in both directions, forward and backward. This makes doubly linked lists more versatile than singly linked lists, which can only be traversed in one direction.

The logic behind all the linked lists are same everywhere, but the implementation varies depending on the programming language.

So, to summarize, we have learned about the different types of linked lists in this post. Be sure to check out the code and implementation of each one in your preferred programming language to solidify your understanding.

& Happy Independence Day to all my Indian comrades 💡

I hope this post has been informative and helpful. If you have any questions, please feel free to leave a comment below.

Happy Coding 👍🏻!
Thank You