Dremendo Tag Line
Python Programming Tutorial

Doubly Linked List in Python Programming

User-Defined Data Structures in Python

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

What is Doubly Linked List in Python

Just like Singly Linked List, a Doubly Linked List in python is a user-defined data structure in which data is stored as an object called a node. Each node has three parts in a doubly linked list: the data, the previous, and the next.

The data part stores the data, the previous part stores the memory address of the previous node, and the next part holds the memory address of the next node, as shown in the image below.

python doubly linked list

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

The first node has three parts: the data, the prev and the next. The prev and the next parts stores the memory address of the previous and next nodes.

In a doubly 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 Doubly Linked List Program

Below we have given the complete structure of a doubly 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.prev = None
        self.next = None

start = None
newnode = None
temp = None
rn = 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 doubly 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 previous and next node, as shown below.

Example

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

In the above code, Node is the name of a class. It contains three instance variables data to store the number, prev and next to store the memory address of the previous and next node objects.

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
temp = None
rn = 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.
  • temp will store the address of a selected node for temporary purpose. 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.
  • 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.prev = None     # assign the None in the previous 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
    newnode.prev = rn   # newnode->prev = recent node

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.prev = None     # assign the None in the previous 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
            rn.prev=newnode             # recent node->prev = newnode
            start=newnode	        # start = new node
            f=1
            break

        elif start is not rn and rn.data==x:    # insert before recent node
            newnode.next=rn	                # newnode->next = recent node
            newnode.prev=rn.prev                # newnode->prev = recent node->prev
            newnode.prev.next=newnode           # newnode->prev->next = newnode
            rn.prev=newnode		        # recent node->prev = 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

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.prev = None     # assign the None in the previous 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 and rn.next==None:              # insert after recent node
            newnode.prev=rn         # newnode->prev = recent node
            rn.next=newnode	    # recent node->next = newnode
            f=1
            break
        elif rn.data==x and rn.next is not None:
            newnode.next=rn.next		# newnode->next = recent node->next
            newnode.next.prev=newnode	        # new node->next->previous = newnode
            newnode.prev=rn	                # new node->previous = recent node
            rn.next=newnode 	                # recent node->next = new node
            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
            rn.next.prev=None   # recent node->next->prev = None
            del(rn)             # delete the recent node
            f=1
            print('Number Deleted Successfully')
            break

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

        elif rn.next==None and rn.data==x:
            # delete the last node
            rn.prev.next=None           # recent node->prev->next = None
            del(rn)
            f=1
            print('Number Deleted Successfully')
            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

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

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

    # 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.