Kursinhalt
Überblick Über Algorithmen und Datenstrukturen
Überblick Über Algorithmen und Datenstrukturen
Doppelt Verkettete Liste
Die verkettete Liste ist eine vielseitige Datenstruktur, frei von den "Löchern", die in Arrays vorhanden sind.
Die Manipulation des ersten Elements ist effizient, aber für bestimmte abstrakte Datentypen wie Warteschlangen sind effiziente Manipulation des letzten Elements und bidirektionale Durchläufe erforderlich. Standard-verkettete Listen haben Schwierigkeiten beim Zugriff auf das letzte Element, was eine Zeitkomplexität von O(N) erfordert.
Doppelt verkettete Listen lösen diese Einschränkung und bieten Lösungen für verschiedene andere Herausforderungen.
from lolviz import * from IPython.display import display_png class Node: def __init__(self, data): self.value = data self.next = None self.previous = None # Let's create some nodes node1 = Node(1) node2 = Node(2) node3 = Node(3) # Then let's couple them into a linked list node1.next = node2 node2.next = node3 # And don't forget to assign the reference to a previous node node2.previous = node1 node3.previous = node2 display_png(objviz(node1))
Die Knoten der doppelt verketteten Liste enthalten die Referenzen auf die nächsten und vorherigen Elemente. Daher können wir auf das erste und das letzte Element in O(1) konstanter Laufzeit zugreifen. Die Zeitkomplexität aller anderen Operationen für die doppelt verkettete Liste ist die gleiche wie für die einfach verkettete Liste.
def search(self, value):
# Start the search from the head of the linked list
current = self.head
# Traverse the linked list
while current:
# Check if the value of the current node matches the target value
if current.data == value:
# Return the node if found
return current
# Move to the next node
current = current.next
# Return None if the value is not found in the linked list
return None
def insert(self, value):
# Create a new node with the given value
new_node = ListNode(value)
# Check if the linked list is empty
if not self.head:
# If the linked list is empty, set the new node as the head
self.head = new_node
else:
# If the linked list is not empty, insert the new node at the beginning
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def delete(self, value):
# Start the search from the head of the linked list
current = self.head
# Traverse the linked list
while current:
# Check if the value of the current node matches the target value
if current.data == value:
# Update the pointers of the surrounding nodes to skip the current node
if current.prev:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
# Update the head pointer if the current node is the head
if current == self.head:
self.head = current.next
# Exit the method after deleting the node
return
# Move to the next node
current = current.next
Danke für Ihr Feedback!
