[알고리즘] Array와 LinkedList 분석해보기

 

 

자료구조 중에서 자주 쓰이는 Array와 LInkedList를 서로 비교하겠다.

언어는 Python 기준으로 하겠다.

(선언할 때 배열 크기를 정해야 하는 c++, 자바의 정적 배열과는 달리 Python의 배열은 동적 배열이다.) 

 

다음 간단한 배열의 예를 들어보자

 

 

 

배열은 index와 데이터로 이루어져있다.

index는 0으로부터 시작되어 데이터의 순서를 매기며

데이터는 int형부터 시작되어 그 어떤 데이터 타입도 들어갈 수 있다.

 

여기서 배열의 어떤 하나의 데이터에 접근하는데 걸리는 시간은 얼마나 소요될까?

정확히 말하자면 시간복잡도 O는 얼마일까?

 

답은 O(1)이다.

 

내가 접근하고 싶은 데이터가 배열의 맨 앞에 있는 뒤에 있든 중간에 있는

ary[0], ary[2], ary[4] 이런 식으로 단 한 번에 접근하기 때문이다.

배열 크기의 상관없이 배열 요소 접근 시간 복잡도는 O(1)이다.

 

그렇다면 삽입/삭제는 어떨까??

 

배열의 3번째 칸에 10이라는 데이터를 삽입한다고 가정해보자

 

 

3번째 칸에 10이라는 데이터를 추가하려면

이미 3번째 칸에 있는 3은 어떻게 해야 할까?

당연히 한 칸 뒤로 보내야 한다.

그렇다면 그 뒤에 있었던 데이터는 한 칸 더 뒤로 보내야 한다. 

 

 

 

이런 식으로 말이다.

 

삭제의 경우는 어떨까?

 

 

 

 삭제의 경우도 마찬가지이다.

지워야 할 인덱스 뒤에 있는 데이터들은 한 칸씩 앞으로 당겨와야 한다.

 

그나마 배열의 맨 뒤에 요소를 추가하거나 삭제하는 것은 마지막 인덱스만 지우면 되니까 O(1)의 시간이 걸리지만

배열의 맨 앞에 요소를 추가하거나 삭제하는 것은 배열의 크기의 인덱스만큼을 앞으로 밀거나 당겨와야 하니

O(N)의 시간이 걸린다.

 

하지만 최악의 경우를 생각해야 하니 배열의 삽입/삭제의 시간복잡도는
O(N)이다

 

 

그다음은 LinkedList를 보겠다.

 

 

LinkedList는 다음과 같으며 코드는 이와 같다

 

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)


linked_list = LinkedList(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)

 

Linkedlist는 데이터와 노드로 이루어져 있다.

노드가 다음 번째 데이터를 가리키고 있어 인덱스와 똑같이

데이터의 순서가 있다.

하지만 차이점은 접근 방식에 있는데

 

Linkedlist의 요소 접근 시간복잡도는 O(N)이다.

그 이유는 기차를 생각하면 된다.

 

기차에 첫 번째 칸에서 마지막 칸으로 이동하는 방법은

첫 번째 칸에서 두 번째 칸으로 가고 그렇게 마지막 칸까지 가는 법이다.

 

배열처럼 데이터들의 위치가 인덱스로 정해져 있는 것이 아닌

데이터들이 노드로 이루어져 있기 때문에

맨 앞에 있는 데이터를 찾으려면 O(1)이 걸리지만

맨 뒤에 있는 데이터를 찾으려면 O(N)이 걸린다.

 

결과적으로 접근 시간복잡도는 O(N)이 걸린다.

 

삽입/삭제는 어떨까?

 

 

그림이 좀 삐뚤어진건 죄송스럽게 생각한다... 작성자의 애교로 생각해주길 바란다

 

삽입/삭제는 해당 요소의 노드를 추가시켜 앞의 노드만 다르게 해 주면 된다.

즉 맨 앞에 추가하든 뒤에 추가하든 O(1)의 시간이 걸린다.

삭제 과정도 이와 유사하다.

 

 

 

삭제도 삭제할 요소 바로 앞의 노드만 고치면 된다.

LinkedList의 삽입/삭제의 시간복잡도는 O(1)이다.

 

 이 둘의 자료구조를 정리하자면 다음과 같다.

 

	Array	LinkedList
특정 요소 접근	O(1)	O(N)
요소 삽입/삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버리면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
요약	데이터에 접근하는 경우가 많다면 Array를 사용	삽입과 삭제가 빈번하다면 LinkedList를 사용