Understanding Linked Lists
A linked list is a data structure that consists of a collection of nodes, each containing data and a reference to the next node in the list. The first node is called the head, while the last node is called the tail.
Linked lists can be either singly linked or doubly linked, depending on whether each node has a reference to its previous node or not. The main advantage of linked lists is that they allow constant-time insertion and deletion of elements, unlike arrays or lists, which require items to be shifted around.
Nodes
Nodes are the building blocks of linked lists. These nodes contain the data that are to be stored in the list and have pointers to other nodes in the list.
To put it more simply, nodes are the functional parts that make up the linked list. Each node contains two parts, namely the data part and the pointer part.
The data part is where elements like integer values, strings, and other data types are stored. On the other hand, the pointer part contains the address of the next node in the list.
Practical Applications of Linked Lists
Linked lists have several practical applications that you may encounter while working on coding projects. One of them is using linked lists as a way of implementing a queue.
Queue
A queue is a data structure that follows the first-in-first-out (FIFO) policy. This means that the first element to be inserted in the queue will be the first element to be removed.
Linked lists can be used to implement queues because of their ability to perform constant time insertions and deletions. Another application of linked lists is in implementing a stack.
Stack
A stack is a data structure that follows the last-in-first-out (LIFO) policy. This means that the last element to be inserted into the stack is the first element to be removed.
Linked lists can also be used to implement stacks because of their ability to perform constant time insertions and deletions. Linked lists can also be used to represent graphs, which are data structures that consist of a set of vertices and edges connecting them.
Graphs
In a graph, linked lists are used as an adjacency list, where the vertex has a linked list of its adjacent vertices. This way, we can efficiently store relationship information between graph nodes.
Performance Comparison: Lists vs. Linked Lists
While linked lists have several advantages, they also have their downsides.
In this section, we will compare linked lists to lists in terms of performance.
Insertion and Deletion of Elements
In Python, lists offer several methods for inserting and deleting elements, such as insert(), remove(), and append(). While these methods are convenient to use, the time complexity of insertion and deletion is O(n), where n is the number of elements in the list.
This is because, after every insertion or deletion operation, the remaining elements must be shifted to accommodate the new element or fill in the gap created by removing an element. Linked lists, on the other hand, perform insertions and deletions in constant time, O(1).
This is because, when inserting a new node, we only update the pointer of the current node to point to the new node, and the new node’s pointer will point to the previous node. When deleting a node, we only need to update the previous node pointer to point to the next node, skipping over the deleted node.
Retrieval of Elements
When it comes to retrieving elements, Python’s lists offer efficient element lookup operations, with a time complexity of O(1). This means that we can access an element directly using its index.
Linked lists, on the other hand, have a time complexity of O(n) for element lookup since we have to iterate over each node in the list until we find the desired element. In conclusion, linked lists are a powerful data structure that offers several advantages when it comes to insertion and deletion, making them suitable for use in situations where we need to perform many of these operations.
However, when it comes to element retrieval, lists offer better performance. It is essential to consider the needs of your project and the type of data you will be working with carefully to choose the data structure that best fits your needs.
In summary, linked lists offer several benefits, such as their ability to perform constant-time insertions and deletions. They can be useful when implementing data structures like queues, stacks, or graphs.
However, they do have their disadvantages, such as slower element retrieval. By understanding the advantages and disadvantages of linked lists, we can use them effectively in our programming projects.
Introducing collections.deque
collections.deque is a module in Python that provides us with a double-ended queue data structure (which is pronounced as ‘deck’). It is essentially a linked list data structure that supports constant-time insertions and deletions from both ends of the deque.
Furthermore, it also supports regular indexing and slicing operations, which makes it a very versatile data structure. How to use collections.deque
How to use collections.deque
To use collections.deque, we must first import it from the collections module.
from collections import dequeOnce we have imported it, we can create a deque object by calling deque(). We can pass an iterable to the deque constructor, and it will create a deque with the elements of the iterable.
my_deque = deque([1, 2, 3, 4])We can also create an empty deque by calling deque() with no arguments.
Inserting and Removing elements
We can insert elements from either end of the deque using the append() and appendleft() methods. The append() method appends an item to the right end of the deque, while the appendleft() method appends an item to the left end of the deque.
my_deque.append(5)
my_deque.appendleft(0)This will add 5 to the right end of the deque and 0 to the left end of the deque. We can remove elements from either end of the deque using the pop() and popleft() methods.
my_deque.pop()
my_deque.popleft()This will remove and return the rightmost and leftmost elements of the deque, respectively.
Queues
Queues are another data structure that can be implemented using collections.deque. A queue is a linear data structure that follows the first-in, first-out (FIFO) policy.
In a queue, elements are added to the end of the queue and removed from the front. To implement a queue using collections.deque, we can add elements using append(), and remove elements using popleft().
queue = deque()
queue.append("apple")
queue.append("banana")
queue.append("cherry")
queue.popleft()This will create a queue starting with “apple,” followed by “banana,” and “cherry.” The popleft() method will remove the first element, in this case, “apple.”
Stacks
Stacks are another data structure that can be implemented using collections.deque. A stack is a linear data structure that follows the last-in, first-out (LIFO) policy.
To implement a stack using collections.deque, we can add elements using append() and remove elements using pop(). Here is an example:
stack = deque()
stack.append("apple")
stack.append("banana")
stack.append("cherry")
stack.pop()This will create a stack starting with “apple,” followed by “banana,” and “cherry.” The pop() method will remove the topmost element, in this case, “cherry.”
Conclusion
In conclusion, collections.deque is a versatile data structure that can be used to implement queues, stacks, and more. It provides efficient methods for inserting and removing elements from both ends of the deque, making it a powerful tool to have in your programming toolkit.
Knowing when and how to use collections.deque effectively will help you write more efficient and organized code. In this article, we have discussed linked lists and their practical applications.
Now, let’s take a closer look at how we can implement our own linked list in Python and how we can traverse it.
How to Create a Linked List
To create a linked list, we first need to define a Node class that will be used as the building block for the linked list. The Node class should have two important attributes – data and next.
class Node:
def __init__(self, data):
self.data = data
self.next = NoneThe data attribute will store the value of the node, while the next attribute will store a reference to the next node in the list. If there is no next node, the next attribute should be set to None.
Next, we need to define a Linked List class that will use Nodes to create a list. The Linked List class should have two important attributes: the head, which represents the first node in the list, and the tail, which represents the last node in the list.
class LinkedList:
def __init__(self):
self.head = None
self.tail = NoneTo add a new node to the linked list, we can create a new node and set the head or tail attributes accordingly. Here is an example of adding a node to an empty linked list:
my_linked_list = LinkedList()
new_node = Node(5)
my_linked_list.head = new_node
my_linked_list.tail = new_nodeWe can also define a method to add a new node to the end of the linked list.
class LinkedList:
def __init__():
...
def append(self, data):
new_node = Node(data)
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_nodeThe append method will check if the tail is None, indicating an empty linked list.
If it is, we set both the head and tail attributes to the new node. If it is not, we set the next attribute of the current tail to the new node and update the tail attribute to the new node.
We can define other methods to insert nodes at a specific position in the linked list or remove nodes from the linked list. However, for the purposes of this article, we will only focus on how to traverse the linked list.
How to Traverse a Linked List
Traversing a linked list means iterating over all the nodes in the list. To do this, we use a while loop that starts at the head of the linked list and continues until we reach the end of the list, which is indicated by the next attribute of the current node being None.
class LinkedList:
def __init__():
...
def traverse(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.nextThe traverse method sets a current_node variable to the head of the linked list.
It then enters a while loop that continues until the current_node is None. Inside the loop, the data of the current node is printed, and the current_node variable is updated to point to the next node in the list.
To make it more convenient to view the entire linked list, we can define a __repr__ method that returns a string representation of the linked list.
class LinkedList:
def __init__():
...
def __repr__(self):
node_list = []
current_node = self.head
while current_node is not None:
node_list.append(str(current_node.data))
current_node = current_node.next
return "->".join(node_list)The __repr__ method initializes an empty list called node_list and sets the current_node variable to the head of the linked list. It then enters a while loop that continues until the current_node is None.
Inside the loop, it appends the data of the current node to the node_list in string form. Finally, it returns a string representation of the linked list by joining the elements of the node_list with “->”.
Conclusion
In conclusion, implementing our own linked list in Python is straightforward, but it requires us to define a Node class and a Linked List class with appropriate methods. Once we have defined these classes, we can add, remove and traverse the nodes in the linked list.
By understanding how to create and traverse a linked list, we can use this powerful data structure in our programming projects. In this article, we have discussed linked lists, collections.deque and how we can implement our own linked list in Python.
We explored the main concepts of linked lists, their practical applications, and compared their performance to lists in terms of insertion, deletion, and retrieval of elements. We also discussed how collections.deque can be used to implement queues and stacks and how to create and traverse a linked list.
By understanding linked lists, collections.deque, and their implementations, we can use these powerful data structures in our programming projects. As a final thought, it is essential to consider the needs of our project and choose the data structure that best fits our needs to write efficient and organized code.