# Understanding Linked Lists

Note: this page has been created with the use of AI. Please take caution, and note that the content of this page does not necessarily reflect the opinion of Cratecode.

When it comes to data structures, arrays often get all the glory. They're simple, straightforward, and intuitive. But in the shadows, there's another hero quietly doing its job: the linked list. Imagine a conga line at a party, where each person holds hands with the next. If someone leaves the line, the others can just link up and keep dancing. That's the essence of a linked list! Let's dive deeper into what makes this data structure so unique and useful.

## What is a Linked List?

A linked list is a collection of elements called nodes. Each node contains two components:

**Data**: The value or information the node holds.**Pointer/Reference**: A reference to the next node in the sequence.

Unlike arrays, where elements are stored in contiguous memory locations, linked list nodes can be scattered throughout memory. The nodes are connected through pointers, creating a chain-like structure. Think of it as a treasure hunt where each clue (node) leads you to the next.

Here's a simple representation of a linked list:

`[Data|Next] -> [Data|Next] -> [Data|Next] -> null`

## Why Use Linked Lists?

Linked lists offer several advantages over other data structures, particularly arrays:

**Dynamic Size**: Linked lists can easily grow and shrink in size by adding or removing nodes. This is unlike arrays, which have a fixed size or require resizing.**Efficient Insertions/Deletions**: Adding or removing elements from a linked list is efficient, especially at the beginning or middle, as it only involves updating pointers. In contrast, arrays require shifting elements to maintain order.

## Types of Linked Lists

There are several types of linked lists, each suited to different scenarios:

### 1. Singly Linked List

In a singly linked list, each node points to the next node in the sequence. The last node points to `null`

, indicating the end of the list.

`# Node class for a singly linked list class Node: def __init__(self, data): self.data = data self.next = None # Creating nodes and linking them node1 = Node(1) node2 = Node(2) node3 = Node(3) node1.next = node2 node2.next = node3 # Traversing the linked list current = node1 while current: print(current.data) current = current.next`

### 2. Doubly Linked List

A doubly linked list extends the concept of a singly linked list by adding a pointer to the previous node. This allows traversal in both directions.

`# Node class for a doubly linked list class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Creating nodes and linking them node1 = Node(1) node2 = Node(2) node3 = Node(3) node1.next = node2 node2.prev = node1 node2.next = node3 node3.prev = node2 # Traversing the linked list forward current = node1 while current: print(current.data) current = current.next # Traversing the linked list backward current = node3 while current: print(current.data) current = current.prev`

### 3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a loop. This is useful for applications where the data needs to be cyclically accessed.

`# Node class for a circular linked list class Node: def __init__(self, data): self.data = data self.next = None # Creating nodes and linking them node1 = Node(1) node2 = Node(2) node3 = Node(3) node1.next = node2 node2.next = node3 node3.next = node1 # Circular link # Traversing the circular linked list current = node1 for _ in range(6): # Loop twice through the list print(current.data) current = current.next`

## Common Operations on Linked Lists

### Insertion

Adding a new node to a linked list can be done at various positions: at the beginning, at the end, or in the middle. Let's explore these operations in a singly linked list.

#### Insert at the Beginning

`def insert_at_beginning(head, new_data): new_node = Node(new_data) new_node.next = head return new_node # Usage head = insert_at_beginning(node1, 0)`

#### Insert at the End

`def insert_at_end(head, new_data): new_node = Node(new_data) if not head: return new_node current = head while current.next: current = current.next current.next = new_node return head # Usage head = insert_at_end(node1, 4)`

### Deletion

Removing a node from a linked list involves adjusting the pointers of the adjacent nodes.

#### Delete a Node

`def delete_node(head, key): current = head prev = None # If the head node holds the key if current and current.data == key: return current.next while current and current.data != key: prev = current current = current.next if current: prev.next = current.next return head # Usage head = delete_node(node1, 2)`

## Real-world Applications

Linked lists are versatile and used in various applications:

**Implementing Stacks and Queues**: Linked lists provide efficient ways to implement stack and queue data structures.**Navigating Undo/Redo**: Doubly linked lists can be used to implement undo/redo functionality by navigating through the node sequences.**Memory Management**: Linked lists are used in dynamic memory allocation (e.g., free lists of available memory blocks).

Linked lists might not be as glamorous as arrays, but their flexibility and efficiency make them indispensable in many scenarios. Whether you're building a simple application or a complex system, understanding linked lists will undoubtedly come in handy.

Hey there! Want to learn more? Cratecode is an online learning platform that lets you forge your own path. Click here to check out a lesson: Common Programming Pitfalls (psst, it's free!).

## FAQ

### What are the advantages of a linked list over an array?

Linked lists can grow and shrink dynamically, and they allow for efficient insertions and deletions, especially at the beginning or middle. On the other hand, arrays have a fixed size and require shifting elements to maintain order during insertions and deletions.

### How do you traverse a linked list?

To traverse a linked list, start from the head node and follow the pointers from one node to the next until you reach the end (null). In a doubly linked list, you can traverse both forward and backward by following the next and previous pointers, respectively.

### What is a circular linked list used for?

Circular linked lists are useful for applications where data needs to be accessed cyclically, such as in round-robin scheduling or implementing a circular buffer.

### How do you delete a node in a linked list?

To delete a node, adjust the pointers of the adjacent nodes to bypass the node to be removed. If the node to delete is the head node, simply move the head pointer to the next node.

### Can linked lists have cycles other than circular linked lists?

Yes, any linked list can inadvertently have cycles if nodes form loops due to incorrect pointer assignments. Detecting and handling such cycles is essential to prevent infinite loops during traversal.