Linked Lists

Linked Lists: An Introduction

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element, called a node, points to the next node in the sequence. This structure makes linked lists a powerful and flexible alternative to arrays, especially when frequent insertions and deletions are needed.

The Structure of a Node

At its core, a linked list is a collection of nodes. Each node typically contains two parts:

• Data: The value stored in the node.
• Next: A pointer or reference to the next node in the list. The final node's next pointer is usually null to mark the end.

The first node in a linked list is called the head, and it serves as the entry point for traversing the list.

Types of Linked Lists

• Singly Linked List

  • This is the most basic form, where each node has a pointer to the next one, allowing traversal in only one direction.

• Doubly Linked List

  • In a doubly linked list, each node has an additional pointer, prev, which points to the previous node. This allows for bidirectional traversal, but it uses more memory per node.

• Circular Linked List

  • A circular linked list is one where the last node's next pointer points back to the head of the list, creating a loop. This can be either singly or doubly linked.

Why Use Linked Lists?

Advantages

• Dynamic Size: Linked lists can easily grow or shrink, as memory is allocated dynamically.
• Efficient Insertions and Deletions: Adding or removing a node is fast (O(1)) if you have a reference to the node's predecessor. You simply update a few pointers.

Disadvantages

• No Random Access: To get to the nth node, you must traverse the list from the head, which takes O(n) time.
• Extra Memory Overhead: Each node requires additional memory to store the pointer to the next node.

---

LeetCode Problems for Linked Lists