🔗 Linked Lists

👉 What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are not stored in contiguous memory locations. Instead, each node contains two parts: the data itself and a pointer (or reference) to the next node in the sequence.

• Head: The entry point to the list, which is a pointer to the very first node.
• Tail: The last node in the list points to None (or null), indicating the end of the list.

⭐ Basic Operations & Complexity

The performance of a linked list is very different from an array due to its structure.

• Access and Search: To find an element, you must start at the head and traverse the list one node at a time.
  • Complexity: O(n)
• Insertion at the Beginning: A new node is created, its pointer is set to the current head, and the list’s head is updated to the new node.
  • Complexity: O(1)
• Insertion at the End: Requires traversing the entire list to find the last node, then updating its pointer.
  • Complexity: O(n) (or O(1) if you maintain a separate pointer to the tail node).
• Deletion from the Beginning: The head pointer is simply moved to the second node.
  • Complexity: O(1)
• Deletion from the Middle/End: You must traverse the list to find the node before the one you want to delete to update its pointer.
  • Complexity: O(n)

⛓️ Types of Linked Lists

• Singly Linked List: The standard version where each node has a pointer only to the next node. Traversal is one-way.
• Doubly Linked List: Each node has two pointers: one to the next node and one to the previous node. This allows for forward and backward traversal but uses more memory.
• Circular Linked List: The last node’s pointer points back to the head of the list instead of None, forming a circle.

👍 Advantages

• Dynamic Size: Can grow and shrink easily without reallocating an entire block of memory.
• Efficient Insertions/Deletions: Very fast (O(1)) to add or remove elements at the beginning of the list.

👎 Disadvantages

• No Random Access: You cannot access an element by its index in constant time. Accessing any element requires O(n) traversal.
• Extra Memory: Each node requires extra memory to store its pointer(s).

⚠️ Important Note: The primary trade-off between a linked list and an array is access vs. insertion/deletion. Use an array for fast O(1) access. Use a linked list when you need efficient O(1) insertions and deletions at the beginning of a sequence.