Как скопировать связанный список в Python?

создание эффективных программ на Python Программирование и разработка

Связанные списки — это тип » абстрактных типов данных » в Python. Эти структуры данных носят линейный характер. Связанные списки отличаются от списков, поскольку связанные списки хранятся в несмежной (несплошной) памяти, тогда как списки, напротив, хранятся в непрерывных (непрерывных) блоках памяти. Элементы, хранящиеся в связанных списках, имеют форму узлов. Каждый узел состоит из двух частей: данных и указателя на следующий узел.

Создание связанного списка в Python

Здесь мы будем создавать собственный связанный список. Давайте посмотрим на шаги ниже, чтобы сделать это:

  • Прежде всего, мы создадим класс Node, который будет состоять из двух частей: Data и Next.
  • Затем мы создадим класс связанного списка, который будет иметь self.head
  • Мы также добавим магический метод ’__str__’, чтобы пользователь мог распечатать созданный им связанный список.
  • После создания этого мы добавим в наш класс метод add_node, чтобы пользователи могли добавлять узлы в свой связанный список.
  • Здесь мы также создадим метод «изменить», который позволит пользователям изменить определенный элемент в своем связанном списке на желаемый элемент.

Вот как мы создадим наш связанный список. Ниже приведена реализация вышеупомянутой идеи:

Python3

# Creating a 'Node' class that contains two 
# arguments, viz. data and next
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
 
# Creating a 'Linked List' class
class LinkedList:
    # getting any number of arguments in our Linked List
    def __init__(self, *args):
        # self.head will store the head of our Linked List.
        # self.head is initialised to None as we don't have any head of the Linked List
        # initially.
        self.head = None
        # converting every passed argument in our Linked List to a Node
        for arg in args:
            node = Node(data = arg, next = self.head) # passing self.head as the 'next' parameter
            # setting self.head as node
            self.head = node
     
    # dunder method to enable users to print their Linked Lists
    def __str__(self):
        llist = '['
        itr = self.head
        if itr == None:
            llist += ']'
        else:
            while itr != None:
                llist += f'[{itr.data}]'
                if itr.next != None:
                    llist += ' -> '
                itr = itr.next
            llist += ']'
        return llist
     
    # adding 'add_node' method to enable users to add a new node to their Linked List
    def add_node(self, data):
        new_node = Node(data, next = self.head)
        # setting the self.head as the newly added node
        self.head = new_node
         
    # adding 'change' method with 'index' and 'with_element' parameters.
    # The 'index' parameter is basically the index number of the element which you want
    # to change.
    # The 'with_element' parameter is the string or element which you want to replace the 
    # given element with. 
    def change(self, index, with_element):
        itr = self.head
        if itr == None:
            return '[]'
        else:
            i =
            while i <= index:
                if i == index:
                    itr.data = with_element
                    break
                else:
                    i += 1
                    itr = itr.next
 
 
# creating the Linked List
linked_list = LinkedList('One', 'Two', 'Three')
 
# adding a node
linked_list.add_node('Four')
 
# changing an element in the Linked List
linked_list.change(2, 2)
 
# Printing the Linked List
print(linked_list)

Вывод

[[Four] -> [Three] -> [2] -> [One]]

Копирование связанного списка в Python

Теперь, когда мы закончили с нашей вводной частью, давайте начнем с нашей основной темы: «Как мы копируем связанные списки?» В этом разделе мы рассмотрим два типа копирования: поверхностное и глубокое копирование. Кроме того, мы рассмотрим реализацию функций связанных списков, которые мы используем для мелкого и глубокого копирования в Python. Наконец, мы рассмотрим различия между связанными списками с глубоким копированием и связными списками с поверхностным копированием с помощью примеров.

Что такое поверхностная копия?

При поверхностном копировании объект копируется в другую переменную, но на вложенные объекты просто ссылаются. Когда у нас есть вложенные списки в списке, эти объекты вложенного списка копируются, но элементы внутри него только ссылаются, а не копируются полностью. Это означает, что исходный объект и скопированный объект ссылаются на одни и те же вложенные элементы объекта. Поэтому изменения, сделанные одним объектом среди исходного и скопированного объекта в элементах вложенного объекта, будут видны и в другом объекте.

Что такое глубокое копирование?

В Deep Copy объекты копируются полностью. Это означает, что вложенные объекты копируются в отдельные области памяти, а не просто ссылаются на них. Это означает, что изменения, внесенные в элементы вложенного объекта исходным объектом, НЕ будут видны в скопированном объекте и наоборот.

Метод копирования в Python включает две функции:

  • Функция copy.copy() (используется в неглубоком копировании)
  • Функция copy.deepcopy() (используется в глубоком копировании)

Неглубокое копирование связанного списка с использованием функции copy.copy():

Здесь мы немного поговорим о модуле копирования и функции copy.copy().

Копировать модуль:

Модуль копирования имеет две функции для копирования объектов в Python. Он предоставляет функции для мелкого и глубокого копирования объектов в Python.

Читайте также:  Платежный шлюз: что это такое, как он работает, сравнение лучших шлюзов

Функция copy.copy(): функция copy.copy() используется для поверхностного копирования объекта. Неглубокое копирование любого объекта можно легко выполнить с помощью функции copy.copy().

Теперь, когда мы знаем модуль копирования и функцию copy.copy(), мы рассмотрим, как мы можем реализовать их в нашем связанном списке.

Прежде всего, мы импортируем модуль копирования. Затем мы создадим объект deque для использования в качестве нашего связанного списка и сохраним его в нашей переменной. Наконец, мы создадим переменную и используем функцию copy.copy() с переменной связанного списка в качестве параметра.

Ниже приведен пример, который показывает нам, как это сделать.

Python3

# importing copy function from copy module
from copy import copy
 
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
 
class LinkedList:
    def __init__(self, *args):
        self.head = None
        for arg in args:
            node = Node(data = arg, next = self.head)
            self.head = node
     
    def __str__(self):
        llist = '['
        itr = self.head
        if itr == None:
            llist += ']'
        else:
            while itr != None:
                llist += f'[{itr.data}]'
                if itr.next != None:
                    llist += ' -> '
                itr = itr.next
            llist += ']'
        return llist
     
    def add_node(self, data):
        new_node = Node(data, next = self.head)
        self.head = new_node
         
    def change(self, index, with_element):
        itr = self.head
        if itr == None:
            return '[]'
        else:
            i =
            while i <= index:
                if i == index:
                    itr.data = with_element
                    break
                else:
                    i += 1
                    itr = itr.next
 
 
# creating the Linked List
linked_list = LinkedList('One', 'Two', 'Three')
 
# adding a new node to the Linked List
linked_list.add_node('Four')
 
# shallow copying the Linked List
shallow_copy = copy(linked_list)
 
# Printing the Linked Lists
print('Original Linked List: ', linked_list) 
print('Shallow Copied Linked List: ', shallow_copy)

Вывод

Original Linked List:  [[Four] -> [Three] -> [Two] -> [One]]
Shallow Copied Linked List:  [[Four] -> [Three] -> [Two] -> [One]]

Глубокое копирование связанного списка

Теперь, когда мы знаем, что такое глубокое копирование, давайте посмотрим, как мы можем на самом деле глубоко скопировать связанный список в Python. Перед этим давайте посмотрим, что такое функция copy.deepcopy().

Функция copy.deepcopy(): функция deepcopy() присутствует в модуле копирования. С помощью функции copy.deepcopy() мы можем глубоко копировать объекты в Python.

Давайте теперь посмотрим, как мы можем глубоко скопировать связанный список с помощью приведенных ниже примеров.

Здесь мы глубоко скопируем наш связанный список. Итак, первый шаг — импортировать модуль копирования. Затем мы создадим связанный список и глубоко скопируем его в другую переменную с помощью функции copy.deepcopy().

Python3

# importing copy function from copy module
from copy import deepcopy
 
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
 
class LinkedList:
    def __init__(self, *args):
        self.head = None
        for arg in args:
            node = Node(data = arg, next = self.head)
            self.head = node
     
    def __str__(self):
        llist = '['
        itr = self.head
        if itr == None:
            llist += ']'
        else:
            while itr != None:
                llist += f'[{itr.data}]'
                if itr.next != None:
                    llist += ' -> '
                itr = itr.next
            llist += ']'
        return llist
     
    def add_node(self, data):
        new_node = Node(data, next = self.head)
        self.head = new_node
         
    def change(self, index, with_element):
        itr = self.head
        if itr == None:
            return '[]'
        else:
            i =
            while i <= index:
                if i == index:
                    itr.data = with_element
                    break
                else:
                    i += 1
                    itr = itr.next
 
 
# creating the Linked List
linked_list = LinkedList('One', 'Two', 'Three')
 
# adding a new node to the Linked List
linked_list.add_node('Four')
 
# deep copying the Linked List
deep_copy = deepcopy(linked_list)
 
# Printing the Linked Lists
print('Original Linked List: ', linked_list) 
print('Deep Copied Linked List: ', deep_copy)

Вывод

Original Linked List:  [[Four] -> [Three] -> [Two] -> [One]]
Deep Copied Linked List:  [[Four] -> [Three] -> [Two] -> [One]]

Различия в поверхностном и глубоком копировании

Теперь мы знаем, как можно поверхностно и глубоко копировать связанный список. Когда мы поверхностно и глубоко копировали связанный список в приведенных выше примерах, в их результатах не было замечено никаких различий.

Можем ли мы заключить, что мелкое копирование и глубокое копирование — это одно и то же?
Абсолютно НЕТ, в них есть отличия. Рассмотрим различия между ними на примерах.

Рассмотрим пример ниже. Здесь мы будем выполнять некоторые операции, которые докажут нам, что поверхностное копирование и глубокое копирование — НЕ одно и то же.

Пример:

Python3

# importing copy and deepcopy function from 
# copy module
from copy import copy, deepcopy
 
 
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
 
 
class LinkedList:
    def __init__(self, *args):
        self.head = None
        for arg in args:
            node = Node(data = arg, next = self.head)
            self.head = node
 
    def __str__(self):
        llist = '['
        itr = self.head
        if itr == None:
            llist += ']'
        else:
            while itr != None:
                llist += f'[{itr.data}]'
                if itr.next != None:
                    llist += ' -> '
                itr = itr.next
            llist += ']'
        return llist
 
    def add_node(self, data):
        new_node = Node(data, next = self.head)
        self.head = new_node
 
    def change(self, index, with_element):
        itr = self.head
        if itr == None:
            return '[]'
        else:
            i =
            while i <= index:
                if i == index:
                    itr.data = with_element
                    break
                else:
                    i += 1
                    itr = itr.next
 
 
# creating the Linked List
linked_list = LinkedList('One', 'Two', 'Three')
 
# shallow copying and deep copying the Linked List
shallow_copied_linked_list = copy(linked_list)
deep_copied_linked_list = deepcopy(linked_list)
 
# adding a node to the original Linked List
linked_list.add_node('New_Node')
 
# changing the element at index 3 in the original Linked List to '1'
linked_list.change(3, '1')
 
# Printing the Linked Lists
print('Original Linked List: ', linked_list)
print('Shallow Copied Linked List: ', shallow_copied_linked_list)
print('Deep Copied Linked List: ', deep_copied_linked_list)

Вывод

Original Linked List:  [[New_Node] -> [Three] -> [Two] -> [1]]
Shallow Copied Linked List:  [[Three] -> [Two] -> [1]]
Deep Copied Linked List:  [[Three] -> [Two] -> [One]]

Здесь мы ясно видим разницу между связанным списком с поверхностным копированием и связанным списком с глубоким копированием.

Читайте также:  Как использовать Python Csv Dictreader?

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

Причина разницы

Как указано в приведенном выше определении мелкой копии, вложенные объекты в объекте просто ссылаются как на исходную, так и на неглубокую копию, а не полностью копируются в другую область памяти. Это означает, что исходный связанный список и связанный список с неглубоким копированием имеют одну и ту же ссылку на вложенный объект. Вложенным объектом здесь является каждый узел в связанном списке, поскольку мы вложили объект узла в наш объект связанного списка. Вот почему, когда мы изменили конкретный узел в нашем связанном списке, так как это вложенный объект, а неглубоко скопированный и исходный связанный список имеют одну и ту же ссылку на этот объект, изменение отразилось в неглубоко скопированном связанном списке.

В связанном списке с глубоким копированием не было замечено никакой разницы, поскольку глубокое копирование объекта копирует весь объект (в том числе вложенные объекты) в совершенно другое место в памяти.

Итак, теперь вы можете подумать, в чем разница между поверхностным копированием и ссылкой на объект ? Давай разницу ниже.

Ссылка на объект

Действие одной переменной, указывающей на место в памяти объекта, хранящегося в другой переменной, называется «ссылкой».

Поскольку эти переменные указывают на одно и то же место в памяти, изменения, сделанные одной из переменных в объекте, видны и в другой переменной. Это просто означает, что объект не копируется, а ссылается на него.

При неглубоком копировании объекты копируются в другие области памяти, но в случае вложенных объектов копируются только дескрипторы, а элементы в нем только ссылаются. При ссылке ничего не копируется, а только упоминается.

Давайте рассмотрим пример, чтобы отличить поверхностное копирование от ссылки

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

Ниже приведена реализация вышеупомянутой идеи:

Python3

# importing copy function from copy module
from copy import copy, deepcopy
 
 
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
 
 
class LinkedList:
    def __init__(self, *args):
        self.head = None
        for arg in args:
            node = Node(data = arg, next = self.head)
            self.head = node
 
    def __str__(self):
        llist = '['
        if self.head == None:
            llist += ']'
        else:
            itr = self.head
            while itr != None:
                llist += '[' + str(itr.data) + ']'
                if itr.next != None:
                    llist += ' -> '
                itr = itr.next
            llist += ']'
        return llist
 
    def add_node(self, data):
        new_node = Node(data, next = self.head)
        self.head = new_node
 
    def change(self, index, with_element):
        itr = self.head
        if itr == None:
            return '[]'
        else:
            i =
            while i <= index:
                if i == index:
                    itr.data = with_element
                    break
                else:
                    i += 1
                    itr = itr.next
 
 
# Driver code
llist = LinkedList(1, 2, 3, 'Four')
 
shallowCopiedLinkedList = copy(llist)
referencedLinkedList = llist
 
llist.add_node('New_Node')
 
print('Original: ', llist)
print('Shallow Copied: ', shallowCopiedLinkedList)
print('Referenced : ', referencedLinkedList)

Вывод

Original:  [[New_Node] -> [Four] -> [3] -> [2] -> [1]]
Shallow Copied:  [[Four] -> [3] -> [2] -> [1]]
Referenced :  [[New_Node] -> [Four] -> [3] -> [2] -> [1]]

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

Adblock
detector