In this article, we will learn about the doubly Doubly Linked List and its implementation using Python.
A doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly-linked list, a node consists of three parts: node data, a pointer to the next node in sequence (next pointer), and a pointer to the previous node (previous pointer).A doubly linked list might be useful when working with something like a list of web pages, which has each page containing a picture, a link to the previous page, and a link to the next page. For a simple list of numbers, a linked list and a doubly-linked list may look the same, e.g., [3, 1, 4, 2, 5]. However, the doubly linked list also has an easy way to get the previous element, as well as the next element.
class Node(object):
""" A Doubly-linked lists' node. """
def __init__(self, data=None, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev
class DoublyLinkedList(object):
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def append(self, data):
""" Append an item to the list. """
new_node = Node(data, None, None)
if self.head is None:
self.head = new_node
self.tail = self.head
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.count += 1
def iter(self):
""" Iterate through the list. """
current = self.head #note subtle change
while current:
val = current.data
current = current.next
yield val
def reverse_iter(self):
""" Iterate backwards through the list. """
current = self.tail
while current:
val = current.data
current = current.prev
yield val
def delete(self, data):
""" Delete a node from the list. """
current = self.head
node_deleted = False
if current is None:
node_deleted = False
elif current.data == data:
self.head = current.next
self.head.prev = None
node_deleted = True
elif self.tail.data == data:
self.tail = self.tail.prev
self.tail.next = None
node_deleted = True
else:
while current:
if current.data == data:
current.prev.next = current.next
current.next.prev = current.prev
node_deleted = True
current = current.next
if node_deleted:
self.count -= 1
def search(self, data):
"""Search through the list. Return True if data is found, otherwise False."""
for node in self.iter():
if data == node:
return True
return False
def print_foward(self):
""" Print nodes in list from first node inserted to the last . """
for node in self.iter():
print(node)
def print_backward(self):
""" Print nodes in list from latest to first node. """
current = self.tail
while current:
print(current.data)
current = current.prev
def insert_head(self, data):
""" Insert new node at the head of linked list. """
if self.head is not None:
new_node = Node(data, None, None)
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.count += 1
def reverse(self):
""" Reverse linked list. """
current = self.head
while current:
temp = current.next
current.next = current.prev
current.prev = temp
current = current.prev
# Now reverse the order of head and tail
temp = self.head
self.head = self.tail
self.tail = temp
def __getitem__(self, index):
if index > self.count - 1:
raise Exception("Index out of range.")
current = self.head # Note subtle change
for n in range(index):
current = current.next
return current.data
def __setitem__(self, index, value):
if index > self.count - 1:
raise Exception("Index out of range.")
current = self.head # Note subtle change
for n in range(index):
current = current.next
current.data = value
dll = DoublyLinkedList()
dll.append("foo")
dll.append("bar")
dll.append("biz")
dll.append("whew")
print("Items in List : ")
dll.print_foward()
print("List after deleting node with data whew")
dll.delete("whew")
dll.print_foward()
print("List count: {}".format(dll.count))
print("Print list backwards")
dll.print_backward()
print("Reverse list ")
dll.reverse()
dll.print_foward()
print("Append item to front of list")
dll.insert_head(55)
dll.print_foward()
print("Get First element: {}".format(dll[0]))
Output:
Items in List :
foo
bar
biz
whew
List after deleting node with data whew
foo
bar
biz
List count: 3
Print list backwards
biz
bar
foo
Reverse list
biz
bar
foo
Append item to front of list
55
biz
bar
foo
Get First element: 55
Related Data Structures in Python
- Stack Implementation in Python
- Queue Implementation in Python
- Deque Implementation in Python
- Singly Linked List Implementation in Python
- Doubly Linked List Implementation in Python
- Circular Linked List Implementation in Python
- PriorityQueue Implementation in Python
- Circular Queue Implementation in Python
- Binary Search Tree Implementation in Python
- Stack Implementation Using Linked List in Python
- Stack Implementation Using Doubly Linked List in Python
DSA
Python
Comments
Post a Comment