Singly linked list: Create and Traverse Python Program

Python program to create and traverse singly linked list

  In this tutorial, we are going to learn the python program to create a singly linked list and traverse its elements.

Problem Statement

Our program will take the elements of the linked list from the user as the input and then print the elements of the linked list.

For example

Case1: If the user inputs the elements of the linked list as 1, 2, 3, 4.

                    The output should be 1234.

Case2: If the user inputs the elements of the linked list as 7, 9, 1, 0.

                    The output should be 7910.

What is a Linked List?

               A linked list is the collection of elements that are connected via the memory address of successor elements. It is an unordered collection of data that is connected via links. Each data elements have another block that contains the address of the next elements of the linked list.

Creation Of Linked List:

Python linked list traversal

        The singly linked list is a linear records shape wherein every element of the listing incorporates a pointer which factors to the following detail inside the listing. Each element within the singly connected list is referred to as a node. Each node has two components: data and next pointer, which factors the following node within the listing. The first node of the list is the head, and the closing node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be linearly accessed with the help of traversing through the list from head to tail. The linked list is created using the node class. We create a node object and another class to use this node object.

Traversal of a linked list

               Traversing is the most common operation of the linked list, it means visiting every node of the linked list once and performing any operation usually, we insert, delete or display the elements of the linked list. For traversing basic idea is to visit every node from head to the null value.

Our Logic to create and traverse singly linked list

  • Our program will take a list of elements as input from the user.
  • Store the elements inputs by the user in linked list format(Linked list creation)
  • Traverse through each element of the linked list and print the elements as the output (Traverse of linked list)

Algorithm to create and traverse singly linked list

Step1: Create a node class having two attributes data and next. The next attribute is a pointer to the next node.

Step2: Create another class having attributes head and tail.

Step3: addNode() function will add a new node to the linked list.

i. Create a new node

ii. Check, if the head is empty, i.e. if the head is equal to null.

iii. If the head is empty, then both head and tail will point to the newly created node.

iv. If the head is not empty, then the newly created node is added to the end of the list. Then tail will point to the newly created node and the newly created node will become the tail of the linked list.

Step 4: show() function will traverse the elements of the linked list and display the elements.

i. Assign a new node that is pointing to the head node.

ii. Traverse through the list till current pointing to is null.

iii. Print each node.

Let’s code the above algorithm in the python programming language.

Python Program to create and traverse singly linked list

Output 1:

create singly linked list in python

Explanations

For the input size 4, the data elements of the linked list are input as 1, 2, 3, and 4. The elements are connected using the pointer which is the pointer to the next node.

1–>2–>3–>4–>Null

Output 2:

traverse singly linked list in python

Explanations

For the input size 7, the data elements of the linked list are input as 90, 87, 65, 22, 87, 0, and 19. The elements are connected using the pointer which is the pointer to the next node.

90–>87–>65–>22–>87–>0–>19–>Null