C++ 에서의 자료구조 Array vs Linked List; 배열과 연결리스트

 

기본 중에 기본부터 알아보자

응용프로그램을 설계할 때 가장 중요하게 고려해야 할 점 중 하나인 데이터 관리는 매우 중요하다.

 

 

즉, 우리는 응용 프로그램에 적합한 자료 구조를 사용하는 것이 정말 중요하다.

해결하고자 하는 문제에 적합한 자료구조를 이용하는 것이 응용프로그램 개발에 도움이 된다.

기본 내장 자료구조가 한계가 있다면 우리는 사용자 정의 자료 구조를 구현해야 한다.

 

-> 결국 자료구조를 배우면서 어떤 문제를 해결하는 데에 어떤 자료구조가 필요할 것인가?

임을 배우는 것이 자료구조를 배우는 목적이라고 하겠다.

 

---

 

C++에는 자료구조 중 대표적으로 선형 자료구조(Linear Data Structure)가 있다.

선형 자료구조는 또 다시 2가지로 나뉘는데

 

 

연속된 구조와 연결된 구조로 나눌 수 있다. (Contiguous & Linked)

-> 위의 구조는 데이터를 저장하는 방법에 따라 나눈 것이다.

 

-연속된 구조

 

연속된 자료 구조는 모든 원소를 단일 메모리 덩어리(chunk)에 저장하는 것을 말한다.

**물론 크기가 너무 크면 못할 수 있음

 

큰 사각형(chunk)에 작은 사각형들이 모여있다. 

단일 메모리 덩어리에 원소가 저장된 메모리 공간들이 있다.

 

**자료형을 명확하게 선언해야 하는 이유 -> sizeof(type)에 의해 메모리 공간이 분할된다.

-> 즉, 타입에 따라 다르겠지?

 

또한 연속적으로 되어 있어서

**BA를 Base Address라고 시작주소라고 한다.

i번째의 원소에 접근하고 싶다면 BA + i*sizeof(type)을 하면 접근 할 수 있다.

 

중요한 것은 i번째에 접근하는데 바로 접근이 가능하다는 이야기다.

O(1)의 시간복잡도를 가진다.

 

우리가 흔히 배열, Array라고 하는 것이 바로 위의 그림과 같다.

 

배열에도 종류가 있다.

동적, Dynamic 과 정적, Static이 있다.

 

정적 배열은 선언된 메모리가 끝나면 소멸되고 (stack 메모리에 할당, 함수 벗어나면 자동해제)

동적 배열은 메모리 공간 할당 시점과 해제 시점이 자유롭다.(Heap 메모리에 할당, 사용자가 해제해야함)

 

C++에서 동적 배열은 아래와 같이 선언한다.

int* arr = new int[size];

 

 

**또한 배열에서 각 원소는 인접해있다. 실제로 주소가 바로 옆이다.

하나의 원소 접근 시 주변의 원소도 같이 캐시로 가져온다.

다시 말하자면 배열은 캐시의 지역성을 이용하여 주변 원소 접근에 무척 빠르게 동작이 가능하다는 점이다.

 

우리가 순차적으로 for문을 돌려 배열의 다음 요소에 접근하는 것은 무척 빠른 방법이라고 말할 수 있다.

 

 

---

 

 

-연결된 구조

 

노드라는 것을 이용하여 메모리가 멀리 떨어져있어도 연결시켜 이용하는 것이다.

배열과는 다르게 여러 개의 메모리 블럭에 노드가 존재할 수 있다.

 

 

즉, 노드마다 있는 위치가 하나도 안비슷할 수 있다는 말이다.

 

위와 같은 자료구조를 Linked List, 연결리스트라고 부른다.

노드에는 data와 다음 노드를 가리키는 포인터가 들어있으며 마지막 노드에는 NULL을 가리킨다.

 

즉, 특정원소에 접근하려면 

극단적으로 N번째 요소에 접근하려면 루트 노드부터 N번의 연산을 거쳐야

N번 요소에 접근이 가능하다는 이야기다.

즉, 데이터 접근, Read에 O(N)의 시간 복잡도를 가진다.

 

또한 데이터와 다음 연결리스트를 가리키는 포인터를 저장하여 배열보다 메모리적으로 손해를 보긴 한다.

하지만!!

 

이렇게 안 좋은데.. 왜 쓰느냐?

원소의 삽입과 삭제가 매우 빠르다. (하지만 해당 위치까지.. 가기가 O(n) 시간이 걸린다.)

중간에 포인터만 바꾸어 주면 되므로  무척 빠르다.

N개의 자료가 있더라도 해당 자료에만 접근하면 삽입과 삭제는 O(1)이라고 할 수 있다.

 

EX)

a -> b -> d -> e로 연결되어있어서 c를 중간에 추가하고 싶다면

1. b가 가리키던 포인터를 c가 가리키도록 하고

2. b가 가리키는 포인터는 c를 가리키면 된다.

 

그림으로 다시 보자면

 

 

이러한 삽입 삭제의 이점은

메모리가 연속적으로 저장되지 않기 때문에 얻는 것이고

단점은 메모리가 연속적으로 저장되지 않기 때문에 캐시의 지역성을 기대할 수는 없다.

 

다시 말해서 현재 노드가 가리키는 다음 노드에 직접 방문하지 않고

캐시에 저장된 것을 불러올 수는 없다는 것이다.

 

 

우리는 N개의 모든 요소들을 순차적으로 읽는 과정에서

배열, 연결리스트 둘다 O(N)이라고 배우지만

실제론 캐시때문에 배열이 조금더 빠르게 모든 원소를 순회할 수 있다.

 

---

 

 

Contiguous		Linked
데이터가 메모리에 연속적으로 저장		노드에 데이터가 저장되고 노드는 다수의 메모리 블럭에 존재
임의의 원소에 바로 접근 가능		임의의 원소에 접근하는 것은 선형 시간복잡도를 가짐
캐시의 지역성 이용 가능		캐시의 지역성 이용 불가
데이터 크기만큼의 메모리 사용		데이터 + 다음 노드를 가리키는 포인터 만큼의 메모리 사용

 

 

다시 배열과 연결리스트에 대해서

CRUD를 보자면

	배열, Array	연결리스트, Linked List
임의 접근	O(1)	O(n)
맨 뒤에 원소 삽입	O(1)	O(1)
임의의 지점에 원소 삽입	O(n)	O(1)

 

Array는 중간에 삽입하면 연속성을 지키기 위해 나머지를 밀어야 하기 때문이다.

맨 뒤의 원소 삽입에 있어서는 예외가 왜 발생하는지 생각해보면 좋다.

 

배열은 맨뒤의 주소에 접근해서 삽입하는데. O(1)이 걸리고

연결리스트는 맨 뒤의 포인터에 접근해서 삽인하는데 O(N) + O(1) = O(N)이 되겠다.

 

---

 

 

배열의 크기보다 큰 원소를 참조하려고 시도하면 Segmentation fault Error가 난다.

에러를 아두는 것도 좋다.

 

또한 C++에서 그냥 배열로 사용하는 것은 Deep copy가 되지를 않아 std::array를 사용하곤 한다.

 

 

또한 연결리스트를 고리형(환형) 또는 단방향이 아닌 양방향, 이중 연결리스트로 구현하기도 한다.