 A linked list is a sequential collection of data elements, which are connected together via links. A linked list consists of independent nodes containing any type of data and each node holds a reference or a link to the next node in the list.

The beginning node of a linked list is called the head and the end node is called the tail. All nodes of a linked list are independent and are not stored contagiously in memory.

The above figure shows a linked list with 4 independent nodes. Each node holds the address of the next node and is linked to it. The head node is the first in the list and therefore has no link pointing towards it. The tail node is identified by a “null” value in the link address.

There are 4 types of linked lists that can be created in python.

In a singly linked list, each node holds a value and a reference/link to the next node. It has no link pointing to the previous node. This is the simplest form of a linked list.

The circular singly linked list is similar to a singly linked list. The only difference is that the last node holds a reference to the first node of the linked list.

When we reach the last node of the circular singly linked list, we have an option of going back to the first node. This is not possible in the case of a singly linked list.

In a doubly-linked list, each node of the list has two references, one of the previous node and the other of the next node. Thus, each node holds two addresses along with the data value. Since each node has two references, a doubly-linked list allows us to traverse in both directions.

Circular doubly linked lists are similar to doubly linked lists. The only difference is that their first and last nodes are interconnected as well. The head node holds a reference to the tail node and vice versa.

Hence, in a circular doubly linked list we can perform circular traversal by jumping from the first node to the last node or from the last node to the first node.

### Creation of Singly Linked List

We can create a singly linked list in python by following the mentioned steps.

• Step 1: First, we create empty head and tail references and initialize both of them with null.
• Step 2: Create a class “node”. The objects of this class hold one variable to store the values of the nodes and another variable to store the reference addresses.
• Step 3: Create a blank node and assign it a value. Set the reference part of this node to null.
• Step 4: Since we have only one element in the linked list so far, we will link both the head and tail to this node by putting in its reference address.
``````#Creating the Node class
class Node:
def __init__(self, value = None):
self.value = value
self.next = None

#Create a class to initialize head and tail references
def __init__(self):
self.tail = None

temp_node1 = Node(10)
temp_node2 = Node(20)

singlyll.tail = temp_node2``````

### The iterator function

Since the custom-created linked list is not iterable, we have to add an “__iter__” function so as to traverse through the list.

``````#Iterator Function
def __iter__(self):
while node:
yield node
node = node.next``````

The time complexity for initializing a singly linked list is O(1). The space complexity is O(1) as no additional memory is required to initialize the linked list.

### Insertion in Singly Linked List

A node can be inserted in a singly linked list in any one of the following three ways.

• At the beginning of the linked list
• In between the linked list
• At the end of the linked list

### Insertion Algorithm

#### Algorithm to insert a node at the beginning

• Step 1: Create a node and assign a value to it.
• Step 2: Assign the “next” reference of the node as head.
• Step 3: Set the created node as the new head.
• Step 4: Terminate.

#### Method to insert a node at the beginning

``````#Insertion at the beginning in a Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None

def __init__(self):
self.tail = None

#Function to add node in the beginning
def atBeg(self, value):
new_node =  Node(value)

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.atBeg(0)
print([node.value for node in sll])

#Output
[0, 1, 3, 5, 7, 9]``````

#### Algorithm to insert a node in between the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the previous node doesn’t exist, return an error message and move to step 5.
• Step 3: Assign the “next” reference of the previous node to the “next” reference of the new node.
• Step 4: Set the “next” reference of the previous node to the newly added node.
• Step 5: Terminate.

#### Method to insert a node in between the linked list

``````#Insertion in between a Singly Linked List
#Function to add node in the middle
def inMid(self,mid_node, value):
if mid_node is None:
print("Mentioned node doesn't exist")
return

new_node = Node(value)
new_node.next = mid_node.next
mid_node.next = new_node

#Initially, we have a linked list (1,3,5,7,9) called "sll" and "mid" node points to the value 3.
sll.inMid(mid, 11)
print([node.value for node in sll])

#Output
[1, 3, 11, 5, 7, 9]``````

#### Algorithm to insert a node at the end of the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the list is empty, assign new node to head and tail. Move to step 5.
• Step 3: Search for the last node. Once found, set its “next” reference pointing to the new node.
• Step 4: Assign the new node as the tail.
• Step 5: Terminate.

#### Method to insert a node at the end of the linked list

``````#Insertion at the end in a Singly Linked List
#Function to add node in the end
def atEnd(self, value):
new_node = Node(value)
self.tail = new_node
return
while(last_node.next):
last_node = last_node.next
last_node.next=new_node
self.tail = new_node

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.atEnd(0)
print([node.value for node in sll])

#Output
[1, 3, 5, 7, 9, 0]``````

#### Time and Space Complexity

In python, instead of iterating over the linked list and reaching the required position, we can directly jump to any point. Therefore, the time complexity of insertion in a singly linked list is O(1).

But, for insertion at the end, the time complexity is O(N) as we need to traverse to the last element. The space complexity is O(1) because it takes a constant space to add a new node.

### Traversal in Singly Linked List

A singly linked list can only be traversed in the forward direction from the first element to the last. We get the value of the next data element by simply iterating with the help of the reference address.

### Traversing Method

``````#Traversal through Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None

def __init__(self):
self.tail = None

def printList(self):
while node_print is not None:
print (node_print.value)
node_print = node_print.next

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.printList()

#Output
1
3
5
7
9``````

#### Time and Space Complexity

We need to loop over the linked list to traverse and print every element. The time complexity for traversal is O(N) where ‘N’ is the size of the given linked list. The space complexity is O(1) as no additional memory is required to traverse through a singly linked list.

### Searching in a Singly Linked List

To find a node in a given singly linked list, we use the technique of traversal. The only difference, in this case, is that as soon as we find the searched node, we will terminate the loop.

The worst-case scenario for search is when we have the required element at the end of the linked list, in such a case we have to iterate through the entire linked list to find the required element.

### Searching Algorithm

• Step 1: If the linked list is empty, return the message and move to step 5.
• Step 2: Iterate over the linked list using the reference address for each node.
• Step 3: Search every node for the given value.
• Step 4: If the element is found, break the loop. If not, return the message “Element not found”.
• Step 5: Terminate.

### Searching Method

``````#Searching in a Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None

def __init__(self):
self.tail = None

def searchList(self, value):
position = 0
found = 0
print ("The linked list does not exist")
else:
while temp_node is not None:
position = position + 1
if temp_node.value == value:
print ("The required value was found at position: " + str(position))
found = 1
temp_node = temp_node.next
if found == 0:
print ("The required value does not exist in the list")

#Initially, we have a linked list (1,3,5,7,9) called "sll".
print(sll.searchList(7))

#Output
The required value was found at position: 4``````

#### Time and Space Complexity

The time complexity for searching a given element in the linked list is O(N) as we have to loop over all the nodes and check for the required one. The space complexity is O(1) as no additional memory is required to traverse through a singly linked list and perform a search.

### Deletion of node from Singly Linked List

To delete an existing node from a singly linked list, we must know the value that the node holds. For deletion, we first locate the node previous to the given node. Then we point the “next” reference of this node to the one after the node to be deleted.

A node can be deleted from a singly linked list in any one of the following three ways.

• Deleting the first node
• Deleting any given node
• Deleting the last node

### Deletion Algorithm

#### Algorithm to delete a node from the beginning

• Step 1: If the linked list is empty, return a null statement and go to step 5.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 5.
• Step 3: Set a “temp_node” pointing at head.
• Step 4: Assign head as the next node. Delete the temp node.
• Step 5: Terminate.

#### Method to delete a node from the beginning

``````#Deletion at the beginning of a Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None

def __init__(self):
self.tail = None

#Function to delete node from the beginning
def delBeg(self):
return
return
temp_node = None
return

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delBeg()
print([node.value for node in sll])

#Output
[3, 5, 7, 9]``````

#### Algorithm to delete a node from between the linked list

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If the value to be deleted is the first node, set head to the next element and remove the first node. Go to step .
• Step 3: Iterate through the linked list and search for the element to be deleted.
• Step 4: Set “prev” as the node before the one to be deleted. Break the loop.
• Step 5: Delete the required node and set “next” reference of “prev” to the node after the deleted one.
• Step 6: Terminate.

#### Method to delete a node from between the linked list

``````#Function to delete a node from between the linked list
def delMid(self, del_value):
return

break

return

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delMid(3)
print([node.value for node in sll])

#Output
[1, 5, 7, 9]``````

#### Algorithm to delete a node from the end

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 6.
• Step 3: Set a “temp_node” pointing at head. Iterate the linked list till that node points to the second last node of the list.
• Step 4: Assign tail as the temp node. Set temp node to the next node, i.e., last in the list.
• Step 5: Delete the temp_node.
• Step 6: Terminate.

#### Method to delete a node from the end

``````#Function to delete node from the end
def delEnd(self):
return
return
else:
while (temp_node.next is not self.tail):
temp_node = temp_node.next
self.tail = temp_node
temp_node.next = None
return
#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delEnd()
print([node.value for node in sll])

#Output
[1, 3, 5, 7]``````

#### Time and Space Complexity

The time complexity for deletion in a singly linked list is O(N) as we have to loop over all the nodes and search for the required one. The space complexity is O(1) as no additional memory is required to delete an element from a singly linked list.

### Deletion of entire Singly Linked List

The deletion of an entire singly linked list is quite a simple process. We have to set the two reference nodes “head” and “tail” to none.

#### Algorithm to delete an entire singly linked list

• Step 1: If the linked list is empty, return an error message and go to step 4.
• Step 2: Delete the “head” node by setting it to none.
• Step 3: Delete the “tail” node by setting it to none.
• Step 4: Terminate.

#### Method to delete an entire singly linked list

``````#Deletion of an entire Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None

def __init__(self):
self.tail = None

def delSLL(self):
print("The singly linked list does not exist.")
else:
self.tail = None
print("The singly linked list has been deleted.")

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delSLL()

#Output
The singly linked list has been deleted.``````

#### Time and Space Complexity

The time complexity for deletion of an entire singly linked list is O(1) because we are just setting the “head” and “tail” references to none. The space complexity is O(1) as well since there is no additional space required when deleting the references.

### Interview Questions on Singly Linked List

#### Write a code to remove duplicate values from an unsorted linked list.

To solve the duplicate value problem, we initialize a set called ‘visited’. It stores every value we encounter while iterating the linked list. If a value already exists in ‘visited’, we can then remove it from the list.

``````#Code to remove duplicate values from a linked list
return
else:
visited = set([current_node.value])
while current_node.next:
if current_node.next.value in visited:
current_node.next = current_node.next.next
else:
current_node = current_node.next
``````

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to check for any duplicate item. The space complexity is O(N) as well since the ‘visited’ set gets dynamically filled during iteration.

#### Implement a code to find the Kth to last element in a singly linked list.

To find the Kth to the last element in a linked list, we initialize two pointers. While one pointer iterates to the end of the linked list, the other pointer stops at Kth to the last element.

``````#Code to find Kth to last element in a singly linked list

for i in range(k):
if second_pointer is None:
return None
second_pointer = second_pointer.next

while second_pointer:
first_pointer = first_pointer.next
second_pointer = second_pointer.next
return first_pointer

#Initially, we have a linked list (1,3,5,7,9) called "sll".
print(kthToLast(sll, 3))

#Output
5``````

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to set the pointers. The space complexity is O(1) as no additional memory is required to assign the references.

#### Write a code to partition a linked list around a value x. All nodes less than x come before all the nodes greater than or equal to x.

``````#Code to partition the linked list around a value 'x'

while current_node:
next_node = current_node.next
current_node.next = None
if current_node.value < x:
else:
current_node = current_node.next

#Initially, we have a linked list (7,3,9,11,1,5) called "sll".
partition(sll, 6)
print([node.value for node in sll])

#Output
[5, 1, 3, 9, 11, 5]``````

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to set the partition. The space complexity is O(1) as no additional memory is required.

There are two numbers represented by a linked list, where each node contains a single digit. The digits are placed in reverse order, i.e., the 1’s digit is at the head of the list. Write a function to add the two numbers and returns the sum as a linked list.

``````#Code to return the sum of two numbers represented by linked lists
carry = 0

while num1 or num2:
result = carry
if num1:
result += num1.value
num1 = num1.next
if num2:
result += num2.value
num2 = num2.next
carry = result /10
return newLL

#Initially, we have a linked list (7, 1, 6) called "sll1" and (5, 9, 2) called "sll2".
print(sll1)
print(sll2)
print(sumList(sll1, sll2))

#Output
7 -> 1 -> 6
5 -> 9 -> 2
2 -> 1 -> 9``````

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list. The space complexity is O(n) as we fill up the newly created linked list dynamically.

Determine whether two given singly-linked lists intersect. Return the intersecting node. The intersection is defined based on the node’s reference, not its value. It means that if the nth node of the first linked list is the same as the mth node of the second linked list, then they are intersecting.

``````#Code to check whether two lists are intersecting
return False
diff = len(longer) - len(shorter)

for i in range(diff):
longer_node = longer_node.next
while shorter_node is not longer_node:
shorter_node = shorter_node.next
longer_node = longer_node.next
return longer_node

#Initially, we have a linked list (7, 1, 6, 8) called "sll1" and (5, 9, 6, 2) called "sll2". Suppose the node with value 6 is the same for both the linked lists.
print(intersection(sll1, sll2))

#Output
6``````

The time complexity of this algorithm is O(A + B) where A is the length of the first linked list and B is the length of the second linked list. We need to traverse both lists to find the number of nodes. The space complexity is O(1) as no additional memory is required.

## FAQ question

##### What is a Linked List in Python?

In a linked list, each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library.

``````class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None

def __init__(self):
def listprint(self):
while printval is not None:
print (printval.dataval)
printval = printval.nextval

day2 = Node("Tuesday")
day3 = Node("Wednesday")
day2.nextval = day3
list.listprint()``````

Output

``````Monday
Tuesday
Wednesday``````
##### How to Reverse a Linked List in Python?

The iterative method is used in the user-defined `reverse()` function to reverse the linked list.

``````class LinkedList:
def __init__(self):

def reverse(self):
prev = None
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next

def push(self, new_data):
new_node = Node(new_data)

def printList(self):
while(temp):
print(temp.data)
temp = temp.next

llist.push(200)
llist.push(40)
llist.push(175)
llist.push(85)
llist.printList()
llist.reverse()
llist.printList()``````

Output

``````Given Linked List
85
175
40
200

200
40
175
85``````
##### How to create a Linked List in Python

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

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

def __init__(self):

def insert(self, data):
newNode = Node(data)
while(current.next):
current = current.next
current.next = newNode
else:

def printLL(self):
while(current):
print(current.data)
current = current.next

LL.insert(98)
LL.insert(23)
LL.insert(5)
LL.printLL()``````

Output

``````98
23
5``````
##### How to Sort a Linked List in Python?

In the below code, while the node is not null, value is added at the end of the node, Which is given by node = next of node. Then the list of values is sorted.

``````class Solution:
def solve(self, node):
values = []
while node:
values.append(node.val)
node = node.next
values.sort()
values = collections.deque(values)
while node:
node.val = values.popleft()
node = node.next

ob = Solution()
head = make_list([5, 8, 41, 21, 5, 60, 3])

Output

``[3, 5, 5, 8, 21, 41, 60, ]``
##### How to Use the Linked List in a Loop using Python?

To traverse through the Linked list loops can be used. In the below code, a while loop is used to traverse through the linked list.

``````class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None

def __init__(self):
def listprint(self):
while printval is not None:
print (printval.dataval)
printval = printval.nextval

day2 = Node("Tuesday")
day3 = Node("Wednesday")
day2.nextval = day3
list.listprint()``````

Output

``````Monday
Tuesday
Wednesday``````
##### How to Transform a Linked List to a Normal List in Python?

The list comprehension can be used to convert a linked list into a list.

``````child = {'Hello':'Welcome', 'Welcome': 'To', 'To': 'Pythonwife', 'Pythonwife': None}
def ll_iterator(node):
while node != None:
yield node
node = child[node]
[x for x in ll_iterator('Hello')]``````

Output

``['Hello', 'Welcome', 'To', 'Pythonwife']``
##### How to Put Contents from an Array into a Linked List using Python?

We create a node in a linked list for each element of an array arr[] and insert it at the end.

``````import math
class Node:
def __init__(self, data):
self.data = data
self.next = None

# Function to insert node
def insert(root, item):
temp = Node(item)

if (root == None):
root = temp
else :
ptr = root
while (ptr.next != None):
ptr = ptr.next
ptr.next = temp
return root

def display(root):
while (root != None) :
print(root.data, end = " ")
root = root.next

def arrayToList(arr, n):
root = None
for i in range(0, n, 1):
root = insert(root, arr[i])
return root

if __name__=='__main__':
arr = [1, 2, 3, 4, 5]
n = len(arr)
root = arrayToList(arr, n)
display(root)``````

Output

``1 2 3 4 5 ``
##### How to Reverse a Linked List Recursively using Python?

The `reverse()` function is called recursively to reverse the linked list.

``````def reverse(head, headRef):
rest = first.next
if rest is None:
rest.next = first
first.next = None

if __name__ == '__main__':
for i in reversed(range(6)):

Output

``6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None``
##### How to Pass a Linked List as a Parameter in Python?

The linked list can be passed as a parameter, like any other list by enclosing the elements in [] symbol.

``````class MyContainer(object):
def __init__(self, iterable=None):
if iterable is not None:
self.data = list(iterable)
else:
self.data = []
def walk_container(self, f):
for x in self.data:
print(f(x))
def _increment(self, x):
return x + 1
def print_increments(self):
self.walk_container(self._increment)

c = MyContainer([10,31,42])
c.print_increments()``````

Output

``````10
31
42``````
##### How to Sort a Linked List in Alphabetical Order in Python?
``````def sort(self):

prev = None
while current != None:
self._next = current.next
current.next = prev
prev = current
current = self._next

temp = None
else:
return temp

while curr != None:
ascn.next = curr
ascn = ascn.next
curr = curr.next
if curr != None:
dscn.next = curr
dscn = dscn.next
curr = curr.next
ascn.next = None
dscn.next = None

llist.printList()
llist.sort()
llist.printList()``````

Output

``````Given linked list
a
hello
bat
pythonwife
website
tech
python

a
bat
hello
python
pythonwife
tech
website``````
##### How to Make an Empty Linked List in Python?

The Empty linked list is created by not inserting any elements into the list.

``````    class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None

def __init__(self):
def listprint(self):
while printval is not None:
print (printval.dataval)
printval = printval.nextval

list.listprint()``````

Output

``None``
##### How to Check if an Element is in a Linked List using Python?

The `search() `user-defined function is used to traverse through the list and search for the elements.

``````def search(self, x):
while current != None:
if current.data == x:
return True
current = current.next

return False
if __name__ == '__main__':
llist.push('hello');
llist.push(30);
llist.push('python wife');
llist.push(21);
llist.push(14);
if llist.search('hello'):
print("Yes the item is present")
else:
if llist.search('hi'):
print("Yes the item is present")
else:

Output

``````Yes the item is present
##### What does Iterator Do in Linked List in Python?

The python has an inbuilt function called `iter() `which can be used to iterate through the linked list. The `next()` function will call the next element in the list.

``````iterable_value = ['Python','Wife','Website','Technology','Knowledge']
iterable_obj = iter(iterable_value)
while True:
try:
item = next(iterable_obj)
print(item)
except StopIteration:
break``````

Output

``````Python
Wife
Website
Technology
Knowledge``````
##### How to make a Doubly Linked List in Python?

The doubly linked list can be traversed in a backward direction thus making insertion and deletion operations easier to perform.

``````class Node:
def __init__(self,data):
self.data = data;
self.previous = None;
self.next = None;

def __init__(self):
newNode = Node(data);
self.tail.next = None;
else:
self.tail.next = newNode;
newNode.previous = self.tail;
self.tail = newNode;
self.tail.next = None;

def display(self):
print("List is empty");
return;
print("Nodes of doubly linked list: ");
while(current != None):
print(current.data),;
current = current.next;

dList.display(); ``````

Output

``````Nodes of doubly linked list:
Hello
Welcome
3
Pythonwife
5``````
##### How to Delete a Node in Linked List using Python?

The linked list is traversed through and the element to be deleted is found. Once found the node is removed and the next pointer is made to point to the next following element.

``````def deleteNode(self, key):
if (temp is not None):
if (temp.data == key):
temp = None
return
while(temp is not None):
if temp.data == key:
break
prev = temp
temp = temp.next
if(temp == None):
return
prev.next = temp.next
temp = None

llist.push(4)
llist.push(10)
llist.push(34)
llist.push(21)
llist.printList()
llist.deleteNode(4)
print ("\nLinked List after Deletion of 4 :")
llist.printList()``````

Output

``````Linked List:
21
34
10
4

Linked List after Deletion of 4 :
21
34
10``````
##### How to Delete the Last Node in the Linked List using Python?

The secondlast node is used to traverse through the linked list till the second last element. Then the last node, which is the next node of the secondlast node is deleted.

``````import sys
import math
return None
return None
while(second_last.next.next):
second_last = second_last.next
second_last.next = None

if __name__=='__main__':

Output

``8 23 11 29 ``
##### How to Loop Through Elements of Linked List in Python?

In the linked list both for loop and while loop can be used to traverse through the list.

``````   def append_item(self, data):
#Append items on the list
node = Node(data)
else:
self.tail = node
self.count += 1

def iterate_item(self):
# Iterate the list.
current_item = self.tail
while current_item:
val = current_item.data
current_item = current_item.next
yield val

items.append_item('Welcome')
items.append_item('You')
items.append_item('All')
items.append_item('To')
items.append_item('Pythonwife')
items.append_item('Website')
print("list:")
for val in items.iterate_item():
print(val)``````

Output

``````list:
Welcome
You
All
To
Pythonwife
Website``````
##### How to Convert an Array List into Linked List in Python?

We build a node in a linked list for each element of an array `arr[] `and insert it at the end.

``````import math
def display(root):
while (root != None) :
print(root.data, end = " ")
root = root.next

def ConvertarrayToList(arr, n):
root = None
for i in range(0, n, 1):
root = insert(root, arr[i])
return root

if __name__=='__main__':
arr = [10, 20, 30, 40, 50]
n = len(arr)
root = ConvertarrayToList(arr, n)
display(root)``````

Output

``10 20 30 40 50 ``
##### How to Implement Deque Singly Linked List in Python?

The enqueue and dequeue operations are performed on the singly linked list.

``````class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.next = None

class Queue:
rear = None
front = None

def dequeue(self):
if self.front is None:
print("Queue Underflow")
exit(1)
temp = self.front
print("Removing…", temp.data)
self.front = self.front.next
if self.front is None:
self.rear = None
item = temp.data
return item

def enqueue(self, item):
node = Node(item)
print("Inserting…", item)
if self.front is None:
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node

def peek(self):
if self.front:
return self.front.data
else:
exit(1)
return -1
def isEmpty(self):
return self.rear is None and self.front is None

if __name__ == '__main__':
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
print("The front element is", q.peek())
q.dequeue()
q.dequeue()
if q.isEmpty():
print("The queue is empty")
else:
print("The queue is not empty")``````

Output

``````Inserting… 1
Inserting… 2
Inserting… 3
Inserting… 4
The front element is 1
Removing… 1
Removing… 2
The queue is not empty``````
##### How to Find the Length of a Singly Linked List in Python?

The variable count is incremented till the node becomes null.

``````def getCount(self):
count = 0
while (temp):
count += 1
temp = temp.next
return count

if __name__=='__main__':
llist.push(1)
llist.push(3)
llist.push(1)
llist.push(2)
llist.push(1)
print ("length of singly linked list is :",llist.getCount())``````

Output

``length of singly linked list is : 5``
##### How to Insert an Element at a Specific Position in Linked List using Python?

Up to position-1 nodes, traverse the Linked list. Allocate memory and the specified data to the new node once all of the position-1 nodes have been traversed. Point the new node’s next pointer to the current node’s next pointer. Point the current node’s next pointer to the new node.

``````  def push_at(self, newElement, position):
newNode = Node(newElement)
if(position < 1):
print("\nposition should be >= 1.")
elif (position == 1):
else:
for i in range(1, position-1):
if(temp != None):
temp = temp.next
if(temp != None):
newNode.next = temp.next
temp.next = newNode
else:
print("\nThe previous node is null.")

#Add three elements at the end of the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.PrintList()
#Insert an element at position 2
MyList.push_at(100, 2)
MyList.PrintList()
#Insert an element at position 1
MyList.push_at(200, 1)``````

Output

``````The list contains: 10 20 30
The list contains: 10 100 20 30
The list contains: 200 10 100 20 30 ``````
##### Why Does a Linked List Return None in Python?

It is possible to reach the end of next without a return statement, any Python function will return None.

``````class FindOdd:
def __init__(self,end):
self.__start = 1
self.__end = end
def __iter__(self):
return OddsIterator(self.__end)

class OddsIterator:
def __init__(self,finish):
self.__current = 0
self.__step = 1
self.__end = finish
def __next__(self):
x = None
if self.__current > self.__end:
raise StopIteration
else:
self.__current += self.__step
if (self.__current - self.__step + 1) % 2 != 0:
x = self.__current - self.__step + 1
if x != None:
return x

odds = FindOdd(2)
print(list(odds))``````

Output

``[1, None, 3]``
##### How to Find the Smallest Element in the Linked List using Python?

The linked list is traversed until the head is not NULL, and the min variable is set to INT MIN. Then, if the min value is larger than the head value, the head value is assigned to the min node; otherwise, the head point is to the next node. This method should be repeated until the head is not equal to NULL.

``````def smallestElement(head):
min = 32767
return min

print("None")

push( 15)
push( 14)
push( 13)
push( 22)
push( 17)
print("Minimum element in linked list: ",end="")

Output

``````Linked list is :
17 -> 22 -> 13 -> 14 -> 15 -> None
Minimum element in linked list: 13``````
##### How to Concatenate Two Linked Lists in Python?

The dummy node is created, which initially points to some node when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’ and adding it to the tail.

``````def mergeLists(headA, headB):
dummyNode = Node(0)
tail = dummyNode
while True:
break
break
else:
tail = tail.next
return dummyNode.next

print("List A : ")
listA.printList()
print("\nList B : ")
listB.printList()
listA.printList()``````

Output

``````List A :
50 120 115
List B :
2 60 205
2 50 60 115 120 205 ``````
##### How to Add an Element to the End of a Linked List in Python?

The user-defined `push_back()` function is used to add elements to the end of the linked list.

``````  def push_back(self, newElement):
newNode = Node(newElement)
return
else:
while(temp.next != None):
temp = temp.next
temp.next = newNode

def PrintList(self):
if(temp != None):
print("The list contains:", end=" ")
while (temp != None):
print(temp.data, end=" ")
temp = temp.next
print()
else:
print("The list is empty.")

MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.PrintList()``````

Output

``The list contains: 10 20 30 ``
##### How to Append to the Linked List in Python?

The user-defined function` append_element()` can be used to append elements to the linked list.

``````    def append_element(self, data):
#Append items on the list
node = Node(data)
if self.tail:
self.tail.next = node
self.tail = node
else:
self.tail = node
self.count += 1

items.append_element('C')
items.append_element('Python')
items.append_element('C#')
items.append_element('C++')
items.append_element('HTML')
for val in items.iterate_item():
print(val)``````

Output

``````C
Python
C#
C++
HTML``````

The characters can be added to the linked list, by passing the character as the node to the` append() `and `push() `functions.

``````	def push(self, new_data):
new_node = Node(new_data)

def append(self, new_data):
new_node = Node(new_data)
return
while (last.next):
last = last.next
last.next = new_node

if __name__=='__main__':
llist.append('a')
llist.push('z');
llist.push('x');
llist.append('p')
llist.printList()``````

Output

``````Created linked list is:
x
z
a
p``````
##### How to Move the Elements of the Linked List in Python?

Traverse down the list until you reach the last node. Use two pointers: one for the final node’s address and the other for the second last node’s address. Do the following activities after the loop has ended.

• Set `secLast->next = NULL` to make the second last the last.
• Use `last->next = *head` ref as the head .
• Assign the last position as the head (`*head ref = last`).
``````	def moveToFront(self):
sec_last = None
if not tmp or not tmp.next:
return
while tmp and tmp.next :
sec_last = tmp
tmp = tmp.next
sec_last.next = None

if __name__ == '__main__':
llist.push("Website")
llist.push("Pythonwife")
llist.push("to")
llist.push("all")
llist.push("Welcome")
print ("Before moving ")
llist.printList()
llist.moveToFront()
print ("After moving")
llist.printList()``````

Output

```Before moving
Welcome, all, to, Pythonwife, Website,
After moving
Website, Welcome, all, to, Pythonwife, ```
##### How to Remove a Node from the Linked List using Python?

Locate the previous node of the to-be-deleted node. Change the preceding node’s next node. To delete a node, the memory of the node is freed.

``````	def removeNode(self, key):
if (temp is not None):
if (temp.data == key):
temp = None
return
while(temp is not None):
if temp.data == key:
break
prev = temp
temp = temp.next
if(temp == None):
return
prev.next = temp.next
temp = None
def printList(self):
while(temp):
print (" %d" %(temp.data)),
temp = temp.next

llist.push(70)
llist.push(231)
llist.push(36)
llist.push(24)
llist.printList()
llist.removeNode(231)
print ("\nLinked List after Deletion of 231:")
llist.printList()``````

Output

``````Created Linked List:
24
36
231
70

Linked List after Deletion of 231:
24
36
70``````
##### How to Remove Duplicate Nodes in an Unsorted Linked List using Python?

The user-defined` removeduplicate()` function that takes a list as an argument and deletes any duplicate node from the list can be used to remove duplicate nodes in an unsorted linked list.

``````	def removeduplicate(self):
ptr1 = None
ptr2 = None
dup = None
while (ptr1 != None and ptr1.next != None):
ptr2 = ptr1
while (ptr2.next != None):
if (ptr1.data == ptr2.next.data):
dup = ptr2.next
ptr2.next = ptr2.next.next
else:
ptr2 = ptr2.next
ptr1 = ptr1.next

print("Before removing duplicates :")
list.printList()
list.removeduplicate()
print()
print("After removing duplicates :")
list.printList()``````

Output

``````Before removing duplicates :
10 12 11 11 110 12 10

After removing duplicates :
10 12 11 110 ``````
##### how to merge two unsorted linked lists in python

The dummy node is created, which initially points to some node when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’ and adding it to the tail.

``````def mergeLists(headA, headB):
dummyNode = Node(0)
tail = dummyNode
while True:
break
break
else:
tail = tail.next
return dummyNode.next

print("List A : ")
listA.printList()
print("\nList B : ")
listB.printList()
listA.printList()``````

Output

``````List A :
50 120 115
List B :
2 60 205
2 50 60 115 120 205 ``````
##### How to Iterate the Linked Lists Backwards in Python?

The head pointer is passed to this method as a node. Check if the next node of a node is Null: If yes, we have reached the end of the linked list. Set the head pointer to this node. If no, pass the next node of the node to the `reversetraverse()` method.

``````	def reversetraverse(self):
prev = None
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next

llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
llist.printList()
llist.reversetraverse()
llist.printList()``````

Output

``````Given Linked List
85
15
4
20

20
4
15
85``````
##### How to Know if a Linked List has a Loop in Python?

To detect if a linked list has a loop or not hashing approach can be used. In hashing method, The list is traversed and the node address is added to the hash table. If NULL is reached at any time, return false; otherwise, return true if the next of the current nodes points to any of the previously recorded nodes in Hash.

``````	def findLoop(self):
s = set()
while (temp):
if (temp in s):
return True
temp = temp.next
return False

llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)
if(llist.findLoop()):
print("Loop found")
else:
print("No Loop ")``````

Output

``Loop found``
##### How To Return a Linked List in Python?

Like any other data linked list can also be returned from the function.

``````def returnlist():
x=[1,2,3,4]
return x
print(returnlist())``````

Output

``[1, 2, 3, 4]``
##### How to Index a Linked List in Python?

The Linked List is traversed through and the count variable is used to keep track of the index of the element.

``````    def findIndex(self, x):
count = 0
while current != None:
if current.data == x:
print("Index of 21 is ",count)
return True
count++
current = current.next
return False

if __name__ == '__main__':
llist.push(10);
llist.push(30);
llist.push(11);
llist.push(21);
llist.push(14);

if llist.search(21):
print("Yes")
else:
print("No")``````

Output

``````Index of 21 is 1
Yes``````
##### How to Traverse the Linked List in Python?

The while loop can be used to traverse through the linked list.

``````def printList(self):
while node_print is not None:
print (node_print.value)
node_print = node_print.next

sll.push(20)
sll.push(4)
sll.push(15)
sll.push(10)
sll.printList()``````

Output

``````20
4
15
10``````
##### How to Interleave Two Linked Lists in Python?
``````class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next

def make_list(elements):
for element in elements[1:]:
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)

print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')

class Solution:
def solve(self, l1, l2):
ans = l1
while l2:
if ans:
if ans.next != None:
newnode = ListNode(l2.val, None)
newnode.next = ans.next
ans.next = newnode
ans = newnode.next
l2 = l2.next
else:
ans.next = l2
return l2
else:
return l1

ob = Solution()
l1 = make_list([5,4,6,3,4,7])
l2 = make_list([8,6,9])
res = ob.solve(l1,l2)
print_list(res)``````

Output

``[5, 8, 4, 6, 6, 9, 3, 4, 7, ]``
##### How To Make a List that has Some Words Linked Together in Python?

The list has some words can be linked together using List comprehension.

``````test_list = ['Python', '52', 'wife', '93', 'Website' , '12', '35']
print("The given list : " + str(test_list))
res = [''.join([i for i in test_list if not i.isdigit()]),
*[j for j in test_list if j.isdigit()]]
print("The joined adjacent words : " + str(res))``````

Output

``````The given list : ['Python', '52', 'wife', '93', 'Website', '12', '35']
The joined adjacent words : ['PythonwifeWebsite', '52', '93', '12', '35']``````
##### How to Insert an Array in Linked List using Python?

The array is passed as a node to `push() `and `append() `function to insert it into a linked list.

``````	def push(self, new_data):
new_node = Node(new_data)

def append(self, new_data):
new_node = Node(new_data)
return
while (last.next):
last = last.next
last.next = new_node

if __name__=='__main__':
llist.append(6)
llist.push(7);
llist.push([1,2]);
llist.append([9,7])
llist.printList()``````

Output

``````Created linked list is:
[1, 2]
7
8
6
[9, 7]``````
##### How to Implement a Stack using a Linked List in Python?

In stack Implementation using Linked List, a stack contains a top pointer. This is the head of the stack, where items are pushed and popped at the top of the list. The first node’s link field is null, the second node’s link field is the first node’s address, and so on, with the last node’s address in the top pointer.

``````class Node:

# Class to create nodes of linked list
# constructor initializes node automatically
def __init__(self,data):
self.data = data
self.next = None
class Stack:
def __init__(self):
def isempty(self):
return True
else:
return False

def push(self,data):
else:
newnode = Node(data)

def pop(self):
if self.isempty():
return None
else:
poppednode.next = None
return poppednode.data

def peek(self):
if self.isempty():
return None
else:

def display(self):
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return

MyStack = Stack()
MyStack.push(11)
MyStack.push(22)
MyStack.push(54)
MyStack.push(34)
MyStack.display()
print("\nTop",MyStack.peek())
MyStack.pop()
MyStack.pop()
MyStack.display()
print("\nTop ", MyStack.peek())``````

Output

``````34 -> 54 -> 22 -> 11 ->
Top 34
22 -> 11 ->
Top  22``````
##### How to Search a Linked List in Another Linked List in Python?

The user-defined `search_list()` function can be used to search a linked list in another linked list.

``````def searchList(first, second):
if not first and not second:
return True
if not first or not second:
return False
ptr1 = first
ptr2 = second
while ptr2:
ptr2 = second
while ptr1:
if not ptr2:
return False
elif ptr1.value == ptr2.value:
ptr1 = ptr1.next
ptr2 = ptr2.next
else:
break
if not ptr1:
return True
ptr1 = first
second = second.next
return False

node_a = Node(16)
node_a.next = Node(2)
node_a.next.next = Node(30)
node_a.next.next.next = Node(49)
node_b = Node(19)
node_b.next = Node(20)
node_b.next.next = Node(16)
node_b.next.next.next = Node(2)
node_b.next.next.next.next = Node(30)
node_b.next.next.next.next.next = Node(49)
if searchList(node_a, node_b):
print("LIST FOUND")
else:
``LIST FOUND``