Introduction to Linked Lists and How to implement in Python ?
In this tutorial we will take a ride to know more about Linked lists – what they are, how are they different from other Data Structures and how to start with one in Python.
Linked List in Python
Linked lists are a basic linear data structure and is not stored in the contiguous form in memory.
Every element in it is called a Node and each node is respectively connected to the other two nodes both forwards and backwards except for the end Nodes.
TYPES of Linked List
- Singly Linked List
- Doubly Linked List
- Multiply Linked list
- Circular Linked List
Advantages of Linked Lists
- Dynamic Memory Allocation: In Linked Lists, memory is used only when some data is required to be saved; rather than pre-defining some space for storage.
- Ease of Insertion/Deletion: In Linked Lists, elements can be easily inserted or removed in any position in the Linked List.
- Reduces Space Complexity: In this case, space for elements is allocated dynamically; there is no extra space reserved to save elements further and thereby reduces the space required to run a specific program.
Disadvantages of Linked List
- NO Random Access: Since Linked Lists work on the fact that address for the next node is saved in the previous node, we cannot access an element randomly and require to traverse through the whole Linked List.
- Requires more space: In Linked Lists, along with the element we need to save the address for the next element; so it increases the space required to save the same elements in Linked Lists as compared to Arrays.
- Increases Time Complexity: As to access a random element, we need to traverse through the whole List which increases the time required.
Create A Linked List in Python
As we have studied so far, a node is a single element; so using the OOPs functionality of Python we will create a node class first to describe an element.
Here, our Node contains two sub-elements – its own value and a link to the next node.
class LNode: def __init__(self, value): self.value = value self.link = None
Further, we will a class LList describing the List connecting all the Node classes.
Here, we have taken the link for the initial node to be NULL, as currently, our Linked List doesn’t contain any element.
class LList: def __init__(self): self.start = None
Hope, you have now got a fair idea about what Linked Lists are.
Feel free to leave any query you face in the comments section below.
Also, have a look at :