Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Doubly Linked List | List and Array
Algorithms and Data Structures Overview

book
Doubly Linked List

The linked list is a versatile data structure, free from the "holes" inherent in arrays.
Manipulating the first element is efficient, but for certain abstract data types like queues, efficient manipulation of the last element and bidirectional traversal are needed. Standard linked lists struggle with accessing the last element, requiring O(N) time complexity.
Doubly linked lists resolve this limitation and offer solutions to various other challenges.

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

The doubly linked list's nodes contain the references to the next and to the previous elements. Therefore we can access the first and the last item in O(1) constant running time. Time complexity of all other operations for doubly linked list is the same as for the simple linked list.

python
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:
question mark

What advantage does a doubly linked list offer over a singly linked list?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 2. Розділ 7
some-alt