연결 리스트(Linked List)의 얕은 복사(shallow copy)와 깊은 복사(deep copy)에 대해 알아보자.

우선 연결 리스트를 정의한다.

# 노드 정의
class Node:
    def __init__(self, x, next_node=None):
        self.val = x
        self.next = next_node

# 연결리스트 클래스 정의
class LinkedList:

    # 초기화 메소드
    def __init__(self):
        dummy = Node("dummy")
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None

        self.num_of_data = 0

    # append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경)
    def append(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node

        self.num_of_data += 1

    # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0:  # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        return self.current

    # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next is None:
            return None

        self.before = self.current
        self.current = self.current.next

        return self.current.data

그리고 변수에 값을 할당하듯이 = 연산자를 이용하면 얕은 복사가 된다.

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.append(4)
a.append(5)

# 얕은 복사 (shallow copy)
b = a

a.first().val = 10
print(a.first().val, b.first().val)

# 결과: 10 10

다만 연결 리스트의 얕은 복사는 ab가 동일한 참조를 가리키게 되므로 a의 요소를 변경하면 b의 요소도 같이 변경된다. ( a의 요소와 b의 요소는 동일한 요소를 참조하고 있으므로)

쉽게 이해가 되지 않는다면 원본과 복사본의 메모리 주소 값의 비교를 통해 확인해보자.

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.append(4)
a.append(5)

b = a

print(f"a: {id(a)}, b: {id(b)}, a_head: {id(a.head)}, b_head: {id(b.head)}")

# 결과: a: 4453768448, b: 4453768448, a_head: 4453767488, b_head: 4453767488

이처럼 얕은 복사된 변수의 메모리 주소 값을 원래의 변수와 비교해보니 a와 b는 결국 동일한 메모리 주소를 참조하게 된다는것을 알 수 있다.

그렇다면 이번에는 깊은 복사를 해보자.

깊은 복사를 위해 연결리스트에 메소드 deep_copy()를 추가해 주자.

# 노드 클래스 정의
class Node:
    def __init__(self, data):
        self.val = data
        self.next = None

# 연결리스트 클래스 정의
class LinkedList:

    # 초기화 메소드
    def __init__(self):
        dummy = Node("dummy")
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None

        self.num_of_data = 0

    # append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경)
    def append(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node

        self.num_of_data += 1

    # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0:  # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        return self.current

    # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next is None:
            return None

        self.before = self.current
        self.current = self.current.next

        return self.current.data

    # 깊은 복사를 위한 메소드 추가
    def deep_copy(self):
        copied = LinkedList()
        item = self.first()

        if item:
            copied.append(item.val)
            while True:
                item = item.next
                if item:
                    copied.append(item.val)
                else:
                    break

        return copied

그리고 얕은 복사를 했을때와 마찬가지로 a의 요소 값을 변경해보자.

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.append(4)
a.append(5)

# 깊은 복사 (deep copy)
c = a.deep_copy()

a.first().val = 10
print(a.first().val, c.first().val)

# 결과: 10 1

메모리 주소도 비교해보자.

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.append(4)
a.append(5)

c = a.deep_copy()

print(f"a: {id(a)}, c: {id(c)}, a_head: {id(a.head)}, c_head: {id(c.head)}")

# 결과: a: 4319350016, c: 4319790800, a_head: 4319349056, c_head: 4319791520

이처럼 깊은 복사는 기존 변수와 전혀 상관없는 새로운 연결 리스트가 생성됨을 확인할 수 있습니다.

파이썬 내장 copy 함수

필요한 경우 별도의 메소드를 만들어 deep copy를 할 수도 있지만 파이썬에서 제공해주는 copy 라이브러리를 활용하면 동일한 결과를 얻을 수 있습니다.

import copy

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.append(4)
a.append(5)

c = copy.deepcopy(a)

print(f"a: {id(a)}, c: {id(c)}, a_head: {id(a.head)}, c_head: {id(c.head)}")

# 결과: a: 4441013504, c: 4441672576, a_head: 4441012544, c_head: 4441672768

마치며

파이썬의 얕은 복사는 객체가 mutable 이냐 immutable 이냐에 따라 다른 결과가 나타날 수 있습니다.

지금 처럼 사용자가 정의한 클래스는 mutable 객체이므로 얕은 복사를 하게되면원본의 변경 사항이 복사본에도 반영 되게되므로 원본에 영향을 받지 않는 복사본을 만들기 위해 깊은 복사가 필요합니다.

그래서 별도의 깊은 복사 메소드를 정의해주거나 copy 라이브러리의 deepcopy 함수를 사용하면 원본에 영향을 받지 않는 복사본을 사용할 수 있습니다.

감사합니다.