🏷️배열의 특징1 - 배열과 인덱스
public class ArrayMain1 {
public static void main(String[] args) {
int[] arr = new int[5];
System.out.println("==index 입력: O(1)==");
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
System.out.println(Arrays.toString(arr));
System.out.println("==index 변경: O(1)==");
arr[2] = 10;
System.out.println(Arrays.toString(arr));
System.out.println("==index 조회: O(1)==");
System.out.println("arr[2] = " + arr[2]);
System.out.println("==배열 검색: O(N)==");
int value = 10;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
System.out.println(value + "찾음");
break;
}
}
}
}- ✔️배열의 성능
- 배열에서 자료를 찾을 때 인덱스를 사용하면 매우 빠르게 자료를 찾을 수 있다.
- 인덱스를 통한 입력, 변경, 조회의 경우 한 번의 계산으로 자료의 위치를 찾을 수 있다.
- 배열에 들어있는 데이터를 찾는 것을 검색이라고 한다.
- 배열에 들어있는 데이터를 검색할 때는 배열에 들어있는 데이터를 하나하나 비교해야 한다. 이 때는 이전과 같이 인덱스를 사용해서 한 번에 찾을 수 없다. 대신 배열 안에 들어있는 데이터를 하나하나 확인해야 한다. 따라서 평균적으로 볼 때 배열의 크기가 클수록 오랜 시간이 걸린다.
- 배열의 순차 검색은 배열에 들어있는 데이터의 크기만큼 연산이 필요하다. 배열의 크기가 N이면 연산도 N만큼 필요하다.
- ✔️배열 정리
- 배열의 인덱스 사용 : O(1)
- 배열의 순차 검색 : O(N)
🏷️빅오(O) 표기법
- ✔️빅오(Big O) 표기법
- 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식
- 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지를 나타낸다.
- 여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다.
- 빅오 표기법은 매우 큰 데이터를 입력한다고 가정하고 데이터 양 증가에 따른 성능 변화 추세를 비교하는데 사용된다. 정확한 성능 측정이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교하는 것이 목적이다. 따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 크게 의미가 없어진다. 이런 이유로 빅오 표기법에서는 상수를 제거한다.
- ✔️빅오(Big O) 표기법 예시
- O(1) : 상수 시간, 입력 데이터 크기에 관계없이 알고리즘 실행 시간이 일정하다.
- O(N) : 선형 시간, 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다.
- O(N^2) : 제곱 시간, 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다.
- O(log N) : 로그 시간, 알고리즘의 실행 시간이 입력 데이터의 크기의 로그에 비례하여 증가한다.
- O(N log N) : 선형 로그 시간
🏷️배열의 특징2 - 데이터 추가
- ✔️배열의 특정 위치에 데이터를 추가
- 배열의 첫 번째 위치에 추가
- 배열의 중간 위치에 추가
- 배열의 마지막 위치에 추가
-
✔️배열의 첫 번째 위치에 추가하는 경우
- 기존 데이터들이 모두 오른쪽으로 한 칸씩 밀려나면서 추가할 위치를 확보해야 한다.
- 배열의 마지막 부분부터 오른쪽으로 밀어야 데이터를 유지할 수 있다.
- 배열의 첫 번째 위치 찾기 : O(1)
- 모든 데이터를 배열의 크기만큼 한 칸씩 이동 : O(N)
- 따라서 O(N)
-
✔️배열의 중간 위치에 추가하는 경우
- 지정한 인덱스에 데이터를 추가할 수 있도록 위치를 확보해야 한다.
- 따라서 지정된 인덱스부터 시작해서 데이터들을 오른쪽으로 한 칸씩 밀어야 한다.
- 인덱스 왼쪽 데이터들은 이동하지 않아도 된다.
- 배열의 중간 위치 찾기 : O(1)
- 지정된 인덱스 이후의 데이터들을 한 칸씩 이동 : O(N/2)
- 따라서 O(N)
-
✔️배열의 마지막 위치에 추가하는 경우
- 기존 데이터를 이동할 필요가 없다.
- 배열의 마지막 위치 찾기 : O(1)
- 기존 배열 이동 불필요
- 따라서 O(1)
public class ArrayMain2 {
public static void main(String[] args) {
int[] arr = new int[5];
arr[0] = 1;
arr[1] = 2;
System.out.println(Arrays.toString(arr));
System.out.println("배열의 첫번째 위치에 3 추가 O(n)");
int newValue = 3;
addFirst(arr, newValue);
System.out.println(Arrays.toString(arr));
System.out.println("배열의 index(2) 위치에 4 추가 O(n)");
int index = 2;
int value = 4;
addAtIndex(arr, index, value);
System.out.println(Arrays.toString(arr));
System.out.println("배열의 마지막 위치에 5 추가 O(1)");
addLast(arr, 5);
System.out.println(Arrays.toString(arr));
}
private static void addFirst(int[] arr, int newValue) {
// 오른쪽에서부터 시작, 왼쪽의 데이터를 오른쪽으로 이동
// 데이터의 유실이 발생하지않음
for (int i = arr.length - 1; i > 0; i--) {
arr[i] = arr[i - 1];
}
arr[0] = newValue;
}
private static void addAtIndex(int[] arr, int index, int newValue) {
for (int i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = newValue;
}
private static void addLast(int[] arr, int newValue) {
arr[arr.length - 1] = newValue;
}
}- ✔️배열의 한계
- 배열은 가장 기본적인 자료구조, 특히 인덱스를 사용할 때 최고의 효율이 나온다.
- 배열의 크기를 생성하는 시점에 미리 정해야 한다.
- 배열처럼 처음부터 정적으로 길이가 정해져있는 것이 아니라, 동적으로 언제든지 길이를 늘리고 줄일 수 있는 자료구조가 있다.
🏷️직접 구현하는 배열 리스트
배열의 경우 다음 2가지 단점이 존재
- 배열의 길이를 동적으로 변경할 수 없다.
- 데이터를 추가하기 불편하다.
배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라 한다.
- ✔️List 자료구조
- 순서가 있고, 중복을 허용하는 자료구조라 한다.
- 배열 : 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다.
- 리스트 : 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다.
- ✔️MyArrayListV1 구현
- 배열을 활용해서 리스트 자료 구조를 직접 만들기
- 정적인 배열을 그대로 사용해서 구현
public class MyArrayListV1 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV1() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV1(int capacity) {
elementData = new Object[capacity];
}
public int size() {
return size;
}
public void add(Object o) {
elementData[size] = o;
size++;
}
public Object get(int index) {
return elementData[index];
}
public Object set(int index, Object element) {
Object oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (elementData[i] == o) {
return i;
}
}
return -1;
}
@Override
public String toString() {
return "MyArrayListV1{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
}public class MyArrayListV1Main {
public static void main(String[] args) {
MyArrayListV1 myArrayListV1 = new MyArrayListV1();
System.out.println("==데이터 추가==");
System.out.println(myArrayListV1);
myArrayListV1.add("a");
System.out.println(myArrayListV1);
myArrayListV1.add("b");
System.out.println(myArrayListV1);
myArrayListV1.add("c");
System.out.println(myArrayListV1);
System.out.println("==기능 사용==");
System.out.println("myArrayListV1.size() " + myArrayListV1.size());
System.out.println("myArrayListV1.get() = " + myArrayListV1.get(2));
System.out.println("myArrayListV1.indexOf() " + myArrayListV1.indexOf("b"));
System.out.println("myArrayListV1.set(), oldValue = " + myArrayListV1.set(1, "f"));
System.out.println(myArrayListV1);
System.out.println("==범위 초과==");
myArrayListV1.add("d");
System.out.println(myArrayListV1);
myArrayListV1.add("e");
System.out.println(myArrayListV1);
// 문제 발생 → Index 5 out of bounds for length 5
myArrayListV1.add("g");
System.out.println(myArrayListV1);
}
}- ✔️MyArrayListV2 구현
- 데이터를 추가할 때 리스트의 크기가 size를 초과할 경우 동적으로 배열을 생성하고 복사를 하여 새로운 배열에 기존 원소를 저장한다.
grow()호출할 때 배열의 크기는 기존과 비교해서 2배씩 증가한다.- 데이터가 하나 추가될 때마다 배열의 크기를 1씩만 증가하게 되면 배열을 복사하는 연산이 자주 발생하게 된다.
- 배열을 새로 복사해서 만드는 연산은 배열을 새로 만들고 또 기존 데이터를 복사하는 시간이 걸리기 때문에 가능한 줄이는 것이 좋다. 이렇게 2배씩 증가하면 배열을 새로 만들고 복사하는 연산을 줄일 수 있다. 반면에 배열의 크기를 너무 크게 증가하면 사용되지 않고 낭비되는 메모리가 많아지는 단점이 발생한다.
- 보통 50%정도 증가하는 방법을 사용한다.
public class MyArrayListV2 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV2() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV2(int capacity) {
elementData = new Object[capacity];
}
public int size() {
return size;
}
public void add(Object o) {
if (size == elementData.length) {
grow();
}
elementData[size] = o;
size++;
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
public Object get(int index) {
return elementData[index];
}
public Object set(int index, Object element) {
Object oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (elementData[i] == o) {
return i;
}
}
return -1;
}
@Override
public String toString() {
return "MyArrayListV1{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
}public class MyArrayListV2Main {
public static void main(String[] args) {
MyArrayListV2 myArrayListV2 = new MyArrayListV2();
myArrayListV2.add("a");
myArrayListV2.add(2);
myArrayListV2.add(3);
myArrayListV2.add(4);
myArrayListV2.add(5);
System.out.println(myArrayListV2);
// 용량 다 찬 상태에서 새로운 원소를 추가할 경우
myArrayListV2.add(6);
System.out.println(myArrayListV2);
}
}
- ✔️MyArrayListV3 구현
add(Index, 데이터): index 위치에 데이터를 추가한다.remove(Index)index 위치의 데이터를 삭제한다.- 앞이나 중간 위치에 데이터를 추가하면 배열에 들어있는 기존 데이터의 위치를 한 칸씩 먼저 이동하고 데이터를 추가해야 한다.
- 삭제의 경우에도 중간에 있는 데이터를 삭제하면 빈 자리를 채우기 위해 데이터를 한 칸씩 왼쪽으로 이동해야 한다.
- 배열 리스트의 빅오
- 데이터 추가
- 마지막에 추가 : O(1)
- 앞, 중간에 추가 : (N)
- 데이터 삭제
- 마지막에 삭제 : O(1)
- 앞, 중간에 삭제 : O(N)
- 인덱스 조회 : O(1)
- 데이터 검색 : O(N)
- 데이터 추가
public class MyArrayListV3 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV3() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV3(int capacity) {
elementData = new Object[capacity];
}
public int size() {
return size;
}
public void add(Object o) {
if (size == elementData.length) {
grow();
}
elementData[size] = o;
size++;
}
public void add(int index, Object o) {
if (size == elementData.length) {
grow();
}
shiftRightFrom(index);
elementData[index] = o;
size++;
}
private void shiftRightFrom(int index) {
for (int i = size; i > index; i--) {
elementData[i] = elementData[i-1];
}
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
public Object get(int index) {
return elementData[index];
}
public Object set(int index, Object element) {
Object oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (elementData[i] == o) {
return i;
}
}
return -1;
}
public Object remove(int index) {
Object o = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return o;
}
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i+1];
}
}
@Override
public String toString() {
return "MyArrayListV1{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
}public class MyArrayListV3Main {
public static void main(String[] args) {
MyArrayListV3 myArrayListV3 = new MyArrayListV3();
myArrayListV3.add("a");
myArrayListV3.add("b");
myArrayListV3.add("c");
System.out.println(myArrayListV3);
System.out.println("addLast");
myArrayListV3.add(3, "addLast");
System.out.println(myArrayListV3);
System.out.println("addFirst");
myArrayListV3.add(0, "addFirst");
System.out.println(myArrayListV3);
Object removed1 = myArrayListV3.remove(4);
System.out.println("remove(4) = " + removed1);
System.out.println(myArrayListV3);
Object removed2 = myArrayListV3.remove(0);
System.out.println("remove(0) = " + removed2);
System.out.println(myArrayListV3);
}
}- ✔️MyArrayListV4 구현
Object를 입력받기 때문에 아무 데이터나 입력받을 수 있고 또 결과로Object를 반환한다. 따라서 필요한 경우 다운캐스팅을 해야하고, 타입 안전성이 떨어지는 단점이 있다.Object[]를 그대로 사용하는 이유 : 제네릭은 런타임 시기에 이레이저에 의해 타입 정보가 사라진다. 따라서 런타임에 타입 정보가 필요한 생성자에 사용할 수 없다. 제네릭을 기반으로 배열을 생성하는 다음 코드는 작동하지 않고 컴파일 오류가 발생한다.- 컴파일 시점에
T[]와 같은 코드를 작성하면 컴파일러가 이를 인식할 수 없다.
public class MyArrayListV4BadMain {
public static void main(String[] args) {
MyArrayListV3 numberList = new MyArrayListV3();
numberList.add(1);
numberList.add(2);
numberList.add(3);
numberList.add("숫자");
System.out.println(numberList);
// Object를 반환하는 get
Integer i0 = (Integer) numberList.get(0);
Integer i1 = (Integer) numberList.get(1);
System.out.println(i0);
System.out.println(i1);
// class java.lang.String cannot be cast to class java.lang.Integer (java.lang.String and java.lang.Integer are in module java.base of loader 'bootstrap')
Integer i3 = (Integer) numberList.get(3);
System.out.println(i3);
}
}public class MyArrayListV4<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV4() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV4(int capacity) {
elementData = new Object[capacity];
}
public int size() {
return size;
}
public void add(E e) {
if (size == elementData.length) {
grow();
}
elementData[size] = e;
size++;
}
public void add(int index, E e) {
if (size == elementData.length) {
grow();
}
shiftRightFrom(index);
elementData[index] = e;
size++;
}
private void shiftRightFrom(int index) {
for (int i = size; i > index; i--) {
elementData[i] = elementData[i-1];
}
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) elementData[index];
}
public E set(int index, E e) {
E oldValue = get(index);
elementData[index] = e;
return oldValue;
}
public int indexOf(E o) {
for (int i = 0; i < size; i++) {
if (elementData[i] == o) {
return i;
}
}
return -1;
}
public E remove(int index) {
E o = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return o;
}
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i+1];
}
}
@Override
public String toString() {
return "MyArrayListV1{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
}public class MyArrayListV4Main {
public static void main(String[] args) {
MyArrayListV4<String> stringList = new MyArrayListV4<>();
stringList.add("a");
stringList.add("b");
stringList.add("c");
String string = stringList.get(0);
System.out.println(string);
MyArrayListV4<Integer> integerList = new MyArrayListV4<>();
integerList.add(1);
integerList.add(2);
integerList.add(3);
Integer integer = integerList.get(0);
System.out.println(integer);
}
}- ✔️정리
- 배열리스트는 순서대로 마지막에 데이터를 추가하거나 삭제할 때는 좋다.
- 하지만 앞이나 중간에 데이터를 추가하거나 삭제할 때는 성능이 좋지 않다.
