How to Add Nodes to Linked Lists in Python
This post discusses how to add nodes to a linked list as well as display the contents of a linked list in Python.
While linked lists are mainly associated with pointers, a concept that has direct usage in python, this post deals with basic methods on linked lists just to understand algorithmic concepts. It may be interesting to note that python variables for most data-types are actually internally treated as pointers!
Prerequisites: Basics of Python classes and objects
What are Linked Lists?
Linked lists are basically individual elements, called nodes, holding some data that are linked with one or more other nodes to form a complete sequence. It is obvious, therefore, that they’re implemented using pointers.
For a more detailed explanation, refer to this.
NOTE: The implementation here does not use the LList mentioned in the above link. Also, this post deals with singly-linked lists
Add to Linked Lists – Nodes
To add nodes to a linked list is to attach a new node to an existing linked list. New nodes may be added to a linked list at the beginning, at the end or somewhere in the middle (in here, it in a sorted linked list).
Consider the following program,
class Node: def __init__(self,val,link): self.data = val self.next = link start = None end = None #Variables to hold first, last nodes def CreateNewNode(value): #Data to be stored in new node newNode = Node(value,None) return newNode def AddToBegin(nod): #The node to be added global start global end if not start: start = nod end = nod else: nod.next = start start = nod def AddToEnd(nod): global start global end if not end: start = nod end = nod else: end.next = nod end = nod def AddToSorted(nod): #Sorted in Ascending Order global start global end if not start: start = nod end = nod else: if start.data>=nod.data: #Add go beginning nod.next = start start = nod else: temp = start flag = False while temp.next: if temp.next.data>=nod.data: nod.next = temp.next temp.next = nod flag = True break else: temp = temp.next if not flag: end.next = nod #Add to end end = nod def Display(): global start global end temp = start print "START","->", while temp: print temp.data,"->", temp = temp.next print "END"
Add Nodes to Linked List at Beginning in Python
Adding node to the beginning is simply to check if it is the first element (if start is None) and add it as the first node and make start and end, both point to this new node. Otherwise, we make the existing first element as the next of the new node and make the start point to the new node.
Add to Linked List at End in Python
Adding to the end of the list is to first again check if this is the first element (if end is None) and add it as the end as well as start node (the one and only node). Otherwise, we simply make the new node as the next of the existing end node and then make endpoint to the new node.
Add to Linked List in Ascending Sorted
Adding to sorted, we first check if it is the first element and perform the same operation as in the above cases. If not, we check whether it is lesser than the first element. If so, we add it to the beginning as in case 1. Otherwise, we start a while loop. We keep checking to find the first node that has data greater than or equal to the new node. Note that we do this process on temp.next and not on temp itself. That’s because, in order to insert, we’ll need the node located previous to the firsts greater node we found!
When found, we make the new node point to this first greater node. Then make its previous node point to the new node, hence re-establishing the links to include the new node between the first greater node and its previous node.
Displaying the List
This is one of the simplest processes. We simply start a while loop, reassigning the temp variable to the next node and display the contents of temp until temp becomes None. That is because, after we display the last node, its next will hold None. Therefore, it indicates that the linked list has ended and so should the loop.
Creating A New Node in Linked List in Python
While creating a new node, we take the next element of the new node as None by default. We leave it up to the inserting functions to take care of assigning a logical value to this attribute. The data passed to this function is assigned to the data attribute. The node so created is returned by the function.
NOTE: If we keep adding to in a sorted manner to a Linked List from start, it will remain sorted. But using any other function to add, in between, will disrupt that order.
So that’s about adding and displaying nodes in a linked list.