[자료 구조] 배열 , 벡터, 연결리스트 , 배열과 동적배열의 차이점

배열 Array

- 삽입 / 삭제 : O(N)

- 탐색 : O(1)

- C++ 에서는 size 변경 불가 

- Python은 리스트를 사용 

 

C++

int arr[4] = {1,2,3,4};
arr[2] = 2;

 

Python

arr = [1,2,3,4]
arr[2] = 2

 

 

벡터 Vector

- 삽입 / 삭제 : O(N)

- 탐색 : O(1)

- 동적 배열 ( 사이즈 변경 가능)

 

C++

vector<pair<int, int> >  v;
v.push_back(make_pair(123,456));
v.emlpace_back(789, 987);

printf(" vector size: %d\n", v.size());

for(auto p : v)
	printf("%d, %d\n" , p.first, p.second);

 

Python

v = []
v.append((123,456))
v.append((789,987))
print("size: ", len(v)))

for p in v:
	print(p)

 

 

 

배열과 동적 배열의 차이점

배열 :   

- 고정된 공간 할당

- 순차적 데이터 저장 

- 인덱스만 알고 있으면, 조회가 빠름

- 특정 조건을 충족하는 값을 찾는 탐색은 느림

 

동적 배열: 

- 데이터 접근 및 할당이 빠르다

- 배열의 크기가 변할 수 있음

- 메모리 공간이 남을 수 있음

 

연결리스트 

- 삽입 /  삭제 : O(1)

- 탐색: O(N)

- 특징 : 삽입, 삭제가 빠르고 탐색이 느리다.

- PS에서는 별로 안쓰지만 기타 자료구조들을 구현할때 쓰임 

 

 

C++

list<int> l;

l.emplace_back(0);
l.emplace_back(1);
l.emplace_back(2);
l.emplace_front(3);

print("size: %d\n", l.size());

for(auto i : l)
	printf("%d\n", i);