Dremendo Tag Line
Python Programming Tutorial

Singly Linked List in Python Programming

User-Defined Data Structures in Python

In this lesson, we will understand what is Singly Linked List in Python Programming and how to create them along with some examples.

What is Singly Linked List in Python

A Singly Linked List in Python is a user-defined data structure in which data is stored as an object called a node. Each node has two parts, the data, and the next part. The data part stores the data, and the next part stores the memory address of the next node, as shown in the image below.

python singly linked list

In the above image, the start is a variable that stores the memory address of the first node.

The first node has two parts: the data and the next. The next part stores the memory address of the next node.

In a singly linked list, data are not stored in a contagious memory location. A new node can be created anywhere in the memory at runtime.

We can create as many nodes as we want by linking the newly created node with the last node.

video-poster

Structure of a Singly Linked List Program

Below we have given the complete structure of a singly linked list program in python, along with all the operations we will perform.

Example

import os

# define node class
class Node:
    def __init__(self):
        self.data = 0
        self.next = None

start = None
newnode = None
nextnode = None
rn = None
pn = None
ch = None
n = None
x = None
c = None
f = None

while 1:
    os.system('cls')
    print('1. Add')
    print('2. Display')
    print('3. Insert Before')
    print('4. Insert After')
    print('5. Count')
    print('6. Search')
    print('7. Delete')
    print('8. Reverse')
    ch=int(input('Enter your choice '))

    if ch==1:       # for add operation
        pass

    elif ch==2:     # for display operation
        pass

    elif ch==3:     # for insert before operation
        pass

    elif ch==4:     # for insert after operation
        pass

    elif ch==5:     # for node count operation
        pass

    elif ch==6:     # for node serach operation
        pass

    elif ch==7:     # for delete operation
        pass

    elif ch==8:     # for reverse
        pass

    else:
        print('Invalid Choice')
        input('\nPress enter to continue...')     # Pause the loop so that the user can see the message Invalid Choice

The above program shows how a singly linked list program will look with all the operations on it. Now we will discuss each part of the above program and the program required to be written in each case for each individual operations like create, insert before, insert after and so on.

The pass statement is a placeholder for codes we will write later.

Define Node Class

So, first of all, we will define a node class that will store data and the address of the next node, as shown below.

Example

# define node class
class Node:
    def __init__(self):
        self.data = 0
        self.next = None

In the above code, Node is the name of a class. It contains two instance variables data to store the number and next to store the memory address of another node object.

Declare Variables

After defining the Node class, now we will declare the necessary variables required for our program as shown below

Example

start = None
newnode = None
nextnode = None
rn = None
pn = None
ch = None
n = None
x = None
c = None
f = None

The description of the above variables are as follows.

  • start will store the address of the first node in the memory. The default value is None.
  • newnode will store the address of newly created node.
  • nextnode will store the address of next node after the current node. This variable will be used to reverse the linked list.
  • rn will store the address of recent node. This variable will be used when we will read each node one by one.
  • pn will store the address of the previous node (node before the recent node).
  • ch will store the choice of the menu input by the user like 1, 2, 3, etc.
  • n will store the number input by the user and will be used later on in the program for various purposes.
  • x will store the number input by the user and will be used later on in the program for various purposes.
  • c will be used to count the total number of nodes present in the linked list.
  • f will be used to check if a node is found or not. When a node is found in the list the value of f will be 1 otherwise 0.

Add Operation (ch==1)

In the add operation, we will add a new node in the linked list using the program below.

Example

# Enter a number to store in node
n=int(input('Enter a number '))

# create a node object in newnode
newnode = Node()
newnode.data = n        # assign the value of n in the data part of newnode
newnode.next = None     # assign the None in the next part of newnode

if start == None:       # if start in None
    start = newnode     # then assing the newnode in start (start points to the first node in the memory)

else:
    rn = start          # if start is not NULL then assign start in rn to start reading from the first node

    # run a while loop until we find None in the next part of rn
    while rn.next is not None:
        rn = rn.next    # if rn->next part is not None then move to the next node
    rn.next = newnode   # when while loop ends, the rn stands at the last node and we assign the newnode in the next part of the rn

Display Operation (ch==2)

In the display operation, we will display all the nodes on the screen using the program below.

Example

if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:
    rn = start      # recent node

    # display the nodes on the screen
    while rn is not None:
        print(rn.data, end=' ')
        rn = rn.next

    input('\nPress enter to continue...')     # Pause the loop so that the user can see the nodes

Insert Before Operation (ch==3)

In the insert before operation, we will insert a new node before a selected node in the linked list using the program below.

Example

f=0
if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:
    n=int(input('Insert Number '))
    x=int(input('Insert Before '))

    # create a node object in newnode
    newnode = Node()
    newnode.data = n        # assign the value of n in the data part of newnode
    newnode.next = None     # assign the None in the next part of newnode

    # search number x in the list from the starting node
    rn = start      # recent node

    while rn is not None:
        if start==rn and rn.data==x:    # insert before first node
            newnode.next=rn	        # newnode->next = recent node
            start=newnode	        # start = new node
            f=1
            break

        elif start is not rn and rn.data==x:    # insert before recent node
            newnode.next=pn.next	        # newnode->next = previous node->next
            pn.next=newnode		        # previous node->next = newnode
            f=1
            break
        pn=rn           # previous node = recent node
        rn=rn.next      # recent node = recent node->next

    if f==0:
        print('Number not found')
        del(newnode)    # delete the newely created node
        input('Press enter to continue...')     # Pause the loop so that the user can see the above message Number not found

Insert After Operation (ch==4)

In the insert after operation, we will insert a new node after a selected node in the linked list using the program below.

Example

f=0
if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:
    n=int(input('Insert Number '))
    x=int(input('Insert After '))

    # create a node object in newnode
    newnode = Node()
    newnode.data = n        # assign the value of n in the data part of newnode
    newnode.next = None     # assign the None in the next part of newnode

    # search number x in the list from the starting node
    rn = start      # recent node

    while rn is not None:
        if rn.data==x:              # insert after recent node
            newnode.next=rn.next    # newnode->next = recent node->next
            rn.next=newnode	    # recent node->next = newnode
            f=1
            break
        rn=rn.next      # recent node = recent node->next

    if f==0:
        print('Number not found')
        del(newnode)    # delete the newely created node
        input('Press enter to continue...')     # Pause the loop so that the user can see the above message Number not found

Count Operation (ch==5)

In the count operation, we will count the total numbers of nodes present in the linked list using the program below.

Example

c=0
if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:
    #count from the first node till last node
    rn = start      # recent node

    while rn is not None:
        c=c+1
        rn=rn.next      # recent node = recent node->next
    print('Total Nodes = %d' %(c))
    input('Press enter to continue...')     # Pause the loop to see the total number of nodes

Search Operation (ch==6)

In the search operation, we will search if a given node is present in the linked list using the program below.

Example

f=0
c=0
if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:
    x=int(input('Enter Number to Search '))

    # search number x in the list from the starting node
    rn = start      # recent node

    while rn is not None:
        c=c+1   # count the numbers
        if rn.data==x:
            print('Number %d Found at Position %d' %(x,c))
            f=1
            break
        rn=rn.next      # recent node = recent node->next

    if f==0:
        print('Number not found')

    input('Press enter to continue...')     # Pause the loop to see search message

Delete Operation (ch==7)

In the delete operation, we will delete a given node from the linked list using the program below.

Example

f=0
if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:
    x=int(input('Enter Number to Delete '))

    # search number x in the list from the starting node
    rn = start      # recent node

    while rn is not None:
        if start==rn and rn.data==x:
            # delete the first node
            start=rn.next       # start = recent node->next
            del(rn)             # delete the recent node
            f=1
            print('Number Deleted Successfully')
            break

        elif start is not rn and rn.data==x:
            # delete the recent node
            pn.next=rn.next
            del(rn)
            f=1
            print('Number Deleted Successfully')
            break
        pn=rn           # previous node = recent node
        rn=rn.next      # recent node = recent node->next

    if f==0:
        print('Number not found')

    input('Press enter to continue...')     # Pause the loop to see search message

Reverse Operation (ch==8)

In the reverse operation, we will reverse the reading order of nodes in the linked list by changing their pointer direction using the program below.

Example

if start == None:
    print('List is empty')
    input('Press enter to continue...')     # Pause the loop so that the user can see the above message List is empty

else:

    rn = start      # recent node
    pn = None       # previous node = None

    while rn is not None:
        nextnode=rn.next		# nextnode = recent node->next
        rn.next=pn			# recent node->next = previous node
        pn=rn				# previous node = recent node
        rn=nextnode			# recent node = nextnode
    start=pn

    # print the reverse list
    rn = start      # recent node
    while rn is not None:
        print(rn.data, end=' ')
        rn = rn.next

    input('\nPress enter to continue...')     # Pause the loop so that the user can see the reverse nodes

Previous Next
Dremendo

For over a decade, Dremendo has been recognized for providing quality education. We proudly introduce our newly open online learning platform, which offers free access to popular computer courses.

Our Courses
News Updates
© 2024 Dremendo. All Rights Reserved.