코딩테스트/이론
자료구조 (배열, 벡터, 연결리스트, 스택, 큐)
확인해볼까
2022. 8. 11. 23:15
* 배열 Array
- 삽입 / 삭제 : O(N) ( 삭제, 삽입하려는 위치 이외의 원소들을 한 칸씩 다 이동시켜야 하기 때문)
- 탐색 : O(1) ( 임의접근 Random access, 이유 : 인덱스를 사용했다고 해서 해당 인덱스에 이르기까지의 요소들을 모두 거치는 것이 아니라 배열의 주소 + 인덱스*type의 크기 = 메모리 주소값이라는 것을 이용해서 바로 해당 인덱스의 원소에 접근하기 때문)
- Python은 리스트를 사용
- C++에서는 size 변경불가 (생성 시, size와 type 고정)
* 벡터 Vector ( 2개 이상의 값 저장 )
- 삽입 / 삭제 : O(N)
- 탐색 : O(1)
- 동적 배열 (size 변경 가능)
* 연결리스트 Linked List (배열과 반대의 특성)
- 삽입 / 삭제 : O(1)
- 탐색 : O(N) (임의접근을 제공하지 않기 때문, 각 노드들이 위치한 메모리 주소값들이 불규칙적으로 존재하기 때문)
- Python에서는 따로 제공을 하지 않기에 직접 만들어서 사용해야 함.
- PS에서는 별로 쓰이지는 않지만 다른 자료구조들을 구현할 때 많이 사용.
* 스택 Stack
- 삽입 / 삭제 : O(1)
- 데이터가 바닥부터 하나씩 쌓이는 구조
- FILO ( 선입후출, 첫 번째로 들어온 데이터가 마지막에 나가는 구조)
- LIFO ( 후입선출, 가장 마지막에 들어온 데이터가 가장 처음 나가는 구조 )
- Python은 리스트로 구현
* 큐
- 스택과 반대되는 특성
- 삽입 / 삭제 : O(1)
- FIFO ( 선입선출, 첫 번쨰로 들어온 데이터가 처음으로 나가는 구조 )
- LILO ( 후입후출, 마지막에 들어온 데이터가 마지막에 나가는 구조 )
Queue 자료형으로도 구현이 가능하지만 이 자료형은 멀티스레드 환경을 고려한 thread-safe를 고려하여 만들어졌기에 실제 속도가 느린 편.
