Skip to main content

Python - Reversing a Singly Linked List

Program to vreate a Singly Linked List and then reverse its order.
Run the program here: https://repl.it/@VinitKhandelwal/ReverseSinglyLinkedList
class SinglyLinkedList:

def __init__(self):
self.reset()
def reset(self):
self.length = 0
self.head = None
self.tail = None

def first_node(self, new_node):
self.head = new_node
self.tail = self.head
self.length += 1

def append_non_first(self, new_node):
self.tail.front_pointer = new_node
self.tail = new_node
self.length += 1

def prepend_non_first(self, new_node):
new_node.front_pointer = self.head
self.head = new_node
self.length += 1

def append(self, value):
new_node = Node(value)
if self.length == 0:
self.first_node(new_node)
else:
self.append_non_first(new_node)

def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.first_node(new_node)
else:
self.prepend_non_first(new_node)

def insert_at(self, index, value):
new_node = Node(value)
if self.length == 0:
self.first_node(new_node)
elif index > self.length+1:
print("Index not available. Appended at the end.")
self.append_non_first(new_node)
else:
temp = self.head
if index == 0:
self.prepend_non_first(new_node)
elif index == self.length+1:
append_non_first(new_node)
else:
for i in range(0, index):
prev_temp = temp
temp = temp.front_pointer
prev_temp.front_pointer = new_node
new_node.front_pointer = temp
self.length += 1

def pop_front_non_first(self):
self.head = self.head.front_pointer
self.head.back_pointer = None
self.length -= 1

def pop_last_non_first(self):
prev_temp = self.head
for i in range(1, self.length):
temp = prev_temp.front_pointer
prev_temp = temp
prev_temp.front_pointer = None
self.length -= 1

def popfirst(self):
if self.length < 2:
self.reset()
else:
self.pop_front_non_first()

def poplast(self):
if self.length < 2:
self.reset()
else:
self.pop_last_non_first()

def delete_at(self, index):
if self.length < 2:
self.reset()
elif index == 0:
self.pop_front_non_first()
elif index == self.length-1:
self.pop_last_non_first()
elif index < self.length and index > 0:
temp = self.head
for i in range(0, index):
prev_temp = temp
temp = prev_temp.front_pointer
prev_temp.front_pointer = temp.front_pointer
self.length -= 1

def delete(self, value):
if self.length < 2:
if self.head.value == value:
self.reset()
else:
if self.head.value == value:
self.pop_front_non_first()
if self.tail.value == value:
self.pop_last_non_first()
prev_temp = self.head
for i in range(1, self.length-1):
temp = prev_temp.front_pointer
if temp.value == value:
prev_temp.front_pointer = temp.front_pointer
self.length -= 1
prev_temp = temp
def view(self):
print("View")
temp = None
arr = []
for i in range(0, self.length):
if temp == None:
temp = self.head
else:
temp = temp.front_pointer
if temp is not None:
arr.append(temp.value)
print(arr)

def reverse(self):
if self.length > 1:
second = self.head
first = second.front_pointer
second.front_pointer = None
for i in range(1, self.length-1): # 1,2,3 ,4,5,6,7,8
temp = first.front_pointer # next = <10><3><2>
first.front_pointer = second # <4-10><10-4><3-10>
second = first # prev_temp = <4><10>
first = temp # temp = <10><3>
temp = self.head # temp = <10>
self.head = self.tail # self.head = <10>
self.tail = temp # self.tail = <10>
self.head.front_pointer = second


class Node:
def __init__(self, value, front_pointer=None):
self.value = value
self.front_pointer = front_pointer


obj = SinglyLinkedList()
obj.view()
obj.prepend(10)
obj.view()
obj.append(1)
obj.view()
obj.append(10)
obj.view()
obj.prepend(2)
obj.view()
obj.insert_at(3, 7)
obj.view()
obj.prepend(3)
obj.view()
obj.prepend(10)
obj.view()
obj.prepend(4)
obj.view()
obj.prepend(10)
obj.view()
obj.reverse()
obj.view()
OUTPUT
View
[]
View
[10]
View
[10, 1]
View
[10, 1, 10]
View
[2, 10, 1, 10]
View
[2, 10, 1, 7, 10]
View
[3, 2, 10, 1, 7, 10]
View
[10, 3, 2, 10, 1, 7, 10]
View
[4, 10, 3, 2, 10, 1, 7, 10]
View
[10, 4, 10, 3, 2, 10, 1, 7, 10]
View
[10, 7, 1, 10, 2, 3, 10, 4, 10]

Comments

Popular posts from this blog

Python - Mathematical Functions - Hexadecimal, Binary, Exponential, Absolute, Round

🐍 Some mathematical functions are in-built in python. Here are some of them. Convert Decimal to Hexadecimal hex(246) Output: '0xf6' hex(512) Output: '0x200' 0x is prefix to all hexadecimal numbers in output. The number after 0x is the hexadecimal value. Convert Decimal to Binary bin(1234) Output: '0b10011010010' bin(246) Output: '0b11110110' bin(512) Output: '0b1000000000' Exponential Function pow() function is similar to num1**num2, but it comes useful when you want to execute (num1**num2)%num3. Passing three arguments to pow(), does this. pow(3,4) Output: 81 This works just like 3**4 pow(3,4,5) Output: 1 But this, works equivalent to (3**4)%5. Either of the two ways can be used. At this point I feel (3**4)%5 is better, as anybody reading the code will understand what is being done immediately. While with pow(2,3,4), the person may have to refer to documentation to understand how this function works. Absolute Value The function abs() is used ...

Two Ways of rendering in React Examples

Two Ways of rendering in React Examples 1 - Render twice HTML < div id = "p1" ></ div > < div id = "p2" ></ div > CSS . person { display : inline - block ; margin : 10px ; border : 1px solid # eee ; box - shadow : 0 2px 2px # ccc ; } JAVASCRIPT (Babel) function Person ( props ) { return ( < div className = ' person "> < h1 >{ props . name }</ h1 > < p > Age :{ props . age }</ p > </ div > ); } ReactDOM . render (< Person name = "VK" age = "29" />, document . querySselector ( '#p1' )); ReactDOM . render (< Person name = "HK" age = "28" />, document . querySselector ( '#p2' )); 2 Render all at once HTML < div id = "app" ></ div > CSS . person { display : inline - block ; margin : 1...

Binary Tree Traversal in Python - In Order, Pre Order, Post Order

Binary Tree Traversal in Python - In Order, Pre Order, Post Order Run the code here to see output:  https://repl.it/@VinitKhandelwal/iterative-traversal-of-binary-tree # Node Class to Create Object of Nodes class Node (): def __init__ ( self , value , left= None , right= None ): self .value = value self .left = left self .right = right # Creation of a Binary Tree class BinaryTree (): def __init__ ( self , mylist ): self .mylist = mylist self .root=Node ( None ) for value in self .mylist : self .curr= self .root self ._add ( value ) def _add ( self , value ): if self .curr.value == None : self .curr.value = value else : if self .curr.value > value : if self .curr.left == None : self .curr.left = Node ( value ) else : self .curr = self .curr.left self ._add ( value ) else : if self...