One can learn the basics of Linked List from the following video tutorial:
Here’s a program which implements Singly Linked Lists in python:
The first and the foremost thing is that we must represent a node of a list. Here’s a representation of a node:
#class for defining a Node in a list
class Node(object):
def __init__(self,value,nextNode=None):
self.value = value
self.next = nextNode
The value field consists the value assigned to the node, and the next field consists the reference to the next node.
After this we need to create the Linked List class which actually holds the nodes and operates on them. The following class represents Linked Lists and the its basic operations:
#class for defining a linked list
class LinkedList(object):
#initializing a list
def __init__(self):
self.length = 0
self.head = None
#method to add a node in the linked list
def addNode(self,node):
if self.length == 0:
self.addBeg(node)
else:
self.addLast(node)
#method to add a node at the beginning of the list with a value
def addBeg(self,node):
newNode = node
newNode.next = self.head
self.head = newNode
self.length += 1
#method to add a node after the node having the value=value1. The value of the new node is value2
def addAfterValue(self,value1,node):
newNode = node
currentnode = self.head
while currentnode.next != None or currentnode.value != value1:
if currentnode.value == value1:
newNode.next = currentnode.next
currentnode.next = newNode
self.length = self.length + 1
return
else:
currentnode = currentnode.next
print "The value provided is not present"
#method to add a node at a particular position
def addAtPos(self,pos,node):
count = 0
currentnode = self.head
previousnode = self.head
if pos > self.length or pos < 0:
print "The position does not exist. Please enter a valid position"
else:
while currentnode.next != None or count < pos:
count = count + 1
if count == pos:
previousnode.next = node
node.next = currentnode
self.length += 1
return
else:
previousnode = currentnode
currentnode = currentnode.next
#method to add a node at the end of a list
def addLast(self,node):
currentnode = self.head
while currentnode.next != None:
currentnode = currentnode.next
newNode = node
newNode.next = None
currentnode.next = newNode
self.length = self.length + 1
#method to delete the first node of the linked list
def deleteBeg(self):
if self.length == 0:
print "The list is empty"
else:
self.head = self.head.next
self.length -= 1
#method to delete the last node of the linked list
def deleteLast(self):
if self.length == 0:
print "The list is empty"
else:
currentnode = self.head
previousnode = self.head
while currentnode.next != None:
previousnode = currentnode
currentnode = currentnode.next
previousnode.next = None
self.length -= 1
#method to delete a node after the node having the given value
def deleteValue(self,value):
currentnode = self.head
previousnode = self.head
while currentnode.next != None or currentnode.value != value:
if currentnode.value == value:
previousnode.next = currentnode.next
self.length -= 1
return
else:
previousnode = currentnode
currentnode = currentnode.next
print "The value provided is not present"
#method to delete a node at a particular position
def deleteAtPos(self,pos):
count = 0
currentnode = self.head
previousnode = self.head
if pos > self.length or pos < 0:
print "The position does not exist. Please enter a valid position"
else:
while currentnode.next != None or count < pos:
count = count + 1
if count == pos:
previousnode.next = currentnode.next
self.length -= 1
return
else:
previousnode = currentnode
currentnode = currentnode.next
#returns the length of the list
def getLength(self):
return self.length
#returns the first element of the list
def getFirst(self):
if self.length == 0:
print "The list is empty"
else:
return self.head.value
#returns the last element of the list
def getLast(self):
if self.length == 0:
print "The list is empty"
else:
currentnode = self.head
while currentnode.next != None:
currentnode = currentnode.next
return currentnode.value
#returns node at any position
def getAtPos(self,pos):
count = 0
currentnode = self.head
if pos > self.length or pos < 0:
print "The position does not exist. Please enter a valid position"
else:
while currentnode.next != None or count < pos:
count = count + 1
if count == pos:
return currentnode.value
else:
currentnode = currentnode.next
#method to print the whole list
def print_list(self):
nodeList = []
currentnode = self.head
while currentnode!= None:
nodeList.append(currentnode.value)
currentnode = currentnode.next
print nodeList
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
ll = LinkedList()
ll.addNode(node1)
ll.addNode(node2)
ll.addNode(node3)
ll.addNode(node4)
ll.print_list()
#output = [1, 2, 3, 4]
node5 = Node(5)
ll.addAtPos(3,node5)
ll.print_list()
#Output = [1, 2, 5, 3, 4]
ll.deleteAtPos(2)
ll.print_list()
#Output = [1, 5, 3, 4]
codeatsociallywired 