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

배열

가장 기본적인 자료구조이다

삽입 / 삭제의 시간복잡도 : O(N)

탐색 시간복잡도 : O(1)

C++에서는 size 변경이 불가하며, python은 리스트를 사용하여 구현한다

// C++
int arr[4] = {10, 11, 12, 13};
arr[2] = 5;

# python
arr = [10, 11, 12, 13]
arr[2] = 5

배열을 생성할 땐, 메모리에 연속된 공간이 생긴다.

탐색시, 임의접근(random access)하기 때문에 탐색속도가 빠르다  O(1)

삽입시 해당하는 위치 뒤에 있는 친구들을 하나씩 다 밀어줘야 하고

삭제시 해당하는 위치 뒤에 있는 친구들을 하나씩 다 땡겨줘야 하기 때문에 시간복잡도는 O(N)이 된다

삽입/삭제를 많이 하는 경우에는 배열이 불리하고, 탐색을 많이 하는 경우에는 배열이 유리하다

 

연결 리스트

역시 가장 기본적인 자료구조이다

파이썬에서는 연결리스트라는 기본 자료구조가 없고, 구현해서 사용해야한다

삽입 / 삭제의 시간복잡도 : O(1)

탐색 시간복잡도 : O(N)

Problem Solving 보다는 다른 자료구조를 구현할 때 많이 쓰인다

// C++
list<int> l;
l.emplace_back(0);
l.emplace_back(1);
l.emplace_back(2);
l.emplace_front(3);
printf("size: %d\n", l.size());
for (auto i : l)
	printf("%d\n", i);

배열과 달리 임의접근이 불가능하며,

모든 노드가 링크로 연결되어 있기 때문에 하나의 노드를 찾기 위해서 걸리는 탐색속도는 O(N)이 걸린다

삽입/삭제시 해당하는 노드의 헤드와 포인터를 붙이거나/떼거나 하면 되기 때문에 시간복잡도는 O(1)이 된다

삽입/삭제를 많이 하는 경우에는 연결리스트가 유리하고, 탐색을 많이 하는 경우에는 배열이 불리하다

 

삽입/삭제를 많이 하는 경우에는 연결리스트, 탐색을 많이 하는 경우에는 배열을 이용하자