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))


              1234567891011121314151617181920212223
            
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.


python
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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:

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 7

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen