How to create a Linked List in PythonA linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain. Show Linked lists are preferred over arrays due to their dynamic size and ease of insertion and deletion properties. The head pointer points to the first node, and the last element of the list points to null. When the list is empty, the head pointer points to null. Linked lists in PythonOriginal Python does not ship with a built-in linked list data structure like the one seen in Java. Lets see how we can create our own implementation of a standard class-based singly linked list in Python. 1. Start with a single nodeLets start with a single node since linking several nodes gives us a complete list. For this, we make a Node class that holds some data and a single pointer next, that will be used to point to the next Node type object in the Linked List. # A single node of a singly linked list
class Node:
# constructor
def __init__(self, data, next=None):
self.data = data
self.next = next
# Creating a single node
first = Node(3)
print(first.data) Run 2. Join nodes to get a linked listThe next step is to join multiple single nodes containing data using the next pointers, and have a single head pointer pointing to a complete instance of a Linked List. Using the head pointer, we will be able to traverse the whole list, even perform all kinds of list manipulations while we are at it. For this, we create a LinkedList class with a single head pointer: # A single node of a singly linked list
class Node:
# constructor
def __init__(self, data = None, next=None):
self.data = data
self.next = next
# A Linked List class with a single head node
class LinkedList:
def __init__(self):
self.head = None
# Linked List with a single node
LL = LinkedList()
LL.head = Node(3)
print(LL.head.data) Run 3. Add required methods to the LinkedList classLast but not least, we can add various linked list manipulation methods in our implementation. Lets have a look at the insertion and print methods for our LinkedList implementation below: # A single node of a singly linked list
class Node:
# constructor
def __init__(self, data = None, next=None):
self.data = data
self.next = next
# A Linked List class with a single head node
class LinkedList:
def __init__(self):
self.head = None
# insertion method for the linked list
def insert(self, data):
newNode = Node(data)
if(self.head):
current = self.head
while(current.next):
current = current.next
current.next = newNode
else:
self.head = newNode
# print method for the linked list
def printLL(self):
current = self.head
while(current):
print(current.data)
current = current.next
# Singly Linked List with insertion and print methods
LL = LinkedList()
LL.insert(3)
LL.insert(4)
LL.insert(5)
LL.printLL() Run |