Двухсвязные списки — это важная структура данных, обеспечивающая эффективные операции вставки и удаления. В этой статье блога мы рассмотрим различные методы вставки элементов в двусвязный список. Мы будем использовать разговорный язык и приводить примеры кода, чтобы облегчить процесс обучения. Итак, давайте углубимся и освоим искусство вставки элементов в двусвязный список!

Метод 1: вставка в заголовок
Один из самых простых способов вставки элемента в двусвязный список — вставка его в заголовок. Этого можно добиться, выполнив следующие действия:

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head

        if self.head is not None:
            self.head.prev = new_node

        self.head = new_node

Метод 2: вставка в хвост
Другой распространенный метод — вставка элемента в хвост двусвязного списка. Для этого необходимо выполнить следующие шаги:

class DoublyLinkedList:
    # previous code...

    def insert_at_tail(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        current = self.head
        while current.next is not None:
            current = current.next

        current.next = new_node
        new_node.prev = current

Метод 3: вставка в определенную позицию
Иногда вам может потребоваться вставить элемент в определенную позицию в двусвязном списке. Вот как это можно сделать:

class DoublyLinkedList:
    # previous code...

    def insert_at_position(self, data, position):
        if position <= 0:
            self.insert_at_head(data)
            return

        new_node = Node(data)
        current = self.head
        count = 0

        while current is not None and count < position:
            current = current.next
            count += 1

        if current is None:
            self.insert_at_tail(data)
            return

        new_node.prev = current.prev
        new_node.next = current
        current.prev.next = new_node
        current.prev = new_node

Метод 4: вставка в отсортированном виде
Если ваш двусвязный список отсортирован, вы можете вставлять элементы, сохраняя отсортированный порядок. Вот пример:

class DoublyLinkedList:
    # previous code...

    def insert_sorted(self, data):
        new_node = Node(data)

        if self.head is None or self.head.data >= new_node.data:
            new_node.next = self.head

            if self.head is not None:
                self.head.prev = new_node

            self.head = new_node
            return

        current = self.head
        while current.next is not None and current.next.data < new_node.data:
            current = current.next

        new_node.next = current.next
        new_node.prev = current
        current.next = new_node

        if new_node.next is not None:
            new_node.next.prev = new_node

В этой статье мы рассмотрели несколько методов вставки элементов в двусвязный список. Мы рассмотрели вставку в начале, в хвосте, в определенной позиции и в сортированном виде. Освоив эти методы, вы сможете эффективно манипулировать двусвязными списками в своих программах. Не забудьте выбрать подходящий метод в зависимости от ваших требований и характеристик ваших данных. Приятного кодирования!