Зміст курсу
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
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))
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.
Дякуємо за ваш відгук!
