Introduction:
As we have already discussed earlier that The Python is more powerful language which offer great tools for data crunching and preparation, as well as for complex scientific data analysis and modelling. Python is a popular programming language. It was created by Guido van Rossum, and released in 1991. It is basically used for:
- web application development (server-side),
- software development,
- mathematics,
- system scripting.
Being the programmer in python Everyone should know about linked lists and its operation. A python developer should know how to create and implement the variety of linked list in practical manner. Here I am going to discuss the various ways of implementing the linked list in python using the suitable methods.
Most of the programmer during the programming always come across a common question such as, “Does Python have a built-in or ‘native’ linked list data structure?” or, “How do I write a linked list in Python?”. Here I am going to discuss the various approaches in detail.
- The Python language doesn’t ship with a built-in linked list data type in the “classical” sense.
- The Python’s list type is implemented as a dynamic array as it has the concept of list, tuple and dictionary.
- So we need here a typical scenarios to use a “proper” linked list data structure for performance reasons.
What is Linked List? And What are their characteristics?
A linked list is mainly defined as an ordered collection of values. In python the list is used to be get created in similar way like other programming language. In python the Linked lists are get created in similar to arrays in the sense that they contain objects in a linear order. But they are get differ from traditional arrays approach in their memory layout.
The link list is a sequence of nodes having a similar data type, each node contains one data object and pointer to the next node.
A linked list is a linear data structure with the collection of multiple nodes. Where each element stores its own data and a pointer to the location of the next element. The last link in a linked list points to null, indicating the end of the chain. An element in a linked list is called a node. The first node is called the head. The last node is called the tail.
As we know that the Arrays are contiguous data structures which stores the similar kind of element under a single name and they’re composed of fixed-size data records stored in adjoining blocks of memory.
In the similar way the Linked lists is also get created. The linked list are made up of data records linked together by pointers. This means that the data records that hold the actual “data payload” can be stored anywhere in memory. The following diagram showed below shows the implementation scenario of linked list.
There are two different kinds of linked lists: singly-linked lists and doubly-linked lists. The above is the singly-linked list where each element in it has a reference to (a “pointer”) to the next element in the list.
Where as in a doubly-linked list, each element has a reference to both the next and the previous element. Why is this useful? Having a reference to the previous element can speed up some operations, like removing (“unlinking”) an element from a list or traversing the list in reverse order.
As you know that the Python 3.6 (C Python), doesn’t able to provide a dedicated linked list data type.
Python does however include the collections. deque class which provides a double-ended queue and is implemented as a doubly-linked list internally.
Now the main question get arises that how to create and write the linked list program in python. Here I am going to discuss below.
How to write a linked list program using Python?
If you want to stick with functionality built into the core language and into the Python standard library you have two options for implementing a linked list:
You could either use the collections. deque class from the Python standard library and take advantage of the fact that it’s implemented as a doubly-linked list behind the scenes.
Alternatively, you could define your own linked list type in Python by writing it from scratch using other built-in data types. You’d implement your own custom linked list class or base your implementation of Lisp-style chains of tuple objects.
Implementing a Linked List
For creating a Linked List, we create a node object and create another class to use this node object.
Code for creating Node class.
The above program creates a linked list with three data elements.
class Node(object):
# Constructor to initilize class variables
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
#get data
def get_data(self):
return self.data
# get next value
def get_next(self):
return self.next_node
# set next data
def set_next(self, new_next):
self.next_node = new_next
When we are going to implement the linked list then the Implementation of link list consists of the following
functionality in a linked list
- Insert: This method is basically used to insert a new node in an existing linked list.
- Size: This method is basically used to return the size of the linked list that how many elements does it contains.
- Search: This method will return a node containing the data, else will raise an error
- Delete: This method will delete a node containing the data, else will raise an error
Init method in a linked list:
This method is basically used to initialised the list with initial value. The code is as showed below.
class LinkedList(object):
def __init__(self, head=None):
self.head = head
Insertion of element into the linked list:
To insert the code into the linked list we need to use the following code. The segment of the program is as
discussed below.
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
Predicting the Size of the list:
The following code is used to return the size of the list.
# Returns total numbers of node in list
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.get_next()
return count
Search the element form the list:
# Returns the node in list having nodeData, error occured if node not present
def search(self, nodeData):
current = self.head
isPresent = False
while current and isPresent is False:
if current.get_data() == nodeData:
isPresent = True
else:
current = current.get_next()
if current is None:
raise ValueError(“Data not present in list”)
return current
Delete the existing element from the list:
# Remove the node from linked list returns error if node not present
def delete(self, nodeData):
current = self.head
previous = None
isPresent = False
while current and isPresent is False:
if current.get_data() == nodeData:
isPresent = True
else:
previous = current
current = current.get_next()
if current is None:
raise ValueError(“Data not present in list”)
if previous is None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
When we are going to implement the delete method it is used to 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 is visited. When delete finally arrives at the node it wants to delete. It simply removes that node from the chain by “leapfrogging” it.
Python Linked Lists: Recap & Recommendations
We just looked at a number of approaches to implement a list in Python. You also saw some code examples of the standard operations and algorithms, for example how to reverse a linked list in-place.
You should only consider using a linked list in Python when you’ve determined that you absolutely need a linked data structure for performance reasons (or you’ve been asked to use one in a coding interview.)
In many cases the same algorithm implemented on top of Python’s highly optimized list objects will be sufficiently fast. If you know a dynamic array won’t cut it and you need a linked list, then check first if you can take advantage of Python’s built-in deque class.
Scope @ NareshIT:
- At NareshIT’s Python application Development program you will be able to get the extensive hands-on training in front-end, middleware, and back-end technology.
- It skilled you along with phase-end and capstone projects based on real business scenarios.
- Here you learn the concepts from leading industry experts with content structured to ensure industrial relevance.
- An end-to-end application with exciting features.
