## Creating a Linked List in Python

To create a linked list in Python, you start by defining a Node class. This class will represent the individual elements of the linked list. Each node object will have two attributes: data, which stores the value of the node, and next, which will point to the next node in the list.

Here's a simple example of how to define this Node class:

```
class Node:
def __init__(self, data):
self.data = data # Assign the data to this node
self.next = None # Initialize the next pointer to None
```

With the Node class defined, you can now create the LinkedList class that will handle the operations of the linked list, such as adding nodes and displaying the list. Hereâ€™s a basic structure for the LinkedList class:

```
class LinkedList:
def __init__(self):
self.head = None # Initialize the head of the list to None
def append(self, data):
new_node = Node(data) # Create a new node with the provided data
if self.head is None:
self.head = new_node # If the list is empty, set the new node as the head
else:
last_node = self.head
while last_node.next:
last_node = last_node.next # Traverse to the last node
last_node.next = new_node # Point the last node's next to the new node
def print_list(self):
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("None") # Indicate the end of the list
```

This LinkedList class starts with an empty head and grows as new nodes are appended. The append method adds a new node at the end of the list, and print_list provides a way to display the contents of the entire list.

## Creating a Node Class

The foundation of a linked list in Python is the Node class. This class is designed to store the individual elements of the list, each encapsulating the data and a reference to the next node. Hereâ€™s how you can create a basic Node class in Python:

```
class Node:
def __init__(self, data):
self.data = data # Store the data passed to the node
self.next = None # Initialize the next pointer to None, indicating the end of the list here
```

In this implementation:

- The __init__ method initializes a new instance of a Node. It takes data as a parameter, which represents the data stored in the node.

- self.data is used to hold the data within the node.

- self.next is a pointer that will eventually point to the next node in the linked list. Initially, it is set to None, which is useful for the end of the list or when the node is the only element in the list.

## Insertion in a Linked List

Inserting a new node into a linked list can be done in several ways, depending on where you want to place the new node: at the beginning, at a specific position, or at the end of the list. Each method has its own procedure:

### Insertion at Beginning in a Linked List

Inserting a node at the beginning of a linked list is one of the simplest and fastest operations. This operation changes the head of the list to the new node and links it to the previous head.

Hereâ€™s how you can implement this in Python:

```
def insert_at_beginning(self, data):
new_node = Node(data) # Create a new node with the given data
new_node.next = self.head # Link the new node's next to the current head
self.head = new_node # Update the head to be the new node
```

This method works as follows:

**Create a New Node:** A new node is created with the data provided.

**Set Next of New Node: **The next attribute of the new node is set to the current head of the linked list, effectively pointing to all the existing nodes.

**Update Head:** The head of the linked list is updated to this new node, making it the first node in the list.

Note -: By using this method, the new node becomes the first node of the linked list, and the operation is completed in constant time, O(1), since it involves a few assignments and does not depend on the size of the linked list.

### Insert a Node at a Specific Position in a Linked List

To insert a node at a specific position within a linked list, you must handle several steps carefully to maintain the integrity of the list. Letâ€™s see how to perform this operation in Python:

```
def insert_at_position(self, data, position):
if position == 0:
self.insert_at_beginning(data) # Handle the special case of inserting at the beginning
return
new_node = Node(data) # Create a new node
current = self.head
# Traverse the list to find the node before the desired position
for i in range(position - 1):
if current is None:
raise Exception("Position out of bounds") # If the position is greater than the number of nodes
current = current.next
new_node.next = current.next # Link the new node to the next node of the current node
current.next = new_node # Insert the new node after the current node
```

This method allows you to insert a node anywhere in the list, not just at the beginning or end.

Here are the steps broken down:

**Special Case for Beginning:** If the specified position is 0, the node is inserted at the beginning using the previously defined method.

**Node Creation: **A new node containing the data is created.

**Traversal:** The list is traversed until the node just before the desired position is reached.

**Insertion: **The next attribute of the new node is linked to the next node of the current node, and then the current node's next is updated to the new node.

Note : This approach ensures that the new node is correctly positioned, and all links are appropriately established to keep the list's structure intact.

### Insertion in a Linked List at End

Adding a node to the end of a linked list involves appending the new node after the last node in the list. This operation ensures that the new node becomes the new tail of the list. Hereâ€™s how you can implement this functionality in Python:

```
def append(self, data):
new_node = Node(data) # Create a new node with the given data
if self.head is None:
self.head = new_node # If the list is empty, this new node becomes the head
return
last = self.head
while last.next:
last = last.next # Traverse to the last node of the list
last.next = new_node # Make the last node's next point to the new node
```

This method works as follows:

**Node Creation:** A new node is created and initialized with the provided data.

**Check for Empty List: **If the list does not have any nodes (i.e., head is None), the new node is set as the head of the list.

**Traversal to the End: **The method traverses from the head to the last node of the list (the node that has None as its next).

**Linking to the Last Node: **The last nodeâ€™s next pointer is updated to point to the new node, thereby adding it to the end of the list.

Note : Appending a node in this manner ensures that the linked list maintains a continuous chain from the head to the tail, with the operation typically running in O(n) time due to the traversal of the list.

## Update the Node of a Linked List

Updating a node in a linked list involves changing the data of one of the nodes in the list. This operation can be useful when you need to modify the content of the list without altering the overall structure. Letâ€™s see the implementation of node updating in a linked list using Python:

```
def update_node(self, position, new_data):
if position < 0:
raise ValueError("Position must be a non-negative integer")
current = self.head
# Traverse to the desired position
for i in range(position):
if current is None:
raise IndexError("Position out of bounds") # Position exceeds the length of the list
current = current.next
if current is None:
raise IndexError("Position out of bounds")
current.data = new_data # Update the node's data with new data
```

In this method:

**Input Validation:** It first checks if the provided position is non-negative.

**Traversal:** The method traverses the list to reach the node at the specified position.

**Data Update: **If the node exists, its data is updated with the new data provided.

Note : This approach ensures that the data of a specific node is modified correctly while keeping the links between nodes intact, maintaining the integrity of the list's structure.

## Delete Node in a Linked List

Deleting a node from a linked list is a key operation that involves removing a node from the list and ensuring that the remaining nodes are still properly connected. Hereâ€™s how you can implement node deletion in a Python linked list:

```
def delete_node(self, key):
current = self.head
previous = None
# If the node to be deleted is the head node
if current is not None and current.data == key:
self.head = current.next # Move the head to the next node
return
# Search for the node to be deleted, keep track of the previous node
while current is not None and current.data != key:
previous = current
current = current.next
# If the node was not found
if current is None:
return "The data is not present in the list."
# Unlink the node from the linked list
previous.next = current.next
```

In this method:

**Head Check**: It first checks if the node to be deleted is at the head of the list.

**Traversal: **The list is traversed while keeping track of the node to be deleted (current) and the node just before it (previous).

**Deletion: **Once the node is found, it is unlinked from the list by setting the next of the previous node to the next of the current node.

**Handling Absence:** If no node contains the key, a message is returned indicating that the data is not present in the list.

Note : This deletion process ensures that the linked list remains intact except for the removed node, and the structural links between remaining nodes are properly maintained.

### Remove First Node from Linked List

Removing the first node from a linked list, also known as the head of the list, is a straightforward process. This operation is typically used when you need to process or remove the front element of the list. Hereâ€™s how you can implement the removal of the first node in a Python linked list:

```
def remove_first(self):
if self.head is None:
return "The list is empty, nothing to remove."
# Move the head pointer to the next node, effectively removing the first node
self.head = self.head.next
```

This method:

**Check for Empty List:** First checks if the list is empty. If it is, it returns a message stating that there is nothing to remove.

**Update Head:** If the list is not empty, the head of the list is updated to the next node in the list, thereby removing the current head.

Note : Removing the first node is an O(1) operation, meaning it can be done in constant time regardless of the size of the list

### Remove Last Node from Linked List

Removing the last node from a linked list requires a bit more effort compared to removing the first node, mainly because you have to traverse the entire list to reach the end. Letâ€™s see how to remove the last node from a linked list in Python:

```
def remove_last(self):
if self.head is None:
return "The list is empty, nothing to remove."
if self.head.next is None:
self.head = None # If there is only one node, make head None
return
second_last = self.head
while second_last.next.next:
second_last = second_last.next # Move to the second last node
second_last.next = None # Remove the last node by setting the second last node's next to None
```

This method:

**Check for Empty List**: Starts by checking if the list is empty. If it is, it informs that there is nothing to remove.

**Single Node Check: **Checks if the list has only one node. If so, it simply sets the head to None.

**Traverse to Second Last Node**: If the list has more than one node, it traverses to the second last node.

**Remove Last Node**: The next of the second last node is set to None, effectively removing the last node from the list.

Note : Removing the last node involves traversing almost the entire list, making it an O(n) operation, where n is the number of nodes in the list. This is necessary to maintain the integrity of the linked list.

### Delete a Linked List Node at a Given Position

To delete a node from a specific position in a linked list, you must correctly identify and unlink the node at that position. Hereâ€™s how to perform this operation in Python:

```
def delete_at_position(self, position):
if self.head is None:
return "The list is empty, nothing to delete."
if position == 0:
self.head = self.head.next # Remove the head if the position is 0
return
previous = None
current = self.head
count = 0
# Traverse to the desired position or the end of the list
while current is not None and count < position:
previous = current
current = current.next
count += 1
if current is None:
return "Position out of bounds."
# Unlink the node from the list by setting the previous node's next to current node's next
previous.next = current.next
```

This method involves:

**Empty List Check: **Checking if the list is empty, in which case there is nothing to delete.

**Head Removal: **Removing the head directly if the position to delete is 0.

**Traversal: **Traversing the list to find the node just before the position to ensure the node at that position can be removed.

**Position Check:** Ensuring that the position is not out of the bounds of the list.

**Unlinking the Node**: If the node is found, it is unlinked by adjusting the next pointer of the previous node.

Note : Deleting a node at a specific position requires careful handling to maintain the integrity of the linked list, especially in terms of not leaving any node disconnected.

### Delete a Linked List Node of a Given Data

Removing a node based on its data involves searching through the linked list to find a node that contains the specified data and then deleting that node from the list. Letâ€™s see how we can implement this in Python:

```
def delete_node_by_data(self, data):
current = self.head
previous = None
# Check if the list is empty
if current is None:
return "The list is empty, nothing to delete."
# If the node to be deleted is the head node
if current.data == data:
self.head = current.next # Move the head to the next node
return
# Traverse the list looking for the node with the specified data
while current is not None and current.data != data:
previous = current
current = current.next
# If the node was not found
if current is None:
return "No node with the specified data found."
# Unlink the node from the linked list
previous.next = current.next
```

This method includes:

**Empty List Check: **Initial check to determine if the list is empty.

**Head Node Check:** Special handling if the node to be deleted is the head.

**Traversal and Search:** Looping through the list to find the node with the matching data.

**Deletion: **Once the node is found, it is unlinked from the list by setting the next attribute of the previous node to the next node of the current node.

**Not Found Case: **Handling the scenario where no node with the specified data exists.

Note : This approach ensures that any node with the specified data is effectively removed from the linked list, maintaining the list's structure and integrity.

## Linked List Traversal in Python

Traversing a linked list involves sequentially accessing each node in the list from the beginning to the end. This is crucial for many operations, such as displaying the listâ€™s content, performing searches, or applying transformations. Here's how you can implement linked list traversal in Python:

```
def traverse(self):
current = self.head
# Check if the list is empty
if current is None:
print("The list is empty.")
return
# Loop through each node until you reach the end of the list
while current:
print(current.data, end=" -> ")
current = current.next
print("None") # This represents the end of the list
```

In this method:

**Empty List Check: **It first checks whether the list is empty, in which case it informs the user.

**Traversal: **The method then loops through each node in the list, starting from the head.

**Displaying Data: **As it traverses, it prints the data contained in each node, followed by an arrow (->) pointing to the next node, indicating the link between nodes.

**End of List: **Once all nodes are accessed, it prints "None" to signify the end of the list.

Note : This traversal technique is not only useful for displaying the contents of the list but also forms the basis for many other linked list operations, such as insertion, deletion, and searching, by providing a mechanism to access each node systematically.

### Get Length of a Linked List in Python

Determining the length of a linked list involves counting the number of nodes from the beginning to the end of the list. This is an essential operation for various purposes, such as validating indices for insertion or deletion. Letâ€™s see a method to calculate the length of a linked list in Python:

```
def get_length(self):
count = 0 # Initialize a counter to zero
current = self.head # Start with the head of the list
while current:
count += 1 # Increment the counter for each node encountered
current = current.next # Move to the next node
return count # Return the total number of nodes
```

This method works by:

**Initialization**: Starting the count at zero and setting the current node to the head of the list.

**Traversal: **Iteratively moving through each node in the list, increasing the count by one for each node passed.

**Completion:** When no more nodes are left (current becomes None), the method returns the count.

Note : Calculating the length of the list is an O(n) operation, where n is the number of nodes in the list, as it requires a full traversal from the head to the end.

## Example of a Linked List in Python

To consolidate our understanding of linked lists and their operations in Python, let's construct a complete example that demonstrates creating a linked list, adding nodes, and performing various operations like insertion, deletion, and traversal. Here's a comprehensive example:

### Python

`class Node:`

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

def append(self, data):

new_node = Node(data)

if not self.head:

self.head = new_node

return

last = self.head

while last.next:

last = last.next

last.next = new_node

def print_list(self):

current = self.head

while current:

print(current.data, end=" -> ")

current = current.next # Corrected here

print("None")

def insert_at_beginning(self, data):

new_node = Node(data)

new_node.next = self.head

self.head = new_node

def insert_at_position(self, data, position):

if position == 0:

self.insert_at_beginning(data)

return

new_node = Node(data)

temp = self.head

for i in range(position - 1):

if not temp:

raise Exception("Position out of bounds")

temp = temp.next

new_node.next = temp.next

temp.next = new_node

def delete_node(self, key):

current = self.head

previous = None

while current and current.data != key:

previous = current

current = current.next

if previous is None:

self.head = current.next

elif current:

previous.next = current.next

def get_length(self):

count = 0

current = self.head

while current:

count += 1

current = current.next

return count

# Usage

llist = LinkedList()

llist.append(3)

llist.append(5)

llist.append(7)

llist.insert_at_beginning(2)

llist.insert_at_position(4, 2)

llist.delete_node(5)

llist.print_list()

print("Length of list:", llist.get_length())

Output

```
2 -> 3 -> 4 -> 7 -> None
Length of list: 4
```

## Frequently Asked Questions

### What is the time complexity of accessing an element in a linked list?

The time complexity of accessing an element in a linked list is O(n), as it requires traversal from the head to the specified position in the worst case.

### Can linked lists contain different data types in Python?

Yes, linked lists in Python can contain different data types because Python is a dynamically typed language, allowing nodes to store data of any type.

### Why would you use a linked list over an array?

Linked lists are preferable when you need dynamic data allocation, frequent insertion and deletion of nodes at arbitrary positions, and when memory size is a concern, as they don't require memory to be allocated in advance.

## Conclusion

In this article, we have learned about all the operations of linked lists in Python. We covered how to create and manipulate nodes within a linked list, including operations such as appending nodes, inserting nodes at specific positions, deleting nodes, and traversing the list to display its contents or determine its length. These concepts are very important to learn as these are the basics of other complex algorithms and concepts of programming. So, practice them properly and try to master them.

You can refer to our __guided paths__ on the Coding Ninjas. You can check our course to learn more about __DSA__, __DBMS__, __Competitive Programming__, __Python__, __Java__, __JavaScript,__ etc. Also, check out some of the __Guided Paths__ on topics such as __Data Structure andAlgorithms__, __Competitive Programming__, __Operating Systems__, __Computer Networks,__ __DBMS__, __System Design__, etc., as well as some __Contests, ____Test Series__, and __Interview Experiences__ curated by top Industry.