삽입, 삭제 연산에 대한 시간 복잡도 비교

 

배열에서의 삽입과 삭제

배열은 연속된 메모리 위치에 고정 크기로 요소를 저장하는 자료 구조입니다. 중간 위치에서 요소를 삽입하거나 삭제할 때 모든 요소를 이동해야 하므로, 시간 복잡도는 $O(n)$ 입니다.

1. 배열에 요소 삽입 (Python)

아래 예시는 배열의 특정 위치에 요소를 삽입하는 코드입니다.

# 배열 초기화
arr = [1, 2, 3, 4, 5]

# 배열의 특정 위치에 요소 삽입 (2번 인덱스에 10 삽입)
position = 2
value = 10

# 2번 인덱스 이후 요소들을 오른쪽으로 이동
arr.insert(position, value)

print("삽입 후 배열:", arr)  # 출력: [1, 2, 10, 3, 4, 5]

삽입 시간 복잡도: $O(n)$ (중간 또는 첫 위치에 삽입 시)

2. 배열에서 요소 삭제 (Python)

아래는 배열의 특정 위치에서 요소를 삭제하는 예시입니다.

# 배열 초기화
arr = [1, 2, 10, 3, 4, 5]

# 배열의 특정 위치에서 요소 삭제 (2번 인덱스의 요소 삭제)
position = 2
arr.pop(position)

print("삭제 후 배열:", arr)  # 출력: [1, 2, 3, 4, 5]

삭제 시간 복잡도: $O(n)$ (중간 또는 첫 위치에서 삭제 시)

---

연결 리스트에서의 삽입과 삭제

연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 포함한 자료 구조로, 동적 메모리 할당을 사용하여 필요할 때마다 크기를 조정할 수 있습니다. 특정 위치에 삽입하거나 삭제할 때 탐색이 필요하므로 시간 복잡도는 $O(n)$ 이지만, 처음이나 끝에서의 삽입과 삭제는 $O(1)$에 가능합니다.

단일 연결 리스트(Node 클래스와 LinkedList 클래스)

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

class LinkedList:
    def __init__(self):
        self.head = None

    # 처음 위치에 노드 삽입
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    # 끝 위치에 노드 삽입
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
    
    # 특정 위치에 노드 삽입
    def insert_at_position(self, position, data):
        new_node = Node(data)
        current = self.head
        count = 0
        while current and count < position - 1:
            current = current.next
            count += 1
        new_node.next = current.next
        current.next = new_node

    # 처음 위치에서 노드 삭제
    def delete_at_beginning(self):
        if self.head:
            self.head = self.head.next
    
    # 끝 위치에서 노드 삭제
    def delete_at_end(self):
        if not self.head:
            return
        if not self.head.next:
            self.head = None
            return
        second_last = self.head
        while second_last.next.next:
            second_last = second_last.next
        second_last.next = None

    # 특정 위치에서 노드 삭제
    def delete_at_position(self, position):
        if not self.head:
            return
        current = self.head
        if position == 0:
            self.head = current.next
            return
        for i in range(position - 1):
            current = current.next
            if not current.next:
                return
        current.next = current.next.next
    
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

1. 연결 리스트에 삽입 연산

# 연결 리스트 초기화
ll = LinkedList()

# 처음에 삽입
ll.insert_at_beginning(3)
ll.insert_at_beginning(2)
ll.insert_at_beginning(1)

# 끝에 삽입
ll.insert_at_end(4)
ll.insert_at_end(5)

# 특정 위치에 삽입 (2번 위치에 10 삽입)
ll.insert_at_position(2, 10)

ll.print_list()  # 출력: 1 -> 2 -> 10 -> 3 -> 4 -> 5 -> None

처음에 삽입: $O(1)$

끝에 삽입: $O(n)$ (단일 연결 리스트)

특정 위치에 삽입: $O(n)$

2. 연결 리스트에서 삭제 연산

# 처음에서 삭제
ll.delete_at_beginning()

# 끝에서 삭제
ll.delete_at_end()

# 특정 위치에서 삭제 (2번 위치의 노드 삭제)
ll.delete_at_position(2)

ll.print_list()  # 출력: 2 -> 10 -> 4 -> None

처음에서 삭제: $O(1)$

끝에서 삭제: $O(n)$ (단일 연결 리스트)

특정 위치에서 삭제: $O(n)$

---

요약

배열과 연결 리스트는 삽입과 삭제 연산에서 시간 복잡도 차이가 있습니다. 배열은 특정 위치에 삽입하거나 삭제할 때 

$O(n)$ 의 시간이 걸리지만, 연결 리스트는 포인터를 조정하여 처음이나 끝에 삽입 및 삭제 시 $O(1)$ 의 시간 복잡도를 가집니다.