Introduction to Doubly Linked List
Doubly Linked List is a data structure that is used to store and manage a collection of nodes. These nodes contain data and links that connect them to other nodes, both in front and behind them.
This feature sets them apart from the Singly Linked List, where nodes are connected one way only, to the node that follows them. In this article, we will discuss the definition and features of Doubly Linked Lists, compare them to Singly Linked Lists, and explain how to implement them in Python.
We will also cover the various methods used to manipulate the list, such as Append, Insert, and Remove. In addition, we will explore the concept of Index, Size, and Display that are fundamental in managing the list.
Definition and Features of Doubly Linked List
Doubly Linked List is a data structure that contains nodes that are linked to their previous and next nodes. The nodes are objects that contain data and links.
The links are two-way, allowing each node to point to the one that follows it and the one that precedes it. This type of linking allows for efficient traversing, both forward and backward, making the structure very useful in certain applications.
Unlike in Singly Linked Lists, where each node is connected to a single node following it, Doubly Linked Lists allow for bidirectional connections. This feature makes it easy to move from one node to another in either direction.
However, this comes at the cost of using more memory than Singly Linked Lists, as each node contains a reference to its preceding node.
Comparison with Singly Linked List
One significant difference between Singly and Doubly Linked Lists is the way nodes are connected. In a Singly Linked List, nodes are linked one way only, with each node connected to the one following it.
This means that traversing the list is only possible in one direction, from the head towards the tail. In contrast, Doubly Linked Lists provide bidirectional connections, allowing for traversing in both directions.
This means that you can easily move to a node preceding or following the current node, making the list very flexible. This feature comes in handy when searching, sorting, or deleting nodes in the list.
Structure of a Doubly Linked List
Each node in a Doubly Linked List contains a reference to its preceding and following nodes, also known as the previous and next pointers. Besides, each node contains a data element that represents the value being stored.
The list itself contains two pointers, namely the head and the tail. The head points to the first node, and the tail points to the last node, making it easier to traverse the list efficiently.
Implementing Doubly Linked List in Python
Node Class
A Node class represents each node in the list. It contains an instance variable called data that stores the node’s value and two pointers, namely the next and previous pointers.
“`
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
“`
Doubly Linked List Class
The Doubly Linked List class represents the list itself and its various operations. It contains pointer variables, head and tail, to the first and last nodes in the list.
Additionally, the class consists of a counter that keeps track of the number of nodes in the list. “`
class DLL:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
“`
Append and Insert methods
The Append method adds a new node to the end of the list. The Insert method, on the other hand, adds a new node at a specified index.
If the index is invalid, the method raises a ValueError. “`
def append(self, data):
new_node = Node(data)
if self.count == 0:
self.head = self.tail = new_node
else:
new_node.prev = self.tail
new_node.next = None
self.tail.next = new_node
self.tail = new_node
self.count +=
1
def insert(self, index, data):
if index > self.count or index < 0:
raise ValueError(“Index out of range”)
new_node = Node(data)
if self.count == 0:
self.head = self.tail = new_node
elif index == 0:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
elif index == self.count:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
else:
temp_node = self.head
for i in range(index –
1):
temp_node = temp_node.next
new_node.prev = temp_node
new_node.next = temp_node.next
temp_node.next.prev = new_node
temp_node.next = new_node
self.count +=
1
“`
Remove method
The
Remove method deletes a node at a specified index. If the index is invalid, the method raises a ValueError.
Additionally, it handles the unlinking of the node from its preceding and following nodes. The garbage collection module deletes the node from the memory.
“`
def remove(self, index):
if index >= self.count or index < 0:
raise ValueError(“Index out of range”)
temp_node = self.head
for i in range(index):
temp_node = temp_node.next
if index == 0:
self.head = temp_node.next
if self.head:
self.head.prev = None
elif index == self.count –
1:
self.tail = temp_node.prev
if self.tail:
self.tail.next = None
else:
temp_node.prev.next = temp_node.next
temp_node.next.prev = temp_node.prev
del temp_node
self.count -=
1
“`
Index, Size, and Display methods
The Index method returns the index of the first occurrence of the value in the list. If the value is not present in the list, the method returns –
1.
The Size method returns the number of nodes in the list. The Display method prints the list values to the console.
“`
def index(self, data):
temp_node = self.head
for i in range(self.count):
if temp_node.data == data:
return i
temp_node = temp_node.next
return –
1
def size(self):
return self.count
def display(self):
temp_node = self.head
while temp_node:
print(temp_node.data)
temp_node = temp_node.next
“`
Conclusion
In conclusion, Doubly Linked List is a powerful data structure that allows bidirectional connections between nodes, making it an efficient way to manage and store data. In this article, we have discussed the definition, features, and implementation of Doubly Linked List in Python.
We have also explored the methods used to manipulate the list, such as Append, Insert, and Remove, as well as the importance of Size, Display, and Index. Hopefully, this article has provided the necessary knowledge to begin using Doubly Linked Lists in your projects.
Review of the Output of the Code
When implementing a data structure such as Doubly Linked List, it is crucial to understand the output produced by the code. The output gives you an insight into how the code is working, which can be useful when debugging or optimizing your code.
In this section, we will review the output of the code used to implement Doubly Linked List in Python. We will examine the various methods used in the code and look at the output they generate under different conditions.
Additionally, we will explore the significance of the output and how it can help in understanding the code.
Node Class
The
Node Class defines the structure of each node in the list. It consists of an instance variable called data that represents the value being stored in the node.
The class also contains two pointers, known as next and prev, which point to the next and previous nodes, respectively. When a new node is created, the output reflects the creation of a new instance of the Node class.
For example, when the following code is executed:
“`
new_node = Node(5)
print(new_node)
“`
The output will be:
“`
<__main__.Node object at 0x00000
1>
“`
This output indicates that a new instance of the Node class has been created, and it has been assigned a memory address. The memory address is a unique identifier that represents the location of the object in the memory.
Doubly Linked List Class
The
Doubly Linked List Class represents the list itself. It contains two pointers, head and tail, which point to the first and last nodes in the list, respectively.
The class also contains a counter that keeps track of the number of nodes in the list. When a new instance of the DLL class is created, the output indicates the creation of the class and its associated attributes.
For example, when the following code is executed:
“`
dll = DLL()
print(dll)
“`
The output will be:
“`
<__main__.DLL object at 0x000002>
“`
This output indicates that a new instance of the DLL class has been created and has been assigned a memory address.
Append Method
The Append method adds a new node to the end of the list. When a new node is created using the Append method, the output reflects the creation of a new instance of the Node class and the update of the list pointer variables, head and tail.
For example, when the following code is executed:
“`
dll = DLL()
dll.append(5)
print(dll.head.data)
print(dll.tail.data)
“`
The output will be:
“`
5
5
“`
This output indicates that a new instance of the Node class has been created with a value of 5, and it has been added to the end of the list. The head and tail pointers are pointing to the same node, which contains a value of 5.
Insert Method
The Insert method adds a new node at a specific index. When a new node is created using the Insert method, the output reflects the creation of a new instance of the Node class and the update of the list pointer variables, head and tail.
For example, when the following code is executed:
“`
dll = DLL()
dll.append(
3)
dll.insert(0, 2)
print(dll.head.data)
print(dll.tail.data)
“`
The output will be:
“`
2
3
“`
This output indicates that a new instance of the Node class has been created with a value of 2, and it has been added to the beginning of the list. The head pointer is pointing to the node with value 2, and the tail pointer is pointing to the node with value
3, which is the last node in the list.
Remove Method
The
Remove method deletes a node at a specific index. When a node is removed from the list using the
Remove method, the output reflects the removal of the node and the subsequent update of the list pointer variables, head and tail.
For example, when the following code is executed:
“`
dll = DLL()
dll.append(
3)
dll.append(4)
dll.remove(
1)
print(dll.head.data)
print(dll.tail.data)
“`
The output will be:
“`
3
3
“`
This output indicates that the node with value 4 has been removed from the list, and the head and tail pointers are now pointing to the same node, which contains a value of
3. This is because there is only one node left in the list after the removal of the node with value 4.
Index, Size, and Display Methods
The Index method returns the index of the first occurrence of the value in the list. The Size method returns the number of nodes in the list.
The Display method prints the list values to the console. When the Index method is called, the output reflects the index of the specified value or –
1 if the value is not present in the list.
For example, when the following code is executed:
“`
dll = DLL()
dll.append(
3)
dll.append(4)
dll.append(5)
print(dll.index(4))
“`
The output will be:
“`
1
“`
This output indicates that the value 4 is present in the list, and its index is
1. When the Size method is called, the output reflects the current number of nodes in the list.
For example, when the following code is executed:
“`
dll = DLL()
dll.append(
3)
dll.append(4)
dll.append(5)
print(dll.size())
“`
The output will be:
“`
3
“`
This output indicates that there are currently three nodes in the list. When the Display method is called, the output reflects the values stored in each node in the list.
For example, when the following code is executed:
“`
dll = DLL()
dll.append(
3)
dll.append(4)
dll.append(5)
dll.display()
“`
The output will be:
“`
3
4
5
“`
This output displays the list values in a line-separated manner.
Conclusion
In conclusion, understanding the output of the code is essential when implementing a data structure such as Doubly Linked List. It provides insight into how the code is working, and it can be useful when debugging or optimizing your code.
In this article, we have reviewed the output of the methods used to implement Doubly Linked List in Python and examined their significance in understanding the code. The knowledge gained from this article should help in creating efficient and effective data structures in future projects.
In summary, this article has provided an overview of Doubly Linked List, its definition, features, and how to implement it in Python. We compared it with Singly Linked List, highlighted the structure of a Doubly Linked List, and outlined the various methods in Python, including Append, Insert, Remove, Index, Size, and Display.
Additionally, we reviewed the output generated by the code for these methods. Understanding the output is crucial as it provides insight into how the code works, facilitating efficient debugging.
Overall, this article emphasizes the importance of using effective data structures and highlights the benefits that Doubly Linked List offers. It leaves the readers with an understanding of the fundamental concepts of Doubly Linked List and the tools in Python’s toolkit to utilize them effectively in their projects.