How to implement the linked list in Python - NareshIT
Naresh i Technologies
Only Institute to offer the 'Most Comprehensive eLearning Platform to suit the self-learning needs of all CMS and LMS
Introduction:
As we previously noted, Python is a more sophisticated language that provides excellent capabilities for data crunching and preparation, as well as advanced scientific data analysis and modeling. Python is a popular programming language. It was developed by Guido van Rossum and published in 1991. It is mostly used for web application development (server-side).
Skills include software development, arithmetic, and system programming.
Everyone who programs in Python should be familiar with linked lists and how they work. A Python developer should understand how to construct and implement various types of linked lists in a realistic manner. Here, I'll go over the various approaches for implementing linked lists in Python.
Most programmers encounter a common question while programming, such as, "Does Python have a built-in or 'native' linked list data structure?". Furthermore, "How do I write a linked list in Python?" . Here, I'll go over the various techniques in depth.
What is Linked List? And What are their characteristics?
A linked list is primarily defined as an ordered set of values. In Python, lists are formed in the same way as in other programming languages. In Python, linked lists are built in a manner similar to arrays in that they hold items in a linear order. However, they differ from standard array approaches in terms of memory layout.
The link list is a succession of nodes of comparable data types, each containing one data object and a reference to the next node.
A linked list is a linear data structure that consists of several nodes. Each element holds its own data as well as a link to the following element's position. A linked list's last link leads to null, indicating that the chain has come to an end. A linked list element is referred to as a node. The first node is called the head. The last node is known as the tail.
As we know, arrays are contiguous data structures that hold comparable types of elements under a single name, and they are made up of fixed-size data records stored in adjacent blocks of memory.
The array is arranged as shown below.
Similarly, linked lists are built. The linked list is made up of data entries connected by pointers. This implies that data records containing the actual "data payload" can be placed wherever in memory. The graphic below depicts the implementation situation of a linked list.
There are two different kinds of linked lists:?singly-linked lists?and?doubly-linked lists. The diagram showed 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 (CPython), 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 primary question arises: how to design and write a linked list program in Python. I will explore this further below.
How to write a linked list program using Python?
If you prefer to remain with capabilities provided into the core language and the Python standard library, you may construct a linked list in two ways:
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
To implement a linked list, consider the following functionality.
1. Insert: This function creates a new node in an existing linked list.
2. Size: This function is mostly used to retrieve the size of the linked list, or how many entries it includes.
3. Search: This function returns a node containing the data, else it raises an error.
4. Delete: This method deletes a node containing the data, else it raises 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 construct the delete method, we will traverse the list in the same manner that search does, but in addition to keeping track of the current node, the delete function will remember the last node visited. When remove finally reaches the node it intends to delete. It just "leapfrogging" that node from the chain.
Python Linked Lists: Recap & Recommendations
We recently looked at a variety of ways to implement a list in Python. You also saw several code examples for common operations and algorithms, such as how to reverse a linked list in-place.
You should only use a linked list in Python if you are certain that you require one for performance reasons.
In many circumstances, the same approach applied to Python's highly optimized list objects will be quick enough. whether you know that a dynamic array will not enough and that you want a linked list, first see whether you can use Python's built-in deque class.
Scope @ NareshIT:
FAQ'S
1. What is a linked list, and why is it used in Python?
A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a node) contains a data value and a pointer to the next node in the list. Linked lists are flexible and dynamic, making them suitable for various applications in Python.
2. How do I create a linked list in Python?
To create a linked list in Python, you typically define a Node class to represent each element. The Node class should have attributes for the data value and a pointer to the next node. You can then create a linked list by creating instances of the Node class and connecting them together.
3. What are the common operations performed on linked lists?
Common operations on linked lists include:
For More Details Visit : Python Online Training
Register For Free Demo on UpComing Batches : https://nareshit.com/new-batches