Python – Heaps ”; Previous Next Heap is a special tree structure in which each parent node is less than or equal to its child node. Then it is called a Min Heap. If each parent node is greater than or equal to its child node then it is called a max heap. It is very useful is implementing priority queues where the queue item with higher weightage is given more priority in processing. A detailed discussion on heaps is available in our website here. Please study it first if you are new to heap data structure. In this chapter we will see the implementation of heap data structure using python. Create a Heap A heap is created by using python’s inbuilt library named heapq. This library has the relevant functions to carry out various operations on heap data structure. Below is a list of these functions. heapify − This function converts a regular list to a heap. In the resulting heap the smallest element gets pushed to the index position 0. But rest of the data elements are not necessarily sorted. heappush − This function adds an element to the heap without altering the current heap. heappop − This function returns the smallest data element from the heap. heapreplace − This function replaces the smallest data element with a new value supplied in the function. Creating a Heap A heap is created by simply using a list of elements with the heapify function. In the below example we supply a list of elements and the heapify function rearranges the elements bringing the smallest element to the first position. Example import heapq H = [21,1,45,78,3,5] # Use heapify to rearrange the elements heapq.heapify(H) print(H) Output When the above code is executed, it produces the following result − [1, 3, 5, 78, 21, 45] Inserting into heap Inserting a data element to a heap always adds the element at the last index. But you can apply heapify function again to bring the newly added element to the first index only if it smallest in value. In the below example we insert the number 8. Example import heapq H = [21,1,45,78,3,5] # Covert to a heap heapq.heapify(H) print(H) # Add element heapq.heappush(H,8) print(H) Output When the above code is executed, it produces the following result − [1, 3, 5, 78, 21, 45] [1, 3, 5, 78, 21, 45, 8] Removing from heap You can remove the element at first index by using this function. In the below example the function will always remove the element at the index position 1. Example import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Remove element from the heap heapq.heappop(H) print(H) Output When the above code is executed, it produces the following result − [1, 3, 5, 78, 21, 45] [3, 21, 5, 78, 45] Replacing in a Heap The heap replace function always removes the smallest element of the heap and inserts the new incoming element at some place not fixed by any order. Example import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Replace an element heapq.heapreplace(H,6) print(H) Output When the above code is executed, it produces the following result − [1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45] Print Page Previous Next Advertisements ”;
Category: python Data Structure
Python – Recursion
Python – Recursion ”; Previous Next Recursion allows a function to call itself. Fixed steps of code get executed again and again for new values. We also have to set criteria for deciding when the recursive call ends. In the below example we see a recursive approach to the binary search. We take a sorted list and give its index range as input to the recursive function. Binary Search using Recursion We implement the algorithm of binary search using python as shown below. We use an ordered list of items and design a recursive function to take in the list along with starting and ending index as input. Then, the binary search function calls itself till find the searched item or concludes about its absence in the list. Example def bsearch(list, idx0, idxn, val): if (idxn < idx0): return None else: midval = idx0 + ((idxn – idx0) // 2) # Compare the search item with middle most value if list[midval] > val: return bsearch(list, idx0, midval-1,val) else if list[midval] < val: return bsearch(list, midval+1, idxn, val) else: return midval list = [8,11,24,56,88,131] print(bsearch(list, 0, 5, 24)) print(bsearch(list, 0, 5, 51)) Output When the above code is executed, it produces the following result − 2 None Print Page Previous Next Advertisements ”;
Python – Algorithm Design
Python – Algorithm Design ”; Previous Next Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. From the data structure point of view, following are some important categories of algorithms − Search − Algorithm to search an item in a data structure. Sort − Algorithm to sort items in a certain order. Insert − Algorithm to insert item in a data structure. Update − Algorithm to update an existing item in a data structure. Delete − Algorithm to delete an existing item from a data structure. Characteristics of an Algorithm Not all procedures can be called an algorithm. An algorithm should have the following characteristics − Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. Input − An algorithm should have 0 or more well-defined inputs. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output. Finiteness − Algorithms must terminate after a finite number of steps. Feasibility − Should be feasible with the available resources. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code. How to Write an Algorithm? There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code. As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm. We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution. Example Let”s try to learn algorithm-writing by using an example. Problem − Design an algorithm to add two numbers and display the result. step 1 − START step 2 − declare three integers a, b & c step 3 − define values of a & b step 4 − add values of a & b step 5 − store output of step 4 to c step 6 − print c step 7 − STOP Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be written as − step 1 − START ADD step 2 − get values of a & b step 3 − c ← a + b step 4 − display c step 5 − STOP In design and analysis of algorithms, usually the second method is used to describe an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can observe what operations are being used and how the process is flowing. Writing step numbers, is optional. We design an algorithm to get a solution of a given problem. A problem can be solved in more than one ways. Hence, many solution algorithms can be derived for a given problem. The next step is to analyze those proposed solution algorithms and implement the best suitable solution. Print Page Previous Next Advertisements ”;
Python – Queue
Python – Queue ”; Previous Next We are familiar with queue in our day to day life as we wait for a service. The queue data structure aslo means the same where the data elements are arranged in a queue. The uniqueness of queue lies in the way items are added and removed. The items are allowed at on end but removed form the other end. So it is a First-in-First out method. A queue can be implemented using python list where we can use the insert() and pop() methods to add and remove elements. Their is no insertion as data elements are always added at the end of the queue. Adding Elements In the below example we create a queue class where we implement the First-in-First-Out method. We use the in-built insert method for adding data elements. Example class Queue: def __init__(self): self.queue = list() def addtoq(self,dataval): # Insert method to add element if dataval not in self.queue: self.queue.insert(0,dataval) return True return False def size(self): return len(self.queue) TheQueue = Queue() TheQueue.addtoq(“Mon”) TheQueue.addtoq(“Tue”) TheQueue.addtoq(“Wed”) print(TheQueue.size()) Output When the above code is executed, it produces the following result − 3 Removing Element In the below example we create a queue class where we insert the data and then remove the data using the in-built pop method. Example class Queue: def __init__(self): self.queue = list() def addtoq(self,dataval): # Insert method to add element if dataval not in self.queue: self.queue.insert(0,dataval) return True return False # Pop method to remove element def removefromq(self): if len(self.queue)>0: return self.queue.pop() return (“No elements in Queue!”) TheQueue = Queue() TheQueue.addtoq(“Mon”) TheQueue.addtoq(“Tue”) TheQueue.addtoq(“Wed”) print(TheQueue.removefromq()) print(TheQueue.removefromq()) Output When the above code is executed, it produces the following result − Mon Tue Print Page Previous Next Advertisements ”;
Python – Binary Tree
Python – Binary Tree ”; Previous Next Tree represents the nodes connected by edges. It is a non-linear data structure. It has the following properties − One node is marked as Root node. Every node other than the root is associated with one parent node. Each node can have an arbiatry number of chid node. We create a tree data structure in python by using the concept os node discussed earlier. We designate one node as root node and then add more nodes as child nodes. Below is program to create the root node. Create Root We just create a Node class and add assign a value to the node. This becomes tree with only a root node. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data def PrintTree(self): print(self.data) root = Node(10) root.PrintTree() Output When the above code is executed, it produces the following result − 10 Inserting into a Tree To insert into a tree we use the same node class created above and add a insert class to it. The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally the PrintTree class is used to print the tree. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): # Compare the new value with the parent node if self.data: if data self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Use the insert method to add nodes root = Node(12) root.insert(6) root.insert(14) root.insert(3) root.PrintTree() Output When the above code is executed, it produces the following result − 3 6 12 14 Traversing a Tree The tree can be traversed by deciding on a sequence to visit each node. As we can clearly see we can start at a node then visit the left sub-tree first and right sub-tree next. Or we can also visit the right sub-tree first and left sub-tree next. Accordingly there are different names for these tree traversal methods. Tree Traversal Algorithms Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree. In-order Traversal Pre-order Traversal Post-order Traversal In-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the In-order traversal logic is implemented by creating an empty list and adding the left node first followed by the root or parent node. At last the left node is added to complete the In-order traversal. Please note that this process is repeated for each sub-tree until all the nodes are traversed. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Inorder traversal # Left -> Root -> Right def inorderTraversal(self, root): res = [] if root: res = self.inorderTraversal(root.left) res.append(root.data) res = res + self.inorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.inorderTraversal(root)) Output When the above code is executed, it produces the following result − [10, 14, 19, 27, 31, 35, 42] Pre-order Traversal In this traversal method, the root node is visited first, then the left subtree and finally the right subtree. In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the Pre-order traversal logic is implemented by creating an empty list and adding the root node first followed by the left node. At last, the right node is added to complete the Pre-order traversal. Please note that, this process is repeated for each sub-tree until all the nodes are traversed. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Preorder traversal # Root -> Left ->Right def PreorderTraversal(self, root): res = [] if root: res.append(root.data) res = res + self.PreorderTraversal(root.left) res = res + self.PreorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.PreorderTraversal(root)) Output When the above code is executed, it produces the following result − [27, 14, 10, 19, 35, 31, 42] Post-order Traversal In this traversal method, the root node is visited last, hence the name. First,
Python – Search Tree
Python – Search Tree ”; Previous Next A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties.The left sub-tree of a node has a key less than or equal to its parent node”s key.The right sub-tree of a node has a key greater than to its parent node”s key.Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree left_subtree (keys) ≤ node (key) ≤ right_subtree (keys) Search for a value in a B-tree Searching for a value in a tree involves comparing the incoming value with the value exiting nodes. Here also we traverse the nodes from left to right and then finally with the parent. If the searched for value does not match any of the exiting value, then we return not found message, or else the found message is returned. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert method to create nodes def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # findval method to compare the value with nodes def findval(self, lkpval): if lkpval < self.data: if self.left is None: return str(lkpval)+” Not Found” return self.left.findval(lkpval) else if lkpval > self.data: if self.right is None: return str(lkpval)+” Not Found” return self.right.findval(lkpval) else: print(str(self.data) + ” is found”) # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() root = Node(12) root.insert(6) root.insert(14) root.insert(3) print(root.findval(7)) print(root.findval(14)) Output When the above code is executed, it produces the following result − 7 Not Found 14 is found Print Page Previous Next Advertisements ”;
Python – Algorithm Classes
Python – Algorithm Classes ”; Previous Next Algorithms are unambiguous steps which should give us a well-defined output by processing zero or more inputs. This leads to many approaches in designing and writing the algorithms. It has been observed that most of the algorithms can be classified into the following categories. Greedy Algorithms Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions. However, generally greedy algorithms do not provide globally optimized solutions. So greedy algorithms look for a easy solution at that point in time without considering how it impacts the future steps. It is similar to how humans solve problems without going through the complete details of the inputs provided. Most networking algorithms use the greedy approach. Here is a list of few of them − Travelling Salesman Problem Prim”s Minimal Spanning Tree Algorithm Kruskal”s Minimal Spanning Tree Algorithm Dijkstra”s Minimal Spanning Tree Algorithm Divide and Conquer This class of algorithms involve dividing the given problem into smaller sub-problems and then solving each of the sub-problem independently. When the problem can not be further sub divided, we start merging the solution to each of the sub-problem to arrive at the solution for the bigger problem. The important examples of divide and conquer algorithms are − Merge Sort Quick Sort Kruskal”s Minimal Spanning Tree Algorithm Binary Search Dynamic Programming Dynamic programming involves dividing the bigger problem into smaller ones but unlike divide and conquer it does not involve solving each sub-problem independently. Rather the results of smaller sub-problems are remembered and used for similar or overlapping sub-problems. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems.Dynamic algorithms are motivated for an overall optimization of the problem and not the local optimization. The important examples of Dynamic programming algorithms are − Fibonacci number series Knapsack problem Tower of Hanoi Print Page Previous Next Advertisements ”;
Python – Linked Lists
Python – Linked Lists ”; Previous Next A linked list is a sequence of data elements, which are connected together via links. 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. We implement the concept of linked lists using the concept of nodes as discussed in the previous chapter. We have already seen how we create a node class and how to traverse the elements of a node.In this chapter we are going to study the types of linked lists known as singly linked lists. In this type of data structure there is only one link between any two data elements. We create such a list and create additional methods to insert, update and remove elements from the list. Creation of Linked list A linked list is created by using the node class we studied in the last chapter. We create a Node object and create another class to use this ode object. We pass the appropriate values through the node object to point the to the next data elements. The below program creates the linked list with three data elements. In the next section we will see how to traverse the linked list. class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None list1 = SLinkedList() list1.headval = Node(“Mon”) e2 = Node(“Tue”) e3 = Node(“Wed”) # Link first Node to second node list1.headval.nextval = e2 # Link second Node to third node e2.nextval = e3 Traversing a Linked List Singly linked lists can be traversed in only forward direction starting form the first data element. We simply print the value of the next data element by assigning the pointer of the next node to the current data element. Example 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(“Mon”) e2 = Node(“Tue”) e3 = Node(“Wed”) # Link first Node to second node list.headval.nextval = e2 # Link second Node to third node e2.nextval = e3 list.listprint() Output When the above code is executed, it produces the following result − Mon Tue Wed Insertion in a Linked List Inserting element in the linked list involves reassigning the pointers from the existing nodes to the newly inserted node. Depending on whether the new data element is getting inserted at the beginning or at the middle or at the end of the linked list, we have the below scenarios. Inserting at the Beginning This involves pointing the next pointer of the new data node to the current head of the linked list. So the current head of the linked list becomes the second data element and the new node becomes the head of the linked list. Example class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None # Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval def AtBegining(self,newdata): NewNode = Node(newdata) # Update the new nodes next val to existing node NewNode.nextval = self.headval self.headval = NewNode list = SLinkedList() list.headval = Node(“Mon”) e2 = Node(“Tue”) e3 = Node(“Wed”) list.headval.nextval = e2 e2.nextval = e3 list.AtBegining(“Sun”) list.listprint() Output When the above code is executed, it produces the following result − Sun Mon Tue Wed Inserting at the End This involves pointing the next pointer of the the current last node of the linked list to the new data node. So the current last node of the linked list becomes the second last data node and the new node becomes the last node of the linked list. Example class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None # Function to add newnode def AtEnd(self, newdata): NewNode = Node(newdata) if self.headval is None: self.headval = NewNode return laste = self.headval while(laste.nextval): laste = laste.nextval laste.nextval=NewNode # Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval list = SLinkedList() list.headval = Node(“Mon”) e2 = Node(“Tue”) e3 = Node(“Wed”) list.headval.nextval = e2 e2.nextval = e3 list.AtEnd(“Thu”) list.listprint() Output When the above code is executed, it produces the following result − Mon Tue Wed Thu Inserting in between two Data Nodes This involves changing the pointer of a specific node to point to the new node. That is possible by passing in both the new node and the existing node after which the new node will be inserted. So we define an additional class which will change the next pointer of the new node to the next pointer of middle node. Then assign the new node to next pointer of the middle node. class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None class SLinkedList: def __init__(self): self.headval = None # Function to add node def Inbetween(self,middle_node,newdata): if middle_node is None: print(“The mentioned node is absent”) return NewNode = Node(newdata) NewNode.nextval = middle_node.nextval middle_node.nextval = NewNode # Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval list = SLinkedList() list.headval = Node(“Mon”) e2 = Node(“Tue”) e3 = Node(“Thu”) list.headval.nextval = e2 e2.nextval = e3 list.Inbetween(list.headval.nextval,”Fri”) list.listprint() Output When the above code is executed, it produces the following result − Mon Tue Fri Thu Removing an Item We can remove
Python – Graph Algorithms
Python – Graph Algorithms ”; Previous Next Graphs are very useful data structures in solving many important mathematical challenges. For example computer network topology or analysing molecular structures of chemical compounds. They are also used in city traffic or route planning and even in human languages and their grammar. All these applications have a common challenge of traversing the graph using their edges and ensuring that all nodes of the graphs are visited. There are two common established methods to do this traversal which is described below. Depth First Traversal Also called depth first search (DFS),this algorithm traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. We implement DFS for a graph in python using the set data types as they provide the required functionalities to keep track of visited and unvisited nodes. Example class graph: def __init__(self,gdict=None): if gdict is None: gdict = {} self.gdict = gdict # Check for the visisted and unvisited nodes def dfs(graph, start, visited = None): if visited is None: visited = set() visited.add(start) print(start) for next in graph[start] – visited: dfs(graph, next, visited) return visited gdict = { “a” : set([“b”,”c”]), “b” : set([“a”, “d”]), “c” : set([“a”, “d”]), “d” : set([“e”]), “e” : set([“a”]) } dfs(gdict, ”a”) Output When the above code is executed, it produces the following result − a b d e c Breadth First Traversal Also called breadth first search (BFS),this algorithm traverses a graph breadth ward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration. Please visit this link in our website to understand the details of BFS steps for a graph. We implement BFS for a graph in python using queue data structure discussed earlier. When we keep visiting the adjacent unvisited nodes and keep adding it to the queue. Then we start dequeue only the node which is left with no unvisited nodes. We stop the program when there is no next adjacent node to be visited. Example import collections class graph: def __init__(self,gdict=None): if gdict is None: gdict = {} self.gdict = gdict def bfs(graph, startnode): # Track the visited and unvisited nodes using queue seen, queue = set([startnode]), collections.deque([startnode]) while queue: vertex = queue.popleft() marked(vertex) for node in graph[vertex]: if node not in seen: seen.add(node) queue.append(node) def marked(n): print(n) # The graph dictionary gdict = { “a” : set([“b”,”c”]), “b” : set([“a”, “d”]), “c” : set([“a”, “d”]), “d” : set([“e”]), “e” : set([“a”]) } bfs(gdict, “a”) Output When the above code is executed, it produces the following result − a c b d e Print Page Previous Next Advertisements ”;
Python – Advanced Linked list ”; Previous Next We have already seen Linked List in earlier chapter in which it is possible only to travel forward. In this chapter we see another type of linked list in which it is possible to travel both forward and backward. Such a linked list is called Doubly Linked List. Following is the features of doubly linked list. Doubly Linked List contains a link element called first and last. Each link carries a data field(s) and two link fields called next and prev. Each link is linked with its next link using its next link. Each link is linked with its previous link using its previous link. The last link carries a link as null to mark the end of the list. Creating Doubly linked list We create a Doubly Linked list by using the Node class. Now we use the same approach as used in the Singly Linked List but the head and next pointers will be used for proper assignation to create two links in each of the nodes in addition to the data present in the node. Example class Node: def __init__(self, data): self.data = data self.next = None self.prev = None class doubly_linked_list: def __init__(self): self.head = None # Adding data elements def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Print the Doubly Linked list def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.push(8) dllist.push(62) dllist.listprint(dllist.head) Output When the above code is executed, it produces the following result − 62 8 12 Inserting into Doubly Linked List Here, we are going to see how to insert a node to the Doubly Link List using the following program. The program uses a method named insert which inserts the new node at the third position from the head of the doubly linked list. Example # Create the Node class class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Create the doubly linked list class doubly_linked_list: def __init__(self): self.head = None # Define the push method to add elements def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Define the insert method to insert the element def insert(self, prev_node, NewVal): if prev_node is None: return NewNode = Node(NewVal) NewNode.next = prev_node.next prev_node.next = NewNode NewNode.prev = prev_node if NewNode.next is not None: NewNode.next.prev = NewNode # Define the method to print the linked list def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.push(8) dllist.push(62) dllist.insert(dllist.head.next, 13) dllist.listprint(dllist.head) Output When the above code is executed, it produces the following result − 62 8 13 12 Appending to a Doubly linked list Appending to a doubly linked list will add the element at the end. Example # Create the node class class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # Create the doubly linked list class class doubly_linked_list: def __init__(self): self.head = None # Define the push method to add elements at the begining def push(self, NewVal): NewNode = Node(NewVal) NewNode.next = self.head if self.head is not None: self.head.prev = NewNode self.head = NewNode # Define the append method to add elements at the end def append(self, NewVal): NewNode = Node(NewVal) NewNode.next = None if self.head is None: NewNode.prev = None self.head = NewNode return last = self.head while (last.next is not None): last = last.next last.next = NewNode NewNode.prev = last return # Define the method to print def listprint(self, node): while (node is not None): print(node.data), last = node node = node.next dllist = doubly_linked_list() dllist.push(12) dllist.append(9) dllist.push(8) dllist.push(62) dllist.append(45) dllist.listprint(dllist.head) Output When the above code is executed, it produces the following result − 62 8 12 9 45 Please note the position of the elements 9 and 45 for the append operation. Print Page Previous Next Advertisements ”;