Linked list is a data structure which contains data objects which are connected by link. Each linked list consists of nodes which have a data field and a reference to the next node in the linked list. In this article, we will study the underlying concept behind linked list and will implement it in python.

## What is a node in a linked list?

A node is an object which has a data field and a pointer to another node in the linked list. A simple structure of a node can be shown in the following figure.

We can implement the above object using a class Node having two fields namely data and next as follows.

```
class Node:
def __init__(self,data):
self.data=data
self.next=None
```

A linked list consists of many such nodes. There is a head pointer in the linked list which points to the first node in the linked list or None when the linked list is empty. The following figure depicts a linked list having three nodes.

We can see that the next field of the last node points to None and the reference Head points to the first Node. An empty linked list will be a linked list having its head pointer pointing to None. An empty linked list can be created in python as follows.

```
class linkedList:
def __init__(self):
self.head=None
```

## Inserting an element to a linked list

We can insert an element in a linked list at the first position, in the last position on anywhere in between.

To insert an element in a linked list at the beginning, we will first create a node and with the given data and assign its next reference to the first node i.e where the head is pointing. Then we point the head reference to the new node.To perform this operation, we implement the method insertAtBeginning as follows.

```
def insertAtBeginning(self,data):
temp=Node(data)
if self.head==None:
self.head=temp
else:
temp.next=self.head
self.head=temp
```

To insert an element in a linked list at the end, we just have to find the node where the next element refers to None i.e. the last node. Then we create a new node with the given data and point the next element of the last node to the newly created node. To perform this operation, we implement the method insertAtEnd as follows.

```
def insertAtEnd(self,data):
temp=Node(data)
if self.head==None:
self.head=temp
else:
curr=self.head
while curr.next!=None:
curr=curr.next
curr.next=temp
```

To insert an element at any other given position, we can count the nodes till we reach that position and then we point the next element of the new node to the next node of the current node and the next reference of the current node to the new node. This can be implemented using the insertAtGivenPosition method as follows.

```
def insertAtGivenPosition(self,data,position):
count=1
curr=self.head
while count<position-1 and curr!=None:
curr=curr.next
count+=1
temp=Node(data)
temp.next=curr.next
curr.next=temp
```

## Traversing a linked list

To traverse a linked list in python, we will start from the head, print the data and move to the next node until we reach None i.e. end of the linked list. The following traverse() method implements the program to traverse a linked list in python.

```
def traverse(self):
curr=self.head
while curr!=None:
print(curr.data)
curr=curr.next
```

## Deleting a node

We can delete a node either from the start or end or in between two nodes of a linked list.

To delete the first node of a linked list, we will first check if the head of the linked list is pointing to None, if yes then we will raise an exception using python try except with a message that the linked list is empty. Otherwise, we will delete the current node referred by head and move the head pointer to the next node. This can be implemented as follows.

```
def delFromBeginning(self):
try:
if self.head==None:
raise Exception("Empty Linked List")
else:
temp=self.head
self.head=self.head.next
del temp
except Exception as e:
print(str(e))
```

To delete the last node of the linked list, we will traverse each node in the linked list and check if the next pointer of the next node of current node points to None,if yes then the next node of current node is the last node and it will get deleted. This can be implemented as follows.

```
def delFromEnd(self):
try:
if self.head==None:
raise Exception("Empty Linked List")
else:
curr=self.head
prev=None
while curr.next!=None:
prev=curr
curr=curr.next
prev.next=curr.next
del curr
except Exception as e:
print(str(e))
```

To delete a node in between the linked list, at every node we will check if the position of next node is the node to be deleted, if yes, we will delete the next node and assign the next reference to the next node of the node being deleted. This can be done as follows.

```
def delAtPos(self,position):
try:
if self.head==None:
raise Exception("Empty Linked List")
else:
curr=self.head
prev=None
count=1
while curr!=None and count<position:
prev=curr
curr=curr.next
count+=1
prev.next=curr.next
del curr
except Exception as e:
print(str(e))
```

Following is the working python code for implementation of linked list in python.

```
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 24 18:28:15 2021
@author: aditya1117
"""
class Node:
def __init__(self,data):
self.data=data
self.next=None
class linkedList:
def __init__(self):
self.head=None
def insertAtBeginning(self,data):
temp=Node(data)
if self.head==None:
self.head=temp
else:
temp.next=self.head
self.head=temp
def insertAtEnd(self,data):
temp=Node(data)
if self.head==None:
self.head=temp
else:
curr=self.head
while curr.next!=None:
curr=curr.next
curr.next=temp
def insertAtGivenPosition(self,data,position):
count=1
curr=self.head
while count<position-1 and curr!=None:
curr=curr.next
count+=1
temp=Node(data)
temp.next=curr.next
curr.next=temp
def traverse(self):
curr=self.head
while curr!=None:
print(curr.data)
curr=curr.next
def delFromBeginning(self):
try:
if self.head==None:
raise Exception("Empty Linked List")
else:
temp=self.head
self.head=self.head.next
del temp
except Exception as e:
print(str(e))
def delFromEnd(self):
try:
if self.head==None:
raise Exception("Empty Linked List")
else:
curr=self.head
prev=None
while curr.next!=None:
prev=curr
curr=curr.next
prev.next=curr.next
del curr
except Exception as e:
print(str(e))
def delAtPos(self,position):
try:
if self.head==None:
raise Exception("Empty Linked List")
else:
curr=self.head
prev=None
count=1
while curr!=None and count<position:
prev=curr
curr=curr.next
count+=1
prev.next=curr.next
del curr
except Exception as e:
print(str(e))
```

## Conclusion

In this article, we have studied about linked list and implemented it in python. You may have observed how linked lists are different from inbuilt data structures like python dictionary, list and set e.t.c. Please copy the working code and do experiments with it to gain more insight. Stay tuned for more informative articles.

## Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.