🦕Linked List

What is a Linked List?

💡A linked list is a linear data structure in which the elements are not stored contiguously in memory, but are linked together by pointers. Each element, called a node, consists of two parts: the data and a pointer to the next node in the list. The last node in the list points to a special value called NULL, which indicates the end of the list.

Here are some key characteristics of linked lists:

• Dynamic size: Linked lists can grow or shrink in size as needed, unlike arrays which have a fixed size.

• Efficient insertion and deletion: Elements can be inserted or deleted from any position in a linked list in constant time ($O(1)$), on average. This is because we only need to update the pointers of the surrounding nodes.

• Random access: Accessing a specific element in a linked list requires traversing the list from the beginning until the element is found, which can take linear time ( ) in the worst case.

• Poor cache locality: Linked lists have poor cache locality because the nodes are not stored contiguously in memory. This can lead to slower performance compared to arrays when accessing elements sequentially.

Linked lists are used in a variety of applications, including:

• Implementing stacks and queues

• Implementing undo/redo functionality

• Representing graphs

• Implementing dynamic data structures such as hash tables

Linked List

How Linked List Is Stored In The Memory?

💡Each node in a linked list occupies its own space in memory. The data is stored within the node, and the pointer is stored as a memory address that points to the next node in the list.

Here is a diagram that shows how a linked list is stored in memory:

0x1000	1	0x1004
0x1004	2	0x1008
0x1008	3	None

In this example, we have 3 values (1, 2, 3) that are stored in the linked list. The first value (1) is stored at the address of 0x1000, the second one is stored right next the first one at address of 0x1004, and the last one is stored right next the second one at address of 0x1008.

But look at the pointer, we’ve got the last value (3) is pointing to address of None, this is because in the linked list, the last value is always pointing to a NULL value.

Big O Notation of Linked List Operations

Operation	Time Complexity	Explanation
Insertion (head)	$O(1)$	Adding to the beginning only requires updating a few pointers.
Insertion (tail)	$O(1)$	Same as head insertion, on average (assuming a tail pointer).
Insertion (middle)	$O(n)$	Requiring finding the insertion point involves traversing nodes.
Deletion (head)	$O(1)$	Updating pointers for the first node is constant time.
Deletion (tail)	$O(n)$	Finding the tail node without a tail pointer requires traversal.
Deletion (middle)	$O(n)$	Finding the node to delete involves traversal.
Search	$O(n)$	Elements are not indexed, so searching involves checking each.
Access by index	$O(n)$	No direct access to elements; must traverse from the beginning.
Traversal	$O(n)$	Visiting each node takes time proportional to the list's length.

Advantages of Linked Lists for Insertion/Deletion:

• Efficient for insertions and deletions compared to arrays, which might require shifting elements.

• No need to pre-allocate space, as nodes can be added or removed dynamically.

Disadvantages of Linked Lists for Access/Search:

• Slower for random access and searching compared to arrays, which have direct access by index.

Choosing the Right Data Structure:

• Consider linked lists when frequent insertions/deletions are needed and random access is less important.

• Choose arrays for efficient random access and faster searching.