[자료구조] 배열 vs 연결 리스트

배열 (Array)

배열에서의 접근 방법

---

---

C언어의 배열(array) 은 각각의 요소들이 연속된 메모리 상에 존재한다는 아주 중요한 특성을 가지고 있습니다.

즉, 다음 메모리 주소에 다음 요소가 붙어있으므로, 다음과 같은 방식을 사용할 수 있습니다.

int a[5] = {1, 2, 3, 4, 5}; // *a == 1

for (int i = 0; i < 5; i++) {
    printf("%d ", *(a+i));
}
/* 출력 결과
1 2 3 4 5
*/

이는 최악의 경우에도 $\Theta(1)$의 시간을 보장합니다.

배열에서의 탐색 방법

---

브루트 포스 방식

배열에서 요소를 찾는 가장 기본적인 방법은 요소 하나하나를 체크하는 반복문을 사용하는 것입니다.

for (int i = 0; i < 5; i++) {
    if ((*a+i) == 3) {
        return i;
    }
}

이는 최악의 경우 배열 전체를 탐색해야 하므로, 전체 요소의 개수를 $N$이라고 하면, $O(N)$의 시간 복잡도를 가집니다.

이진 탐색 방식

이 방법은 배열이 정렬되었을 경우에 가능합니다. 이진 탐색 알고리즘을 사용하므로, 시간 복잡도가 $O(\log N)$ 입니다.

배열에서의 삽입, 삭제 방법

---

배열은 각 요소가 서로 메모리 상에서 붙어있는 특성을 가집니다. 이는 요소를 삽입 또는 삭제할 때에도 지켜져야 합니다.

요소 삽입

위 그림처럼 삽입 위치 뒤의 모든 요소들을 한 칸씩 뒤로 이동시키는 작업이 시행되어야 합니다.

요소를 가장 앞에 삽입하는 경우, 기존의 모든 요소들을 뒤로 옮기는 연산이 시행됩니다. 즉, 이때의 시간 복잡도는 $\Theta(N)$ 입니다.

요소를 가장 뒤에 삽입하는 경우, 뒤에는 어떤 요소도 없으므로 연산이 필요하지 않습니다. 이때의 시간 복잡도는 $\Theta(1)$ 입니다.

단, 배열의 크기가 충분히 커서 삽입에 문제가 없다는 가정이 필요합니다.

요소 삭제

---

삭제도 삽입과 비슷한 방식으로, 삭제된 위치 뒤의 모든 요소들을 앞으로 한 칸씩 당겨주는 연산이 필요합니다.

가장 앞의 요소를 삭제하는 경우, 뒤의 모든 요소들을 끌어와야 하기 때문에 $\Theta(N)$ 의 시간 복잡도로 나타낼 수 있습니다.

가장 뒤의 요소를 삭제하는 경우, 어떤 요소도 움직일 필요가 없으므로 이 때의 시간 복잡도는 $\Theta(1)$ 입니다.

---

따라서, 배열 구조에서 요소에 접근할 때는 $O(1)$, 요소를 탐색할 때는 $O(N)$, 삽입과 삭제 역시 $O(N)$ 의 시간 복잡도를 가집니다.

연결 리스트 (Linked List)

---

연결 리스트의 구조는 위와 같습니다.

단순 연결 리스트 (Singly linked list) 로, 각 요소를 노드(node) 라고 부르며, 각 노드 는 data 와 next 로 구성되어 있습니다.

• data : 값을 저장하는 변수입니다.

• next : 다음 노드의 메모리 주소를 저장하는 포인터 변수입니다.

• 가장 앞의 노드를 head 라고 하며, 이 노드에는 값을 저장하지 않습니다.
• 마지막 노드의 next 값은 null로 지정합니다.

구조체로 간단히 구현하면 아래와 같습니다.

typedef struct LinkedListElement LE;

struct LinkedListElement {
    int data;
    LE* next;
};

연결 리스트에서의 접근 방법

---

연결 리스트의 각 요소들은 각 노드의 next 포인터를 통해 연결됩니다.

즉, 메모리 상에서 서로 붙어있지 않을 수 있습니다. 특정 노드에 접근하려면, head 로부터 next 포인터를 통해 이동하는 과정이 필요합니다.

최악의 경우 모든 노드를 돌아야하므로 시간 복잡도는 $O(N)$ 입니다.

연결 리스트에서의 탐색 방법

---

연결 리스트에서 요소를 찾는 것은 배열에서 요소를 찾는 방식과 같습니다. head 로부터 타겟 노드를 찾을 때까지 이동합니다.

배열에서 가능했던 이진 탐색은, 연결 리스트에서 바로 mid 노드에 접근할 수 없으므로 불가능합니다.

찾고자 하는 값이 리스트 가장 끝에 존재할 경우 모든 노드를 돌아야 하므로 시간 복잡도는 $O(N)$ 입니다.

연결 리스트에서의 삽입, 삭제 방법

---

배열과 비교해서 연결 리스트에서의 삽입/삭제는 더 효율적이라고 할 수 있습니다.
모든 요소가 메모리 상에서 붙어있어야 하는 배열과 달리, 연결 리스트의 요소들은 그에 자유롭기 때문입니다.

요소 삽입

---

위 그림처럼, 삽입하는 위치 주변의 노드만 수정해주면 되기 때문에 배열보다 훨씬 빠르게 삽입이 가능합니다.

하지만, 삽입 위치를 탐색하는 과정이 필요하기 때문에, 삽입 위치를 따로 저장해 놓지 않는 이상 $O(N)$ 의 시간 복잡도를 갖습니다. 삽입 연산 자체의 시간 복잡도는 $O(1)$ 입니다.

• 위 그림에서 파란색으로 표시된 화살표는 삽입 노드의 next 를 기존 노드의 next 로 연결하는 과정입니다.

• 빨간색 화살표는 기존 노드에 새로운 노드를 연결하는 과정입니다.

이때, 파란색 화살표로 표시된 과정을 먼저 수행해야 합니다. 그렇지 않은 경우, 기존 노드에 기억된 다음 노드의 주소를 잃어버리는 경우가 발생합니다.

요소 삭제

---

삽입과 마찬가지로 삭제 역시 연산 과정이 간단합니다. 삭제할 노드의 next 를 앞 노드의 next 로 바꾸어 주면 끝납니다.

그러나 삭제 위치까지의 탐색이 필요할 수도 있으므로 주소를 따로 저장해 놓지 않는다면 $O(N)$ 의 시간 복잡도를 갖습니다. 삭제 연산 과정은 $O(1)$ 입니다.

Array vs. Linked List

---

배열과 연결리스트의 Query, Manipulation에 관한 시간 복잡도를 표로 정리하면 다음과 같습니다.

	접근	탐색	탐색 (정렬됨)	삽입	삭제
배열	$\Theta(1)$	$O(N)$	$O(\log N)$	$O(N)$	$O(N)$
연결 리스트	$O(N)$	$O(N)$	$O(N)$	$\Theta(1)$	$\Theta(1)$

배열은 접근, 탐색 (정렬된 경우에 한함) 에서 강점을 보이고, 연결 리스트는 삽입, 삭제에 강점을 보입니다.

또한 배열은 메모리를 정적 할당하여 제한된 메모리 크기를 가지지만, 연결 리스트는 동적 할당을 사용하여 메모리 사용에 있어 더 효율적이라고 할 수 있습니다.

그러나 연결 리스트는 다음 노드의 주소를 저장하는 공간이 필요합니다.

데이터의 종류, 구성, 수량 등에 따라 적절한 자료 구조를 사용함으로써 공간/시간 복잡도를 줄일 수 있습니다.