자료구조 (배열, 벡터, 연결리스트, 스택, 큐)

* 배열 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를 고려하여 만들어졌기에 실제 속도가 느린 편.

 

 

[ 출처 : 컴공선배 알고리즘 강의 ]

 

 

[ 출처 : 컴공선배 알고리즘 강의 ]