LAB 08

Linked List and its Operation

in Python

________________________________________ __________ ___

STUDENT NAME ROLL NO SEC

_________________________________________________________
SIGNATURE & DATE

MARKS AWARDED: ______________

___________________________________________________________________
NATIONAL UNIVERSITY OF COMPUTER AND EMERGING SCIENCE
(NUCES) KARACHI

Prepared by: Engr. Syed Asim Mahmood Summer 2022

 LAB: 03LIST]
[LINKED LAB: 08

Lab Session 08: Linked List and its Operation in Python

OBJECTIVES:
A linked list is a linear data structure, in which the elements are not stored at
contiguous memory locations. The elements in a linked list are linked using pointers as
shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data
field and a reference (link) to the next node in the list.

What is a Node?
A linked list usually consists of a root node, allocated on the stack and one or more
nodes allocated on the heap (by calling new). Each node is a structure object. The data
filed holds the information stored in the node. The next field saves address of the next
node in the linked list. The end of the linked list is indicated by setting the next field to
NULL, which means that there is no node next to this node. Nodes are allocated on the
heap memory using new operator.

This is what a single linked list looks like diagrammatically. Each node has a
Key/Value which are strings in the case shown above, and a reference i.e., a next
pointer that points to the next element. Basically, the first node is the head, and the last
node is the tail in the list. The movement from one node to other is called traversal in
the list.
Head and tail of a linked list:
A singly linked list is also a collection of nodes and has a starting point called as
HEAD and an endpoint called TAIL.

National University of Computer & Emerging Sciences, Karachi Page | 2

 LAB: 08 [LINKED LIST]

 Head is the pointer that simply points or identifies to the first element in the
singly linked list.
 Tail identifies to the last node in the singly linked list and in this case, the
reference part of the node points to nothing or nil.

NOTE:A singly linked list does not have a predetermined size, so it uses
spaceproportionally according to the number of elements present in the list and unlike
arrays, it does not have the contiguous memory allocation i.e., they are not allocated one
after another, rather, distributed in memory and attached through pointer that we call the
reference part.

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following
limitations.

 The size of the arrays is fixed: So, we must know the upper limit on the number
of elements in advance. Also, generally, the allocated memory is equal to the upper
limit irrespective of the usage.

 Inserting a new element in an array of elements is expensive because the room

must be created for the new elements and to create room existing elements must be
shifted.

For example, in a system, if we maintain a sorted list of IDs in an array Id [ ].

Id [ ] = [1000, 1010, 1050, 2000, 2040].

 And if we want to insert a new ID 1005, then to maintain the sorted order, we
must move all the elements after 1000 (excluding 1000).

 Deletion is also expensive with arrays until unless some special techniques are
used. For example, to delete 1010 in id [ ], everything after 1010 has to be moved.

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion
Drawbacks:

1. Random access is not allowed. We have to access elements sequentially

starting from the first node. So, we cannot do binary search with linked lists efficiently
with its default implementation.

Page | 3 National University of Computer & Emerging Sciences, Karachi

 LAB: 03LIST]
[LINKED LAB: 08

2. Extra memory space for a pointer is required with each element of the list.

3. Not cache friendly. Since array elements are contiguous locations, there is
locality of reference which is not there in case of linked lists.

Following are the important points to be considered.

 Linked List contains a link element called first.

 Each link carries a data field(s) and a link field called next.

 Each link is linked with its next link using its next link.

 Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.

1. Simple Linked List − Item navigation is forward only.

2. Doubly Linked List − Items can be navigated forward and backward.
3. Circular Linked List − Last item contains link of the first element as next and
the first element has a link to the last element as previous.
Basic Operations
Following are the basic operations supported by a list.

1. Insertion − Adds an element at the beginning of the list.

2. Deletion − Deletes an element at the beginning of the list.
3. Display − Displays the complete list.
4. Search − Searches an element using the given key.
5. Delete − Deletes an element using the given key.
Representation:
A linked list is represented by a pointer to the first node of the linked list. The first
node is called the head. If the linked list is empty, then the value of the head is NULL.

Each node in a list consists of at least two parts:

1. Data

2. Pointer (Or Reference) to the next node

In python, LinkedList can be represented as a class and a Node as a separate class. The
LinkedList class contains a reference of Node class type.

National University of Computer & Emerging Sciences, Karachi Page | 4

 LAB: 08 [LINKED LIST]

# Node class
class Node:
def __init__(self,data):
# Function to initialise the node object
self.data = data # Assign data
self.next = None # Initialize next as null
------------------------------------------------------------------
class LinkedList:
def __init__(self): #Function to initialize the Linked List
self.head = None
def printList(self):
temp = self.head
while (temp):
print (temp.data,end=' , ')
temp = temp.next

------------------------------------------------------------------
# Code execution starts here
if __name__=='__main__':

llist = LinkedList( ) # Start with the empty list

llist.head = Node(1)
second = Node(2)
third = Node(3)
llist.head.next = second; # Link first node with second
second.next = third; # Link 2nd with 3rd node
llist.printList()
#print the list contents (TRAVERSAL)
Insert a new node in linked list:
A node can be added in three
ways1)At the front of the
linked list 2)After a given
node.
3)At the end of the linked list.

a.Insert at beginning: (A 4 steps process)

The new node is always added before the head of the given Linked List. And
newly added node becomes the new head of the Linked List.

If the given Linked List is 10->15->20->25

 We add an item 5 at the front, then the Linked List becomes 5->10->15->20-
>25.

 Let us call the function that adds at the front of the list is insert_beginning ().

Page | 5 National University of Computer & Emerging Sciences, Karachi

 LAB: 03LIST]
[LINKED LAB: 08

 The insert_beginning () must receive a pointer to the head pointer, because

insert_beginning must change the head pointer to point to the new node

# This function is in LinkedList class

# Function to insert a new node at
thebeginning
def insert_beginning(self,data):
node=Node(data)
if self.head == None:
self.head = node
else:
node.next = self.head
self.head = node
self.ctr += 1
print("Node inserted: ",data )
return

Time complexity of is insert_beginning( ) is O(1) as it does constant amount of work.

b. Insert at middle: (5 steps process)

We are given pointer to a node, and the new node is inserted after the given node.

c. Add a node at the end:

National University of Computer & Emerging Sciences, Karachi Page | 6

 LAB: 08 [LINKED LIST]

the new node is always added after the last node of the given Linked List.
For example:
1. If the given Linked List is 5->10->15->20->25
2. We add an item 30 at the end, then the Linked List becomes 5->10->15->20-
>25>30.
3. Since a Linked List is typically represented by the head of it, we have to
traverse the list till end and then change the next of last node to new node.

Time complexity of append is O(n) where n is the number of nodes in linked list. Since
there is a loop from head to end, the function does O(n) work. This method can also be
optimized to work in O(1) by keeping an extra pointer to tail of linked list/

Deletion in a Linked List:

We can delete a node from anywhere in a linked list. The delete method traverses the list
in the same way that search does, but in addition to keeping track of the current node, the
delete method also remembers the last node it visited. When delete finally arrives at the
node it wants to delete, it simply removes that node from the chain by “leap frogging” it.
By this I mean that when the delete method reaches the node it wants to delete, it looks at
the last node it visited (the ‘previous’ node), and resets that previous node’s pointer so that,
rather than pointing to the soon-to-be-deleted node, it will point to the next node in line.
Since no nodes are pointing to the poor node that is being deleted, it is effectively removed
from the list!

The time complexity for delete is also O(n), because in the worst case it will visit every
node, interacting with each node a fixed number of times.

Deletion at the beginning of a Linked List

Page | 7 National University of Computer & Emerging Sciences, Karachi

 LAB: 03LIST]
[LINKED LAB: 08

Deletion at the middle of a Linked List

Deletion at the end of a Linked List

National University of Computer & Emerging Sciences, Karachi Page | 8

 LAB: 08 [LINKED LIST]

Search:
Search is actually very similar to size, but instead of traversing the whole list of
nodes it checks at each stop to see whether the current node has the requested data and if
so, returns the node holding that data. If the method goes through the entire list but still
hasn’t found the data, it raises a value error and notifies the user that the data is not in the
list.
Once a linked list is created, we can search for a particular item in it. We start from
the root node and keep moving to the next node unless either we find the desired item, or
the linked list ends i.e., node is NULL. In the former case, search is successful i.e., the
item is found, whereas in the latter case search is unsuccessful. The time complexity of
search is O(n) in the worst case (you often hear about best case / average case / worst case
for Big O analysis. For this purpose of this blog post, we’ll assume worst case is the one
we care about it, because it often
is!)

Page | 9 National University of Computer & Emerging Sciences, Karachi

 LAB: 03LIST]
[LINKED LAB: 08

Lab Report:
(It is recommended to write Lab Report in bullet Form)

________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________

National University of Computer & Emerging Sciences, Karachi Page | 10

 LAB: 08 [LINKED LIST]

________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________
________________________________________________________________________________________

Page | 11 National University of Computer & Emerging Sciences, Karachi

 LAB: 03LIST]
[LINKED LAB: 08

class Node(object): print("Node deleted: ",self.head.data)

def __init__(self,data): self.head=self.head.next
self.data=data self.ctr-=1
self.next=None return
class S_L_List(object): def delete_middle(self,pos):
def __init__(self): if self.head==None:
self.head=None print("No node exists!")
self.ctr=0 elif pos==0:
def printlist(self): self.delete_beginning()
elif pos==self.ctr:
temp=self.head self.delete_end()
while temp is not None: else:
print(temp.data,end='->') temp=self.head
temp=temp.next prev=temp
print() i=0
def insert_beginning(self,data): while i<pos:
node=Node(data) prev=temp
if self.head==None: temp=temp.next
self.head=node i+=1
else: prev.next=temp.next
node.next=self.head print("Node deleted: ",temp.data)
self.head=node temp.next=None
self.ctr+=1 self.ctr-=1
print("Node inserted: ",data) return
return def delete_end(self):
def insert_middle(self,pos,data): if self.ctr==0:
if pos==0: print("No node exists!")
self.insert_beginning(data) elif self.ctr==1:
elif pos == self.ctr+1: self.ctr=0
self.insert_end(data) print("Node deleted ", self.head.data)
else: self.head=None
node=Node(data) else:
temp=self.head temp=self.head
i=0 prev=self.head
while(i<pos-1): while(temp.next is not None):
temp=temp.next prev=temp
i+=1 temp=temp.next
node.next=temp.next print("Node deleted: ",temp.data)
temp.next=node prev.data=None
self.ctr+=1 self.ctr-=1
print("Node inserted: ",data," at ",pos) return
return def traverse_forward(self):
def insert_end(self,data): if self.head==None:
node=Node(data) print("No node exists!")
node.next=None else:
if self.head==None: print("Traverse nodes: \n")
self.head=node temp=self.head
return while(temp is not None):
temp=self.head print(temp.data)
while(temp.next is not None): temp=temp.next
temp=temp.next print()
temp.next=node def count_nodes(self):
self.ctr+=1 temp = self.head
print("Node Inserted: ",data) count = 0
return while (temp):
def delete_beginning(self): count += 1
if self.head==None: temp = temp.next
print("No node exists!") return print("Number of nodes are",count)
elif self.ctr==1: while True:
print("Node deleted ", self.head.data) a=S_L_List()
self.head=None print("1.Insert at beginning")
self.ctr-=1 print("2.Insert at middle")
else: print("3.Insert at end")

National University of Computer & Emerging Sciences, Karachi Page | 12

 LAB: 08 [LINKED LIST]

print("4.Delete at beginning")
print("5.Delete at middle")
print("6.Delete at end")
print("7.Traversal Forward")
print("8.Count number of nodes")
print("9.Exit")
ch=int(input("Enter your choice [1-8]: "))
if ch==1:
x=int(input("enter the value"))
a.insert_beginning(x)
a.printlist()
elif ch==2:
x=int(input("enter the value"))
a.insert_middle(1,x)
a.printlist()
elif ch==3:
x=int(input("enter the value"))
a.insert_end(x)
a.printlist()
elif ch==4:
a.delete_beginning()
a.printlist()
elif ch==5:
x=int(input("enter the value"))
a.delete_middle(x)
a.printlist()
elif ch==6:
a.delete_end()
a.printlist()
elif ch==7:
a.traverse_forward()
a.printlist()
elif ch==8:
a.count_nodes()
a.printlist()

Page | 13 National University of Computer & Emerging Sciences, Karachi