Data Structures with Python Week 5 & 6
Week-5
Linear (arrays) vs nonlinear (pointer) structures – Run time and space requirements, when to use what?
Introduction to linked list, Examples: Image viewer, music player list etc. (to be used to explain concept of list),
applications.
Week-6
The Singly Linked List- Creating Nodes, Traversing the Nodes, searching for a Node, Prepending Nodes,
Removing Nodes. Linked List Iterators.
Linear Structures (Arrays):
Arrays a kind of data structure that can store a fixed-size sequential collection of elements of the same type.
All arrays consist of contiguous memory locations.
The lowest address corresponds to the first element and the highest address to the last element.
Non-Linear structures (Pointers):
A pointer is a variable which holds the address of another variable, i.e., address of the memory location.
Advantages of pointers:-
Pointers increase the speed of execution because manipulation with address is faster than the variables.
Pointers allow dynamic memory allocation and de allocation.
Using pointers arrays, strings, structures can be handled in more efficient way.
Using pointers it is possible to create more complex data structures like linked lists, trees etc
Introduction to Linked List:
A linked list is a sequence of data elements, which are connected together via links.
A Linked list is a collection of zero or more nodes where each node contains 2 fields, data and link.
Data field stores the actual information and link (address) field contains the address of the next node.
The memory representation of a node is given below
Dept. of Computer Science & Engg. Page 1 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
The memory representation of a linked list is given below
Each node contains two fields i.e. data and link field
The data field contains data or information.
Link field is a pointer which contains the address of the next node.
Last node’s link field will be NULL.
They are less rigid; elements can be stored in non-contiguous locations.
They require additions values to reference the next element.
Every node in the linked list points to the next element in the linked list.
Since they are non-contiguous, the size of the linked list can be altered at run-time.
Memory is allocated to linked list at run time.
Linked list requires more memory since it includes reference to next node.
Array V/s Linked List:
Arrays Linked Lists
Size of an array is fixed Size of a linked list is not fixed.
Memory is allocated from stack area. Memory is allocated from heap area.
Memory is allocated during compile time. Memory is allocated during run time.
It occupies less memory It occupies more memory
Inserting a new elements is difficult Inserting new elements is easy
Deleting an element from an array is difficult Deleting an element is easy
Advantages of Linked List:-
Linked lists are dynamic data structure they can grow or shrink during the execution of a program.
Insertion and deletion are easier & efficient.
Efficient memory utilization i.e. memory is allocated whenever it is required and de allocated whenever it is
no longer needed.
Many complex applications can be easily carried out with Linked Lists.
Disadvantages of Linked List:-
It consumes more space because every node requires a additional space to store the address of the next node.
Searching is difficult & also time consuming (only linear search )
No random access (only sequential access)
Reverse traversing is difficult
Applications of linked list in real world:
Dept. of Computer Science & Engg. Page 2 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
1. Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.
2. Previous and next page in web browser – We can access previous and next URL searched in web browser
by pressing back and next button since, they are linked as linked list.
3. Music Player – Songs in music player are linked to previous and next song. We can play songs either from
starting or ending of the list.
Types of Linked List:
Singly Linked List:
A singly linked list is one in which each node has only one link field which contains the address of the next
node of a list.
A single linked list allows traversal of data only in one way.
Doubly Linked List:
A doubly linked list or a two-way linked list which contains a pointer to the next node as well as the
previous node in the list.
Doubly Linked list is a list in which each node contains 2 link fields is called doubly Linked List.
It contains three fields, data, a pointer to the next node, and a pointer to the previous node.
It allows us to traverse the list in the backward direction as well.
Circular Linked List:
A Circular Linked List is a list in which the link field of the last node contains the address of the first node
of a list.
While traversing a circular linked list, we can begin at any node and traverse the list until we reach the same
node we started.
Dept. of Computer Science & Engg. Page 3 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
Doubly Circular Linked List:
In Circular Doubly Linked list the previous pointer of the first node contains address of the last node & next
pointer of last node contains the address of the first node
It also contains three fields, data, a pointer to the next node, and a pointer to the previous node.
While traversing a circular doubly linked list, we can begin at any node and traverse the list in any direction
forward and backward until we reach the same node we started.
Creation of Singly Linked List:
We can create a singly linked list in python by following the mentioned steps.
Step 1: First, we create empty head or first reference and initialize it with null.
Step 2: Create a class “node”. The objects of this class hold one variable to store the values of the nodes and
another variable to store the reference addresses.
Step 3: Create a blank node and assign it a value. Set the reference part of this node to null.
Step 4: Since we have only one element in the linked list so far, we will link first to this node by putting in its
reference address
The python code to create a new node of the linked list is given below.
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
The python code to create a linked list and initialize first reference.
class LinkedList:
def __init__(self):
self.first = None
Dept. of Computer Science & Engg. Page 4 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
Prepending Nodes:
The following are the steps to be followed to insert a new node at beginning of the list.
Step 1:- Create a new node and insert the item into the new node.
Step 2:- If the list is empty then make new node as first. Go to step 4
Step 3:- Assign the “next” reference of the new node as first. Set the created node as the new first.
Step 4: Terminate.
The python code to add new node to the linked list is given below.
def insertFirst(self, data):
temp = Node(data)
if(self.first == None):
self.first=temp
else:
temp.next=self.first
self.first=temp
Removing Nodes:
The following are the steps to be followed to remove node from the beginning of the list.
Step 1: If the linked list is empty, return and go to step 5.
Step 2: If there’s only one element, delete that node and set first to none. Go to step 5.
Step 3: Set a “temp” node pointing at first.
Step 4: Assign first as the next node. Delete the temp node.
Step 5: Terminate
The python code to remove node from the linked list is given below.
Dept. of Computer Science & Engg. Page 5 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
def removeFirst(self):
if(self.first== None):
print("list is empty")
else:
cur=self.first;
self.first=self.first.next
print("the deleted item is",cur.data)
Traversing the Nodes:
A singly Linked list can only be traversed in forward direction from the first element to the last. We get the
value of the next data element by simply iterating with the help of the reference address.
Step 1: If the linked list is empty, display the message “List is empty” and move to step 5.
Step 2: Iterate over the linked list using the reference address for each node.
Step 3: Print every node’s data.
Step 4: Terminate.
The python code to traversing the nodes of linked list is given below.
def display(self):
if(self.first== None):
print("list is empty")
return
current = self.first
while(current):
print(current.data, end = " ")
current = current.next
Searching for a Node:
To find a node in a given singly linked list, we use the technique of traversal. In this case as soon as we find
the node, we will terminate the loop.
Algorithm to search a given node from the linked list is given below
Step 1: If the linked list is empty, display the message “List is empty” and move to step 5.
Step 2: Iterate over the linked list using the reference address for each node.
Step 3: Search every node for the given value.
Step 4: If the element is found, break the loop. If not, return the message “Element not found”.
Step 5: Terminate.
The python code implementation of searching the nodes of linked list is given below.
def search(self,item):
if(self.first== None):
print("list is empty")
return
current = self.first
found = False
while current != None and not found:
if current.data == item:
Dept. of Computer Science & Engg. Page 6 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
found = True
else:
current = current.next
if(found):
print("Item is present in the linked list")
else:
print("Item is not present in the linked list")
Implementation of singly linked list (Traversing the Nodes, searching for a Node, Prepending Nodes,
Removing Nodes) :
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.first = None
def insertFirst(self, data):
temp = Node(data)
if(self.first == None):
self.first=temp
else:
temp.next=self.first
self.first=temp
def removeFirst(self):
if(self.first== None):
print("list is empty")
else:
cur=self.first
self.first=self.first.next
print("the deleted item is",cur.data)
def display(self):
if(self.first== None):
print("list is empty")
return
current = self.first
while(current):
print(current.data, end = " ")
Dept. of Computer Science & Engg. Page 7 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
current = current.next
def search(self,item):
if(self.first== None):
print("list is empty")
return
current = self.first
found = False
while current != None and not found:
if current.data == item:
found = True
else:
current = current.next
if(found):
print("Item is present in the linked list")
else:
print("Item is not present in the linked list")
#Singly Linked List
ll = SinglyLinkedList()
while(True):
c1 = int(input("\nEnter your choice 1-insert 2-delete 3-search 4-display 5-exit :"))
if(c1 == 1):
item = input("Enter the element to insert:")
ll.insertFirst(item)
ll.display()
elif(c1 == 2):
ll.removeFirst()
ll.display()
elif(c1 == 3):
item = input("Enter the element to search:")
ll.search(item)
elif(c1 == 4):
ll.display()
else:
break
Linked List Iterators:
Traversals are very common operations, especially on containers.
A python for loop is used to traverse the items in strings, lists, tuples and dictionaries as follows.
print("List iteration")
l1 = [1,2,3,4]
for x in l1:
Dept. of Computer Science & Engg. Page 8 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
print(x)
print("tuple iteration")
t1 = (10,20,30,40)
for x in t1:
print(x)
print("String iteration")
t1 = "Welcome to gpt koppal"
for x in t1:
print(x)
An iterators guarantee that each element is visited exactly once.
Custom created linked list is not iterable; there is a need to add a __iter__ function to traverse through the
list.
Iterator function is defined as follows
def __iter__(self):
current = self.first
while current:
yield current.data
current = current.next
Implementation of linked list Iterators:
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.first = None
def insert(self, data):
temp = Node(data)
if(self.first):
current = self.first
while(current.next):
current = current.next
current.next = temp
else:
self.first = temp
def __iter__(self):
current = self.first
while current:
yield current.data
Dept. of Computer Science & Engg. Page 9 Govt. Polytechnic Koppal
Data Structures with Python Week 5 & 6
current = current.next
# Linked List Iterators
ll = LinkedList()
ll.insert(9)
ll.insert(98)
ll.insert("welcome")
ll.insert("govt polytechnic koppal")
ll.insert(456.35)
ll.insert(545)
ll.insert(5)
for x in ll:
print(x)
Time Complexity of Linked List Vs Array:
Dept. of Computer Science & Engg. Page 10 Govt. Polytechnic Koppal
