Develop a Single Linked List Using Python

Original article was published by Abhayparashar31 on Artificial Intelligence on Medium


Hello there, I am Abhay

A linked list is a part of data structures. It is one of the most important data structures. In simple words, we can say that a linked list is a collection of nodes where each node is connected to some other node and the last node is connected to a Null pointer. Each Node Consist of two fields one is data and the other one is next. the data field contains the value of that node, whether the next contains the address of the next node. The last node contains the address of the null pointer.

There are three types of linked lists.

  1. Single Linked List
  2. Circular Linked List
  3. Doubly Linked List

In this blog, we are going to develop a single linked list.

Single Linked List is a type of linked list in data structures that is unidirectional mean it can only be traversed in one direction only. In a single lined list there can be multiple nodes connected to each other. the last node of a single linked is connected to a NULL pointer. The first node of the single linked list is connected to a start pointer which always points to the start location. The next part of each node contains the address of another node.

Single Linked List-Image By Author

We can Perform Two types of operation in a Single Linked List.
1. Insertion
2. Deletion

Insertion in a Single Linked List

Insertion means adding a new node to the linked list. In a Single Linked List, a node can be added to a linked list in three ways.

  1. At the end (append)
  2. At the start(prepend)
  3. At a Particular Position

Whenever we try to add a new node to the end of the linked list it is called append. Let’s take the example of our image, we have a new node E to be inserted in the list then we first break the connection between the D node next and Null Pointer, then we point the D next to E data and E next to Null.

NODE FIELD     NODE FIELD    OPERATION
D NEXT → NULL BREAK ##Break Connection
D NEXT → E DATA ADD ##ADD a new Connection
E NEXT → NULL ADD
“Insertion At Last-Image By Author”

When we try to add a node to the start of the linked list then we need to take the start pointer and make it point to the data field of new node and then new node next to our older head data field. In the case of our example if we have to add a new node E to the start of our linked list then we first take the start pointer and make it to point the new node E data field and then next of E to A data.

NODE FIELD     NODE FIELD    OPERATION
START → A DATA BREAK ##Break Connection
E NEXT → A DATA ADD ##ADD a new Connection
START → E DATA ADD
“Insertion At Start- Image By Author”

Now Let’s see what happens when we try to add a new node after a certain node then next of the previous node will point to the data of the new node and the next of new node will point to the next node data. In our example, if we try to add a new node E after A then the next of A will point to the data of E, and Next of E will point to Data of B, the connection between A next to B data get’s broken.

NODE FIELD     NODE FIELD    OPERATION
A NEXT → E DATA ADD
E NEXT → B DATA ADD ##ADD a new Connection
A NEXT → B DATA BREAk ##Break Connection
“Insertion After A Particular Node- Image By Author”