# Linked List in Python

## Introduction to Linked List in Python

A linked list in Python is a data structure used for storing a collection of elements, where each element, known as a “node,” contains both data and a reference to the next node in the sequence.

In this page, we will dive deep into understanding linked lists in Python, exploring their types, operations, and practical applications.

## What is a Linked List in Python?

A linked list is a linear data structure where elements, known as nodes, are connected together using pointers or references. Each node contains two components: data and a reference (or link) to the next node in the sequence.

- Linked lists are versatile and can be used to implement various data structures like stacks, queues, and symbol tables.

**Types of Linked List in Python**

**Singly Linked List :**In a singly linked list, each node points to the next node in the sequence. It is the simplest form of a linked list and is often used when we need to traverse the list in one direction.

**Doubly Linked List :**A doubly linked list extends the concept of a singly linked list by adding an additional reference to the previous node. This bidirectional connection allows for more versatile operations but consumes additional memory.

**Circular Linked List :**In a circular linked list, the last node points back to the first node, forming a closed loop. This structure is advantageous in scenarios where we need continuous access to elements.

**Creating a Linked List in Python**

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None

## Mastering Linked List Operations in Python

- Insertion Operation
- Deletion Operation

### Insertion Operation

To insert a node at the beginning of the linked list, we modify the**Insertion at the Beginning :****‘****head’**reference.

def insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node

To insert a node at the end, we traverse the list to find the last node:**Insertion at the End :**

def insert_at_end(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node

### Deletion Operations

To delete a node by its value, we find the node and update the references:**Deleting a Node by Value :**

def delete_by_value(self, value): current = self.head if current and current.data == value: self.head = current.next current = None return prev = None while current and current.data != value: prev = current current = current.next if current is None: return prev.next = current.next current = None

## Understanding Singly vs. Doubly Linked Lists

Aspect | Singly Linked List | Doubly Linked List |
---|---|---|

Definition | A data structure where each node points to the next node in the list. | A data structure where each node points to both the next and the previous node in the list. |

Nodes | Each node contains data and a reference (pointer) to the next node. | Each node contains data, a reference to the next node, and a reference to the previous node. |

Traversing Forward | Easy and efficient. | Easy and efficient. |

Traversing Backward | Not efficient; requires starting from the head and traversing the list. | Efficient; can traverse backward easily using the previous pointers. |

Insertion/Deletion at Head | Efficient; O(1) complexity. | Efficient; O(1) complexity. |

Insertion/Deletion at Tail | Inefficient; O(n) complexity as it requires traversing the entire list to reach the tail. | Efficient; O(1) complexity as the tail pointer is readily accessible. |

Insertion/Deletion in Middle | Requires traversal to the insertion/deletion point; O(n) complexity. | Requires traversal to the insertion/deletion point; O(n) complexity. |

Use Cases | Suitable for cases where forward traversal is the primary operation and memory efficiency is crucial. | Suitable for cases where both forward and backward traversal is required, and memory efficiency is not a significant concern. |

**Advantages of Linked Lists in Python**

- Dynamic Sizing: Linked lists can grow or shrink dynamically, optimizing memory usage.
- Efficient Insertions/Deletions: O(1) time complexity for inserting/deleting at the beginning.
- No Wasted Memory: Memory allocation only occurs when needed.

**Conclusion**

In this page, we’ve explored the world of linked lists in Python, covering their types, operations of linked list in python implementations, advantages, and real-world applications.

### Prime Course Trailer

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

**Question 1**.

**Are linked lists only used in Python?**

No, linked lists are a data structure used in many programming languages, not just Python.

**Question 2**.

**How can I optimize linked list operations for large datasets?**

To optimize linked list operations for large datasets, consider using data structures like skip lists or balanced trees, which offer faster search times.

**Question 3**.

**What is the time complexity of inserting a node in a linked list?**

The time complexity depends on the position of insertion. In the worst case, it’s O(n) for singly linked lists and O(1) for doubly linked lists when inserting at the beginning.

**Get over 200+ course One Subscription**

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Login/Signup to comment