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.