오늘은 배열과 ArrayList에 대해서 간단하게 정리해 보려고 한다.
Java의 Collection도 다뤄야 하는데 머리에서 뒤엉킬까봐 너무 걱정이다.
먼저 배열!
배열이란?
정적(static) 자료구조 이며 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
인덱스를 통해 원소에 접근이 가능하다.
사용법
선언 및 index를 통한 접근은 제외.
for(int i = 0; i < (sizeof(score) / sizeof(*score); i++)
{
cout << arr[i];
}arr이라는 배열의 크기만큼 돌면서 모든 원소들을 출력해주는 코드이다.
아쉽게도 배열은 .length()가 안 돼서 서칭하던 중
(sizeof(score) / sizeof(*score)) 이 방법을 찾았다.
장단점
장점
- 크기가 고정이고, 인덱스를 가지고 있어 원하는 곳에 접근할 수 있다.
- 검색이 쉽고, 속도가 빠르다.
단점
- 배열의 특성상 삽입/삭제는 매우 불편하다.
- 배열 중간에 값을 넣는다면, 그 뒤에 있는 모든 값들을 이동시켜야되고, 배열이 꽉 차있을 경우, 메모리를 재할당하거나, 최악의 경우는 삽입이 불가능하다.
- 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.
시간복잡도
O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n) 이다.
ArrayList란?
동적(dynamic) 자료구조이며 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.
사용법
#include<list> //헤더 추가- 초기화
list<자료형>[list이름]([크기]) //[]제외list<int>list_int([갯수], [값]); //[]제외만약 listlist_int([2], [5]); 라면 5, 5 가 저장이 된다.
.assign(2, 5)위에 선언과 동시에 초기화도 할 수 있지만 assign() 함수를 사용해도 된다.
- 삽입/삭제
list.push_back(); // 맨 뒤에 값을 넣는다.
list.push_front(); // 맨 앞에 값을 넣는다.
list.pop_back(); // 맨 뒤 값을 삭제한다.
list.pop_front(); // 맨 앞에 값을 삭제한다.- 정렬
list.sort();- 중복 제거
list.unique(); //정렬이 필수여야한다.장단점
장점
- 가장 간단한 자료구조이다.
- 접근속도가 빠르다.
- 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
단점
- 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거롭다.
- 데이터 추가와 삭제가 느리다.
추가 및 삭제
Array List는 내부적으로 데이터를 배열에 저장한다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면, 이후의 데이터들이 한칸씩 뒤로 물러나야한다.
삭제도 추가와 유사하게 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한칸씩 땡겨야 한다.
시간복잡도
O(n) 의 최악 실행 시간을 갖는다.
자바 collection 문법들도 최대한 빨리, 그리고 많이 숙지해야겠다.
끝!
Slow and Steady