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

Связанные списки — это тип » абстрактных типов данных » в 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 = 0

            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 = 0

            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 = 0

            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 = 0

            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]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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 = 0

            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]]