UNIVERSITYOF ENGINEERING AND TECHNOLOGY

TAXILA

Submitted To:
Engr. Iqra Jabeen

Submitted By:
Amjid Khan (23-TE-86)

Subject:
Data Structure and Algorithms Lab

DEPARTMENT OF TELECOMMUNICATION
ENGINEERING
 1

Lab Report: 6
Development of a program in Python for the implementation of Singly
Linked List

Objectives:
The objective of this lib is to familiarize with the following properties of singly Linked List.

➢ Create a Node: Make a class to store data and the next link.
➢ Build the List: Create a class to manage the list starting with the first node (head).
➢ Add Nodes: Write methods to add new items to the list (at the start, end, or in the middle).
➢ Remove Nodes: Add methods to delete items from the list.
➢ Show the List: Make a function to display all the items in the list.

Equipment Required:
➢ Computer/Laptop with at least 4 GB RAM.
➢ Python 3.x installed and configured.
➢ IDE/Text Editor like PyCharm, VS Code, or Jupyter, Notebook etc.
➢ NumPy library (optional) for advanced array handling.
➢ Internet connection for downloading resources and accessing documentation.

Procedure:
➢ Open Computer System.
➢ Go to all programs.
➢ Open python.
➢ Create a new file with the extension .py.
➢ Write all the required code and then run the module.

Introduction to Linked List:

A Linked List is a data structure used to store a collection of elements, where each element is
called a node. Unlike arrays, which store elements in contiguous memory locations, linked lists
use a series of connected nodes, where each node contains two parts:
1. Data: The value or information stored in the node.
2. Next: A reference (or link) to the next node in the list.
In a Singly Linked List, each node points to the next one, and the last node points to null (or None
in Python), marking the end of the list. This structure allows for dynamic memory allocation,
 2

meaning the list can grow or shrink as needed. However, accessing elements is slower than arrays
because traversal starts at the first node and continues sequentially.
Linked lists are useful for efficiently adding and removing elements from any position in the list,
especially when working with large or dynamically changing datasets.
[Data | Next] -> [Data | Next] -> [Data | None]

Traversing:
This method traverses the linked list and prints the data of each node. In this method, we made
a current_node equal to the head and iterate through the linked list using a while loop until
the current_node become None and print the data of current_node in each iteration and make
the current_node next to it.

Class and Object in python:

Class:
A class is a user-defined blueprint or prototype from which objects are created. Classes provide a
means of bundling data and functionality together. Creating a new class creates a new type of
object, allowing new instances of that type to be made. Each class instance can have attributes
attached to it to maintain its state. Class instances can also have methods (defined by their class)
for modifying their state.

Syntax:
class ClassName:
#Statement
 3

Object:
In python programming an Object is an instance of a Class. A class is like a blueprint while an
instance is a copy of the class with actual values. It’s not an idea anymore, it’s an actual dog, like
a dog of breed pug who’s seven years old. You can have many dogs to create many different
instances, but without the class as a guide, you would be lost, not knowing what information is
required.
An object consists of:
• State: It is represented by the attributes of an object. It also reflects the properties of an
object.
• Behavior: It is represented by the methods of an object. It also reflects the response of
an object to other objects.
• Identity: It gives a unique name to an object and enables one object to interact with
other objects.

Syntax / Object Definition:

class Dog:
def __init__(self, name):
self.name = name
def bark(self):
print(f"{self.name} says Woof!")
my_dog = Dog("Buddy")
my_dog.bark()

Output:
 4

The __init__() function:

The __init__() method in Python is a special method called a constructor. It is automatically called
when a new object is created from a class and is used to initialize the object's attributes.

Key Points about __init__():

1. It is used to set the initial state of an object (assign values to the object’s properties).
2. It’s not mandatory to include it in a class, but it’s commonly used for initialization.
3. The first parameter of __init__() is always self, which refers to the current object being
created.

class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def greet(self):
print(f"Hello, my name is {self.name} and I am
{self.age} years old.")
person1 = Person("Alice", 30)
person1.greet()

Output:

The __str__() method:

Python has a particular method called __str__(). that is used to define how a class object should
be represented as a string. It is often used to give an object a human-readable textual
representation, which is helpful for logging, debugging, or showing users object information.
When a class object is used to create a string using the built-in functions print() and str(),
the __str__() function is automatically used. You can alter how objects of a class are represented
in strings by defining the __str__() method.

class GFG:
def __init__(self, name, company):
self.name = name
 5

self.company = company
def __str__(self):
return f"My name is {self.name} and I work in
{self.company}."
my_obj = GFG("John", "GeeksForGeeks")
print(my_obj)

Output:

Inserting elements at the start of Linked List:

Algorithm:
➢ Make the first node of Linked List linked to the new node
➢ Remove the head from the original first node of Linked List
➢ Make the new node as the Head of the Linked List.

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

class linkedlist:
def __init__(self):
 6

self.head = None

def printLL(self):
if self.head is None:
print("linked list is empty:")
else:
n = self.head
while n is not None:
print(n.data)
n = n.next

def add_start(self, data):

new_node = node(data)
new_node.next = self.head
self.head = new_node

LL = linkedlist()
LL.add_start(50)
LL.add_start(20)
LL.printLL()

Output:

Conclusion:
The development of a program in Python for the implementation of a singly linked list
demonstrates a fundamental data structure that efficiently manages collections of elements. By
utilizing a linked list, we gain the flexibility of dynamic memory allocation, allowing for efficient
insertions and deletions without the need to resize arrays.
 7

Lab Tasks:
1. Write a program in Python to create a singly linked list of n nodes and display it in reverse order.

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

class LinkedList:
def __init__(self):
self.head = None

def insert(self, data):

new_node = Node(data)
if self.head is None:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node

def display(self):
if self.head is None:
print("Linked list is empty")
else:
temp = self.head
while temp:
print(f"data={temp.data}")
temp = temp.next
 8

def reverse(self):
prev = None
current = self.head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev

L = LinkedList()

print("Inserted nodes")
L.insert(5)
L.insert(6)
L.insert(7)
L.display()

L.reverse()

print("\nReversed nodes")
L.display()

Output:
 9

2. Write a program in Python to create a singly linked list of n nodes and count the number
of nodes.
➢ Data entered in the list:
o Data = 5
o Data = 6
o Data = 7
➢ Total number of nodes = 3

class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def count_nodes(self):
count = 0
temp = self.head
while temp:
count += 1
temp = temp.next
return count
def display(self):
 10

temp = self.head
if temp is None:
print("Linked list is empty")
else:
print("Data entered in the list:")
while temp:
print(f"Data = {temp.data}")
temp = temp.next
linked_list = LinkedList()
linked_list.append(5)
linked_list.append(6)
linked_list.append(7)
linked_list.display()
total_nodes = linked_list.count_nodes()
print("Total number of nodes =", total_nodes)

Output:
 11

3. Write a program in Python to create a singly linked list of n nodes to generate the following
output.

class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def print_list(self):
temp = self.head
while temp:
print("Data:", temp.data)
temp = temp.next
n = int(input("Input the number of Nodes: "))
linked_list = LinkedList()
for i in range(1, n+1):
data = int(input(f"Input data for Node {i}: "))
linked_list.append(data)
print("Data Entered in the list")
linked_list.print_list()
 12

Output:

4. Write a Python program for Given a singly linked list, find the middle of the linked list.
1->2->3->4->5->NULL
The middle element is [3]

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

class LinkedList:
def __init__(self):
self.head = None

def append(self, data):

new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node

def find_middle(self):
 13

slow = self.head
fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.data

n = int(input("Enter the number of nodes: "))

linked_list = LinkedList()
for i in range(n):
data = int(input(f"Enter data for node {i+1}: "))
linked_list.append(data)

middle_element = linked_list.find_middle()
print("The middle element is", middle_element)

Output:

5. Write a Python program for Given a singly linked list and insert a new node at the end of
the linked list.
Input 4,5,6,7,8,9
Output 4,5,6,7,8,9,1

class Node:
def __init__(self, data):
self.data = data
 14

self.next = None

class LinkedList:
def __init__(self):
self.head = None

def append(self, data):

new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node

def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" ")
temp = temp.next

# Get the numbers as input

numbers = list(map(int, input("Enter numbers for the
linked list, separated by spaces: ").split()))

# Create a linked list

linked_list = LinkedList()

# Append numbers to the linked list

for number in numbers:
linked_list.append(number)
 15

# Insert a new node at the end

new_data = int(input("Enter a new number to add at the
end: "))
linked_list.append(new_data)

# Print the linked list

print("\nLinked list:")
linked_list.print_list()

Output: