배열

• 삽입 / 삭제 : O(N)
• 탐색 : O(1)
• C++에서는 size 변경 불가
• python은 리스트를 사용

임의 접근 O(1)

O(N)

배열에서 삽입이나 삭제를 한번 할 때 마다 시간 복잡도가 bigO(N)으로 느리다.
탐색을 하는 경우는 배열을 쓰는것이 유리한데 삽이이나 삭제를 하는 경우 다른 자료구조를 생각해봐야 한다.

벡터

• 삽입 / 삭제 : O(N)
• 탐색 : O(1)
• 동적 배열 (size 변경 가능)

벡터는 배열과 비슷한데 장점은 size를 동적으로 늘릴수 있다는점

연결 리스트(Linked List)

• 삽입/삭제 : O(1)
• 탐색 : O(N)
• PS에서는 별로 안쓰이지만 다른 자료구조들을 구현할 때 많이 쓰인다.

배열이랑 반대되는 특성을 가지고 있다. 연결 리스트는 삽입/삭제가 bigO(1) 로 빠르고 탐색이 bigO(N) 으로 느리다.

배열은 메모리가 연속적으로 연결되어 있는데 Linked List 는 메모리가 노드로 랜덤으로 되어있다. 다음 노드가 어디에 있는지는 이전 노드만 알 수 있다.

ex) 노드2를 찾기 위해서 노드 0에서 한번에 점프해서 찾을수 없고 0 - 1, 1 - 2 로 접근해서 찾아야 한다. 그래서 탐색속도가 bigO(N)으로 느리다.

삽입

삭제