**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.

**Table of Contents**

### Linked Lists vs Arrays

Linked List | Array |

Linked lists have a dynamic size, i.e., they can be changed at runtime. | The size of an array can not be altered at runtime. |

Memory is allocated at runtime. | Memory is allocated at the time of compilation. |

The linked list uses more memory as each node holds a reference to the next one as well. | For the same number of elements, arrays use less memory. |

Accessing elements is more time consuming | Accessing elements is less time consuming |

Operations such as insertion/deletion are faster. | Operations such as insertion/deletion are slower. |

### Types of Linked Lists

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

**Singly Linked List****Circular Singly Linked List****Doubly Linked List****Circular Doubly Linked List**

### Singly Linked List

**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.

### Circular Singly 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.

### Doubly 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 List

**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
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
singlyll = SinglyLinkedList() #Initializing object of singly linked list
temp_node1 = Node(10)
temp_node2 = Node(20)
singlyll.head = temp_node1
singlyll.head.next = temp_node2
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):
node = self.head
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
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
#Function to add node in the beginning
def atBeg(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
#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)
if self.head is None:
self.head = new_node
self.tail = new_node
return
last_node = self.head
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
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def printList(self):
node_print = self.head
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
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def searchList(self, value):
position = 0
found = 0
if self.head is None:
print ("The linked list does not exist")
else:
temp_node = self.head
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
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
#Function to delete node from the beginning
def delBeg(self):
if(self.head == None):
return
elif(self.head.next == self.tail.next):
self.head = self.tail = None
return
elif (self.head is not None):
temp_node = self.head
self.head = self.head.next
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):
temp_head = self.head
if (temp_head is not None):
if (temp_head.value == del_value):
self.head = temp_head.next
temp_head = None
return
while (temp_head is not None):
if temp_head.value == del_value:
break
prev = temp_head
temp_head = temp_head.next
if (temp_head == None):
return
prev.next = temp_head.next
temp_head = None
#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):
if(self.head == None):
return
elif (self.head.next == self.tail.next):
self.head = self.tail = None
return
else:
temp_node = self.head
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
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def delSLL(self):
if self.head is None:
print("The singly linked list does not exist.")
else:
self.head = None
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.

### Time Complexity of Linked List vs Array

Operations | Array | Linked List |
---|---|---|

Creation | O(1) | O(1) |

Insertion at beginning | O(1) | O(1) |

Insertion in between | O(1) | O(1) |

Insertion at end | O(1) | O(n) |

Searching in Unsorted Data | O(n) | O(n) |

Searching in Sorted Data | O(logn) | O(n) |

Traversal | O(n) | O(n) |

Deletion at beginning | O(1) | O(1) |

Deletion in between | O(1) | O(n)/O(1) |

Deletion at end | O(1) | O(n) |

Deletion of entire linked list/array | O(1) | O(n)/O(1) |

Accessing elements | O(1) | O(n) |

### 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
def removeDuplicates(linkedList):
if linkedList.head is None:
return
else:
current_node = linkedList.head
visited = set([current_node.value])
while current_node.next:
if current_node.next.value in visited:
current_node.next = current_node.next.next
else:
visited.add(current_node.next.value)
current_node = current_node.next
return linkedList
```

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
def kthToLast(linkedList, k):
first_pointer = linkedList.head
second_pointer = linkedList.head
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'
def partition(linkedList, x):
current_node = linkedList.head
linkedList.tail = linkedList.head
while current_node:
next_node = current_node.next
current_node.next = None
if current_node.value < x:
current_node.next = linkedList.head
linkedList.head = current_node
else:
linkedList.tail.next = current_node
linkedList.tail = current_node
current_node = current_node.next
if linkedList.tail.next is not None:
linkedList.tail.next = None
#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
def sumList(linkedList1, linkedList2):
num1 = linkedList1.head
num2 = linkedList2.head
carry = 0
newLL = SinglyLinkedList()
while num1 or num2:
result = carry
if num1:
result += num1.value
num1 = num1.next
if num2:
result += num2.value
num2 = num2.next
newLL.add(int(result % 10))
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
def intersection(linkedList1, linkedList2):
if linkedList1.tail is not linkedList2.tail:
return False
lenA = len(linkedList1)
lenB = len(linkedList2)
shorter = linkedList1 if lenA < lenB else linkedList2
longer = linkedList2 if lenA < lenB else linkedList1
diff = len(longer) - len(shorter)
longer_node = longer.head
shorter_node = shorter.head
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
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Monday")
day2 = Node("Tuesday")
day3 = Node("Wednesday")
list.headval.nextval = day2
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):
self.head = None
def reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
llist = LinkedList()
llist.push(200)
llist.push(40)
llist.push(175)
llist.push(85)
print("Given Linked List")
llist.printList()
llist.reverse()
print("\nReversed Linked List")
llist.printList()
```

**Output**

```
Given Linked List
85
175
40
200
Reversed Linked List
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
class LinkedList:
def __init__(self):
self.head = None
def insert(self, data):
newNode = Node(data)
if(self.head):
current = self.head
while(current.next):
current = current.next
current.next = newNode
else:
self.head = newNode
def printLL(self):
current = self.head
while(current):
print(current.data)
current = current.next
LL = LinkedList()
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 = []
head = node
while node:
values.append(node.val)
node = node.next
values.sort()
values = collections.deque(values)
node = head
while node:
node.val = values.popleft()
node = node.next
return head
ob = Solution()
head = make_list([5, 8, 41, 21, 5, 60, 3])
print_list(ob.solve(head))
```

**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
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Monday")
day2 = Node("Tuesday")
day3 = Node("Wednesday")
list.headval.nextval = day2
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):
if head is None:
return headRef
first = head
rest = first.next
if rest is None:
headRef = first
return headRef
headRef = reverse(rest, headRef)
rest.next = first
first.next = None
return headRef
def reverseList(head):
return reverse(head, head)
if __name__ == '__main__':
head = None
for i in reversed(range(6)):
head = Node(i + 1, head)
head = reverseList(head)
printList(head)
```

**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):
Ahead = self.Node(0)
Dhead = self.Node(0)
self.splitList(Ahead, Dhead)
Ahead = Ahead.next
Dhead = Dhead.next
Dhead = self.reverseList(Dhead)
self.head = self.mergeList(Ahead, Dhead)
def reverseList(self, Dhead):
current = Dhead
prev = None
while current != None:
self._next = current.next
current.next = prev
prev = current
current = self._next
Dhead = prev
return Dhead
def mergeList(self, head1, head2):
if head1 == None:
return head2
if head2 == None:
return head1
temp = None
if head1.data < head2.data:
temp = head1
head1.next = self.mergeList(head1.next, head2)
else:
temp = head2
head2.next = self.mergeList(head1, head2.next)
return temp
def splitList(self, Ahead, Dhead):
ascn = Ahead
dscn = Dhead
curr = self.head
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 = LinkedList()
llist.head = llist.newNode('a')
llist.head.next = llist.newNode('hello')
llist.head.next.next = llist.newNode('bat')
llist.head.next.next.next = llist.newNode('pythonwife')
llist.head.next.next.next.next = llist.newNode('website')
llist.head.next.next.next.next.next = llist.newNode('tech')
llist.head.next.next.next.next.next.next = llist.newNode('python')
print('Given linked list')
llist.printList()
llist.sort()
print('Sorted linked list')
llist.printList()
```

**Output**

```
Given linked list
a
hello
bat
pythonwife
website
tech
python
Sorted linked list
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
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node()
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):
current = self.head
while current != None:
if current.data == x:
return True
current = current.next
return False
if __name__ == '__main__':
llist = LinkedList()
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:
print("No the item is not found")
if llist.search('hi'):
print("Yes the item is present")
else:
print("No the item is not found")
```

**Output**

```
Yes the item is present
No the item is not found
```

##### 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;
class DoublyLinkedList:
def __init__(self):
self.head = None;
def addNode(self, data):
newNode = Node(data);
if(self.head == None):
self.head = self.tail = newNode;
self.head.previous = None;
self.tail.next = None;
else:
self.tail.next = newNode;
newNode.previous = self.tail;
self.tail = newNode;
self.tail.next = None;
def display(self):
current = self.head;
if(self.head == None):
print("List is empty");
return;
print("Nodes of doubly linked list: ");
while(current != None):
print(current.data),;
current = current.next;
dList = DoublyLinkedList();
dList.addNode("Hello");
dList.addNode("Welcome");
dList.addNode(3);
dList.addNode("Pythonwife");
dList.addNode(5);
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):
temp = self.head
if (temp is not None):
if (temp.data == key):
self.head = temp.next
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 = LinkedList()
llist.push(4)
llist.push(10)
llist.push(34)
llist.push(21)
print ("Linked List: ")
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
def removeLastNode(head):
if head == None:
return None
if head.next == None:
head = None
return None
second_last = head
while(second_last.next.next):
second_last = second_last.next
second_last.next = None
return head
if __name__=='__main__':
head = None
head = push(head, 12)
head = push(head, 29)
head = push(head, 11)
head = push(head, 23)
head = push(head, 8)
head = removeLastNode(head)
while(head):
print("{} ".format(head.data), end ="")
head = head.next
```

**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)
if self.head:
self.head.next = node
self.head = node
else:
self.tail = node
self.head = 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 = singly_linked_list()
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):
temp = self.head
count = 0
while (temp):
count += 1
temp = temp.next
return count
if __name__=='__main__':
llist = LinkedList()
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):
newNode.next = self.head
self.head = newNode
else:
temp = self.head
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.")
MyList = LinkedList()
#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
while (head != None) :
if (min > head.data) :
min = head.data
head = head.next
return min
def printList( head) :
while (head != None) :
print(head.data ,end= " -> ")
head = head.next
print("None")
push( 15)
push( 14)
push( 13)
push( 22)
push( 17)
print("Linked list is : ")
printList(head)
print("Minimum element in linked list: ",end="")
print(smallestElement(head),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:
if headA is None:
tail.next = headB
break
if headB is None:
tail.next = headA
break
if headA.data <= headB.data:
tail.next = headA
headA = headA.next
else:
tail.next = headB
headB = headB.next
tail = tail.next
return dummyNode.next
listA = LinkedList()
listB = LinkedList()
listA.addToList(50)
listA.addToList(120)
listA.addToList(115)
print("List A : ")
listA.printList()
listB.addToList(2)
listB.addToList(60)
listB.addToList(205)
print("\nList B : ")
listB.printList()
listA.head = mergeLists(listA.head, listB.head)
print("\nMerged Linked List is:")
listA.printList()
```

**Output**

```
List A :
50 120 115
List B :
2 60 205
Merged Linked List is:
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)
if(self.head == None):
self.head = newNode
return
else:
temp = self.head
while(temp.next != None):
temp = temp.next
temp.next = newNode
def PrintList(self):
temp = self.head
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 = LinkedList()
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.head = node
self.tail = node
self.count += 1
items = singly_linked_list()
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
```

##### How to Add Characters to Linked List in Python?

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)
new_node.next = self.head
self.head = new_node
def append(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node
if __name__=='__main__':
llist = LinkedList()
llist.append('a')
llist.push('z');
llist.push('x');
llist.append('p')
print ('Created linked list is:')
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):
tmp = self.head
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
tmp.next = self.head
self.head = tmp
if __name__ == '__main__':
llist = LinkedList()
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):
temp = self.head
if (temp is not None):
if (temp.data == key):
self.head = temp.next
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):
temp = self.head
while(temp):
print (" %d" %(temp.data)),
temp = temp.next
llist = LinkedList()
llist.push(70)
llist.push(231)
llist.push(36)
llist.push(24)
print ("Created Linked List: ")
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
ptr1 = self.head
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
list = LinkedList()
list.head = Node(10)
list.head.next = Node(12)
list.head.next.next = Node(11)
list.head.next.next.next = Node(11)
list.head.next.next.next.next = Node(110)
list.head.next.next.next.next.next = Node(12)
list.head.next.next.next.next.next.next = Node(10)
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:
if headA is None:
tail.next = headB
break
if headB is None:
tail.next = headA
break
if headA.data <= headB.data:
tail.next = headA
headA = headA.next
else:
tail.next = headB
headB = headB.next
tail = tail.next
return dummyNode.next
listA = LinkedList()
listB = LinkedList()
listA.addToList(50)
listA.addToList(120)
listA.addToList(115)
print("List A : ")
listA.printList()
listB.addToList(2)
listB.addToList(60)
listB.addToList(205)
print("\nList B : ")
listB.printList()
listA.head = mergeLists(listA.head, listB.head)
print("\nMerged Linked List is:")
listA.printList()
```

**Output**

```
List A :
50 120 115
List B :
2 60 205
Merged Linked List is:
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
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
print ("Given Linked List")
llist.printList()
llist.reversetraverse()
print ("\nReversed Linked List")
llist.printList()
```

**Output**

```
Given Linked List
85
15
4
20
Reversed Linked List
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()
temp = self.head
while (temp):
if (temp in s):
return True
s.add(temp)
temp = temp.next
return False
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)
llist.head.next.next.next.next = llist.head
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):
current = self.head
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 = LinkedList()
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):
node_print = self.head
while node_print is not None:
print (node_print.value)
node_print = node_print.next
sll = LinkedList()
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):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
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)
new_node.next = self.head
self.head = new_node
def append(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node
if __name__=='__main__':
llist = LinkedList()
llist.append(6)
llist.push(7);
llist.push([1,2]);
llist.append([9,7])
print ('Created linked list is:')
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):
self.head = None
def isempty(self):
if self.head == None:
return True
else:
return False
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
def pop(self):
if self.isempty():
return None
else:
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
def display(self):
iternode = self.head
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:
print("LIST NOT FOUND")
```

**Output**

`LIST FOUND`