doubly linked list Algorithm
A doubly linked list is a data structure that consists of a sequence of elements, where each element contains a reference to the previous and the next element in the sequence. It is a variation of the singly linked list, which only contains a reference to the next element. The doubly linked list algorithm is an efficient way to manage and manipulate a collection of elements since it allows for easy insertion and deletion of elements at any position in the list.
The algorithm for a doubly linked list comprises several fundamental operations, such as creating a new list, inserting elements at the beginning, end, or a specific position, deleting elements, searching for elements, and traversing the list. The key to the algorithm's efficiency lies in the use of two pointers for each element, one pointing to the previous element (prev) and the other pointing to the next element (next) in the list. When inserting or deleting elements, the algorithm updates the pointers of the adjacent elements to maintain the correct sequence. This bidirectional referencing system allows for quicker access and manipulation of elements within the list, particularly when working with large data sets or when the list needs to be traversed in reverse order.
"""
- A linked list is similar to an array, it holds values. However, links in a linked
list do not have indexes.
- This is an example of a double ended, doubly linked list.
- Each link references the next link and the previous one.
- A Doubly Linked List (DLL) contains an extra pointer, typically called previous
pointer, together with next pointer and data which are there in singly linked list.
- Advantages over SLL - IT can be traversed in both forward and backward direction.,
Delete operation is more efficient"""
class LinkedList: # making main class named linked list
def __init__(self):
self.head = None
self.tail = None
def insertHead(self, x):
newLink = Link(x) # Create a new link with a value attached to it
if self.isEmpty(): # Set the first element added to be the tail
self.tail = newLink
else:
self.head.previous = newLink # newLink <-- currenthead(head)
newLink.next = self.head # newLink <--> currenthead(head)
self.head = newLink # newLink(head) <--> oldhead
def deleteHead(self):
temp = self.head
self.head = self.head.next # oldHead <--> 2ndElement(head)
# oldHead --> 2ndElement(head) nothing pointing at it so the old head will be
# removed
self.head.previous = None
if self.head is None:
self.tail = None # if empty linked list
return temp
def insertTail(self, x):
newLink = Link(x)
newLink.next = None # currentTail(tail) newLink -->
self.tail.next = newLink # currentTail(tail) --> newLink -->
newLink.previous = self.tail # currentTail(tail) <--> newLink -->
self.tail = newLink # oldTail <--> newLink(tail) -->
def deleteTail(self):
temp = self.tail
self.tail = self.tail.previous # 2ndLast(tail) <--> oldTail --> None
self.tail.next = None # 2ndlast(tail) --> None
return temp
def delete(self, x):
current = self.head
while current.value != x: # Find the position to delete
current = current.next
if current == self.head:
self.deleteHead()
elif current == self.tail:
self.deleteTail()
else: # Before: 1 <--> 2(current) <--> 3
current.previous.next = current.next # 1 --> 3
current.next.previous = current.previous # 1 <--> 3
def isEmpty(self): # Will return True if the list is empty
return self.head is None
def display(self): # Prints contents of the list
current = self.head
while current is not None:
current.displayLink()
current = current.next
print()
class Link:
next = None # This points to the link in front of the new link
previous = None # This points to the link behind the new link
def __init__(self, x):
self.value = x
def displayLink(self):
print(f"{self.value}", end=" ")
