[자료구조] 배열(Array)과 연결 리스트(Linked List)

들어가며

배열과 연결 리스트는 기본적인 자료 구조중 가장 기본적이고 중요한 것이다. 둘다 데이터의 집합을 저장하는데 사용되지만 그들의 내부 구조와 동작 방식은 매우 다르다. 이번 글에서는 두 자료 구조의 차이점과 장단점 그리고 어떤 상황에서 어떤 것을 선택하는것이 좋은지에 대해서 알아보려고 한다.

배열(Array)

정의: 배열은 메모리 상의 연속적인 위치에 저장된 요소의 집합이다.

장점

• 인덱싱: 각 요소는 인덱스를 통해 직접 접근이 가능하여 O(1)의 시간 복잡도로 데이터에 접근할 수 있다.
• 메모리 사용: 메모리가 연속적으로 할당되기 때문에 캐시 효율성이 좋다.

단점

• 크기 변경: 배열의 크기는 생성 시 정해지므로, 크기를 변경하기 위해서는 새로운 배열을 생성하고 데이터를 복사해야 한다.
• 삽입/삭제: 중간에 데이터를 삽입하거나 삭제할 때, 다른 모든 요소의 위치를 변경해야 한다. 따라서 O(n)의 시간 복잡도가 소요된다.

연결 리스트(Linked List)

정의: 연결 리스트는 노드들의 집합으로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.

장점

• 동적 크기: 연결 리스트의 크기는 동적으로 변경될 수 있다. 즉, 필요에 따라 노드를 추가하거나 삭제할 수 있다.
• 삽입/삭제: 연결 리스트에서는 특정 노드의 앞이나 뒤에 노드를 쉽게 삽입하거나 삭제할 수 있다. 이러한 작업의 시간 복잡도는 O(1)이다.

단점

• 인덱싱: 연결 리스트는 인덱스를 사용해 직접 접근할 수 없다. 따라서 특정 위치의 데이터에 접근하려면 처음부터 순차적으로 노드를 탐색해야 한다. 이로 인해 O(n)의 시간 복잡도가 소요된다.
• 메모리 사용: 각 노드에 데이터뿐만 아니라 포인터도 저장되어 있기 때문에 배열에 비해 메모리 사용이 많다.

배열과 연결 리스트의 차이점

항목	배열	연결 리스트
메모리 구조	연속적	비연속적
인덱싱	O(1)	O(n)
삽입/삭제	첫/마지막: O(1), 중간: O(n)	첫: O(1), 중간/마지막: O(n)
메모리 사용	데이터만 저장	데이터 + 포인터 저장
크기 변경	고정 (크기 변경 필요 시 재생성)	동적

시간복잡도에 대한 구체적인 설명

1. 인덱싱:
   • 배열: 배열의 각 요소에는 인덱스가 있어, 해당 인덱스를 사용하여 O(1)의 시간복잡도로 직접 접근할 수 있다.
   • 연결 리스트: 특정 요소를 찾기 위해서는 첫 노드부터 순차적으로 탐색해야 하므로 O(n)의 시간복잡도를 가진다.
2. 삽입/삭제:
   • 배열: 첫번째나 마지막 위치에 삽입/삭제하는 경우 O(1)의 시간복잡도를 가지지만, 중간에 삽입/삭제하는 경우 모든 요소의 위치를 업데이트해야 하므로 O(n)의 시간복잡도를 가진다.
   • 연결 리스트: 첫 노드에 삽입/삭제하는 경우 O(1)의 시간복잡도를 가지지만, 중간이나 마지막 노드에서 삽입/삭제하는 경우 O(n)의 시간복잡도를 가진다.

파이썬 코드 활용 사례

배열 활용:

# 배열을 활용한 예시 (파이썬 리스트 사용)
arr = [1, 2, 3, 4, 5]

# 인덱싱
print(arr[2])  # 3

# 중간 삽입
arr.insert(2, 6)
print(arr)  # [1, 2, 6, 3, 4, 5]

# 중간 삭제
arr.pop(2)
print(arr)  # [1, 2, 3, 4, 5]

연결 리스트 활용:

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

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

    # 삽입
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    # 삭제
    def delete_node(self, key):
        curr_node = self.head
        if curr_node and curr_node.data == key:
            self.head = curr_node.next
            curr_node = None
            return
        prev = None
        while curr_node and curr_node.data != key:
            prev = curr_node
            curr_node = curr_node.next
        if curr_node is None:
            return
        prev.next = curr_node.next
        curr_node = None

    # 출력
    def print_list(self):
        curr_node = self.head
        while curr_node:
            print(curr_node.data, end=" -> ")
            curr_node = curr_node.next

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

llist.print_list()  # 1 -> 2 -> 3 -> 4 -> 5 -> 

llist.delete_node(3)
llist.print_list()  # 1 -> 2 -> 4 -> 5 -> 

결론

그렇다면 우리는 무엇을 선택 해야할까? 빠른 접근이 필요한 경우애는 배열을 사용하는게 좋다. 동적인 크기 변경과 빈번한 삽입/삭제 작업이 필요한 경우에는 연결 리스트를 사용하는게 좋다. 그러나 배열과 연결 리스트는 각자의 장단점이 있다. 따라서 프로젝트의 요구 사항과 기대하는 성능에 따라 적절한 자료 구조를 선택하는 것이 중요하다.

맨 위로 올라가기