Главная » Руководства

Двусвязный список

На чтение 15 мин. Просмотров 17 Опубликовано

Вот чем он отличается от односвязного списка
Односвязный список

Двусвязный список

Итак, при создании узла в односвязном списке у нас было вот что:


На самом деле у нас было


Что мы и написали в классе:

B
Но в дважды связанном списке мы будем иметь :

Теперь давайте создадим класс Doubly Linked List.

Мы создадим дважды связанный список, вызвав класс:


Это создает дважды связанный список:

весь код:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

#Creating a doubly Linked List which has a node 7
my_doubly_linked_list = DoublyLinkedList(7)

#Printing the list
my_doubly_linked_list.print_list()
Вход в полноэкранный режим Выход из полноэкранного режима

Добавить
Случай 1:
Когда нет значения и добавляется одно

и превращаем это в это


Сначала мы проверим, указывает ли head на None:


Сделаем это


Случай 2:


Теперь мы запишем код this для добавления нового узла.


Итак, общий код:


Общий код:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

#A linked list of a node 1
my_doubly_linked_list = DoublyLinkedList(1)
#Appending node 2
my_doubly_linked_list.append(2)

my_doubly_linked_list.print_list()
Войти в полноэкранный режим Выход из полноэкранного режима

Открыть

Случай 1:
Если список имеет 0 узлов


Для этого мы будем иметь:
Потому что мы ничего не вернем

Случай 2: Если у нас более 2 значений


Сначала мы создадим временную переменную


Затем мы установим tail на предыдущий узел:


Затем мы установим следующее направление хвоста в None, чтобы отделить его от последнего элемента:


то же самое для последнего узла:

Случай 3:
Когда у нас есть только 1 значение:

Мы выберем его и также установим для головы и хвоста значение None:

Список будет выглядеть примерно так:

Таким образом, код будет выглядеть следующим образом:

Также мы можем изменить его на такой формат:

Итого код:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        #For 0 items in list
        if self.length == 0:
            return None
        temp = self.tail
        #For 1 items in list
        if self.length == 1:
            self.head = None
            self.tail = None 
        #For more than 1 nodes in list
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

#Creates a list of Node 1 & Node 2

my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(2)


# (2) Items - Returns  Node 2
print(my_doubly_linked_list.pop())
# (1) Item -  Returns  Node 1
print(my_doubly_linked_list.pop())
# (0) Items - Returns  None
print(my_doubly_linked_list.pop())
Вход в полноэкранный режим Выйти из полноэкранного режима

Вставьте

Случай: 1
Когда у нас ничего нет в списке


Поэтому мы установим head & tail:


Случай 2:
Если у нас более 1 значения:


Сначала мы сделаем следующее:


затем


тогда

Итого код становится:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        # If we have no value in the list
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        #If we have more than 1 values
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

#Doubly list with Node 1 & Node 3
my_doubly_linked_list = DoublyLinkedList(2)
my_doubly_linked_list.append(3)

#Prepending Node 1
my_doubly_linked_list.prepend(1)

my_doubly_linked_list.print_list()
Вход в полноэкранный режим Выйти из полноэкранного режима

Получить
Для односвязного списка у нас был правильный код:

Далее мы преобразуем его следующим образом

Случай 1:
Давайте вернем что-то, что находится внутри Двусвязного списка. Вернем индекс 1


Если индекс находится в 1-й половине


если во 2-й половине

S
задаем хвост как temp и итерируем в обратном направлении


и вернем значение temp, когда получим это.

Таким образом, общий код будет следующим

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        #Checking if the index is in 1st half
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        #Checking if the index is in 2nd half
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp #Will return the node . But for value, use temp.value

#Creating a doubly list of 0,5,9,3
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(5)
my_doubly_linked_list.append(9)
my_doubly_linked_list.append(3)


#Lokking for index 1 no node
print(my_doubly_linked_list.get(1))

#Looking for index 2 no node
print(my_doubly_linked_list.get(2))
Вход в полноэкранный режим Выйти из полноэкранного режима

Установить
Давайте установим значение индекса 1 от 3 до 4.


Итак, здесь мы собираемся проверить, находится ли индекс в пределах диапазона, и если да, то мы изменим значение.


в противном случае вернется False

Весь код выглядит следующим образом

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        #if the index is within the range
        if temp:
            temp.value = value
            return True
        #if the index is not within range    
        return False

#Doubly linked list of 11,3,23,7  
my_doubly_linked_list = DoublyLinkedList(11)
my_doubly_linked_list.append(3)
my_doubly_linked_list.append(23)
my_doubly_linked_list.append(7)


#setting index value to 4

my_doubly_linked_list.set_value(1,4)

my_doubly_linked_list.print_list()
Вход в полноэкранный режим Выйти из полноэкранного режима

Вставить

По определенному индексу мы собираемся вставить узел.
Сначала мы проверим, находится ли индекс в диапазоне

Случай 1:
Если необходимо, добавьте его в начало

Случай 2:
Добавление в последнюю строку списка

случай 3:
Добавление где-то в середине.
Предположим, что мы хотим добавить

к этому

то есть попытаемся вставить узел между 1 & 2.
Таким образом, мы установим индекс 1 на before, а индекс 2 на after.

Мы собираемся сделать это


к этому

Итак, код

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def insert(self, index, value):
        #to check if the index is within range
        if index < 0 or index > self.length:
            return False
        #to add a node at the start
        if index == 0:
            return self.prepend(value)
        #to add a node at the end    
        if index == self.length:
            return self.append(value)
        #to add a node within the list
        new_node = Node(value)
        before = self.get(index - 1)
        after = before.next

        new_node.prev = before
        new_node.next = after
        before.next = new_node
        after.prev = new_node

        self.length += 1   
        return True  


#Doubly linked list of nodes 1 ,3
my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(3)



#at the index 1, adding node 2
my_doubly_linked_list.insert(1,2)

my_doubly_linked_list.print_list()
Войти в полноэкранный режим Выйти из полноэкранного режима

Удалить

Проверка выхода индекса за пределы диапазона


Случай 1:
Возврат первого элемента.


от этого к этому


Для этого мы просто выберем


Случай 2:
Удалить из последнего.


Случай 3:
Чтобы удалить что-то из середины


Например, мы удалим значение числа с индексом 2. Во-первых, укажем на него переменную


Которая может быть следующей


используя

Итоговый код будет выглядеть следующим образом

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def insert(self, index, value):
        if index < 0 or index > self.length:
            return False
        if index == 0:
            return self.prepend(value)
        if index == self.length:
            return self.append(value)

        new_node = Node(value)
        before = self.get(index - 1)
        after = before.next

        new_node.prev = before
        new_node.next = after
        before.next = new_node
        after.prev = new_node

        self.length += 1   
        return True  

    def remove(self, index):
        #Checking the range
        if index < 0 or index >= self.length:
            return None
        #to remove from the beginning    
        if index == 0:
            return self.pop_first()
        #to remove from the last    
        if index == self.length - 1:
            return self.pop()

        #to remove from the middle of the doubly linked list
        temp = self.get(index)

        temp.next.prev = temp.prev
        temp.prev.next = temp.next
        temp.next = None
        temp.prev = None

        self.length -= 1
        return temp

# a doubly linked list of 0,1 & 2 nodes
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(1)
my_doubly_linked_list.append(2)


# removing index 1 out of the list
print(my_doubly_linked_list.remove(1), 'n')

my_doubly_linked_list.print_list()
Вход в полноэкранный режим Выйти из полноэкранного режима

Готово!

Рекомендуем почитать:

Оцените статью
Procodings.ru
Добавить комментарий