1. 추상 자료형이란?
구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것이다. 추상 자료형은 사용하는 영역에 따라 의미상 약간의 차이가 있지만 본질적으로 같은 맥락이기 때문에 이 부분을 생각하고 이해해야한다. 자료구조에서 추상 자료형은 선풍기의 사용 설명서와 같다고 생각하면 된다. 사용 설명서에 정지, 미풍, 약풍, 강풍, 회전, 타이머 등의 기능 설명과 사용 방법이 나와있지만 실제로 선풍기 내부에서 어떻게 동작하는지는 설명되어 있지 않다. 이렇게 사용자가 선풍기의 본질을 몰라도 사용할수 있는 것이 추상 자료형이다.
구체적인 기능의 완성과정을 언급하지 않고 순수하게 기능이 무엇인지 나열한 것이다.
자료구조 구현(미풍, 약풍, 강풍 등)과 구현된 자료구조의 활용(선풍기 동작원리)는 완전히 구분되어야한다.
2. 순차 리스트란? (ArrayList)
배열을 기반으로 구현된 리스트이다.
배열(Array)
같은 타입의 데이터를 그룹핑하여 관리하기 위한 자료구조로 index-value 구조로 이루어지며 리스트를 구현하기 위해 주로 사용된다.
▶장점
구현이 용이하고 추가적인 메모리 공간이 필요없다.
index로 바로 element에 접근이 가능하기 때문에 탐색 속도가 빠르다.
▶단점
메모리 크기가 고정된 static변수이기 때문에 확장이 불가능하다.
저장/처리해야 하는 데이터 수가 정확하지 않으면 빈공간으로 메모리 낭비가 발생할 수 있다.
데이터를 삽입하고 삭제할 때마다 해당 index기준 오른쪽 데이터가 모두 이동해야한다.
데이터를 순서대로 메모리에 연속해서 저장하는 자료 구조이다. 배열과 동일하게 <index, value>를 가지고 있다. 배열의 단점인 정적 크기 단점을 극복한다. 데이터를 삽입/삭제하는 경우 원소의 개수의 맞게 크기를 조정하고 중간에 빈 공간을 허용하지 않는다.
사용자 입장에서는 보이지 않지만 내부적으로 배열을 사용하기 때문에 배열과 동일하게 요소를 복사, 이동, 삭제하는 과정은 동일하다. 데이터 용량이 변경되는 경우 새로운 배열을 생성하고 기존의 배열을 복사한다.
2-1. ArrayList 추가
// add()
ArrayList arrList = ArrayList<>()
arrList.add("a")
arrList.add("b")
arrList.add("c")ArrayList에서 add를 이용해 자료를 추가할 수 있다.
// add 내부 구현
public boolean add(E e) { // E: String, e = "a"
modCount++;
add(e, elementData, size); // add("a", elementData, 0) -> elementData는 ArrayList가 저장되는 배열 버퍼이다.
return true;
}
private void add(E e, Object[] elementData, int s) {
if(s == elementData.length) elementData = grow(); // elementData.length == size 일경우 grow() 호출
elementData[s] = e;
size = s + 1;
}- size
- ArrayList의 사이즈를 의미한다. (포함하는 요소의 수) 현재 리스트가 empty이기 때문에 0이다.
- modCount
- ArrayList 자료구조가 몇번 수정되었는지 체크하는 필드이다.
modCount와 expectedModCount 이란?
modCont는 자료구조가 수정된 횟수를 저장하게 된다. 평소엔 무시 될수 있지만 ArrayList는 for each문을 도는 동안 변형이 오면 안되기 때문에 이런 경우에 사용한다. expectedModCount는 ArrayList 내부의 ltr의 멤버 변수이다. for each문을 실행시켜 iterator이 생성될때 modCount의 값으로 초기화가 되게 된다. 반복문을 도는 동안 modCount의 개수가 변하게 된다면 ArrayList의 자료가 수정되었다는 것이기 때문에 오류가 발생하게 된다. 반복문을 도는 동안 modCount와 expectedModCount를 비교하여 ArrayList의 데이터 상태를 체크한다.
- elementData
- ArrayList의 요소가 저장되는 배열 버퍼이다.
add 메소드가 호출되게 되는 경우 size와 elementData.length를 비교하여 동일하게 된다면 grow()를 호출하게 된다. grow()는 현재 할당된 elementData의 길이와 ArrayList의 길이를 비교해 요소의 개수가 같아진다면 배열의 사이즈를 늘리는 역할을 한다.
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 기존 용량 + 기존 용량 / 2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}ArrayList의 사이즈를 나타내는 capacity 인스턴스 변수가 있기 때문에 가능하다. 기존 크기 + 기존 크기 / 2 만큼 배열을 copy한다. (1.5배 크게 복사한다.)
2-2. ArrayList 조회
ArrayList에서 자료를 조회하는 방법은 index로 검색하는 방법이 있다.
arrList.get(0); // index가 0인 자료를 조회한다.// get 내부구현
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
// Objects.checkIndex()
public static int checkIndex(int index, int length) {
return Preconditions.checkIndex(index, length, null);
}
// Preconditions.checkIndex()
public static <X extends RuntimeException>
int checkIndex(int index, int length,
BiFunction<String, List<Integer>, X> oobef) {
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
return index;
}매개변수로 넘어온 index가 ArrayList의 크기보다 큰지와 0보다 작은지를 체크하고 문제가 없다면 elementData에서 index의 값을 찾아 반환해준다.
2-3 ArrayList 삭제
ArrayList에서 요소를 삭제하는 방법은 index, value 2가지가 있다.
- Object로 삭제하기
arrList.remove("a");public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false; // Object가 없을 경우
}
fastRemove(es, i);
return true;
}
private void fastRemove(Object[] es, int i) {
modCount++; // 자료구조가 변경되었기 때문에 modCount 증가
final int newSize;
if ((newSize = size - 1) > i) // 배열의 마지막 값을 계산하지 않음
System.arraycopy(es, i + 1, es, i, newSize - i);
// 원본 배열의 i+1의 값을 복사할 배열의 i의 값에 복사
es[size = newSize] = null; // 배열의 마지막 값을 null로 바꿈
}
/**
* Params:
* src - 원본 배열
* srcPos - 원본 배열의 복사 시작 위치. 여기서부터 전부 복사합니다.
* dest - 복사할 배열
* destPost - 복사할 배열의 복사 시작 위치. 여기서부터 전부 덮어씁니다.
* length - 복사할 요소의 개수
*/
@HotSpotIntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);Object의 index를 찾아 해당 요소를 삭제하고 나머지 요소들을 앞땡겨온다. 마지막 배열은 비었기 때문에 null로 변경해주는 과정을 거치게 된다.
- index로 삭제하기
arrList.remove(0);public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}index로 요소를 제거하는 경우 index를 탑색하지 않아도 되기 때문에 값이 유효한지만 체크하게 된다.
2-4 Array vs ArrayList
| Array | ArrayList | |
| 사이즈 | 초기화시에 고정된다. | 초기화시에 사이즈를 표시하지 않고 동적이다. |
| 속도 | 초기화 시에 메모리에 할당되기 때문에 빠르다. | 메모리를 재할당하여 느리다. |
| 변경 | 사이즈 변경이 불가능하다. | 추가, 삭제가 가능하다. |
| 다차원 | 가능하다. | 불가능하다. |
| 타입 | 원시타입, object | object elemnet |
| 제네릭 | 불가능하다. | 가능하다. (타입 안전성을 보장한다.) |
| 길이 | length | size() |
| 변수 추가 | assignment 연산자를 사용한다. | add() |
3. 깊은 복사 (deep copy)와 얕은 복사 (shallow copy)
복사를 하는 경우 데이터를 수정하게 된다면 깊은 복사인지 얕은 복사인지에 따라 다른 데이터도 함께 수정될 수 있기 때문에 복사에 대한 개념을 이해하고 구분을 할줄 알아야한다.
3-1 얕은 복사 (shallow copy)
얕은 복사란 객체를 복사할 때 객체의 주솟값을 복사하는 방법이다. = 을 이용해 단순 대입으로 복사한다.
fun main() {
val origin = ArrayList<String>()
origin.add("a")
origin.add("b")
var swallowCopy = ArrayList<String>()
swallowCopy = origin
swallowCopy.removeAt(1) // 얕은 복사한 swallowCopy list에서 1번 요소를 제거
println(origin.toString()) // a -> 얕은 복사를 했기 때문에 origin list의 1번 요소도 제거됨
}얕은 복사를 하였기 때문에 두 변수가 같은 주소값을 참조해 list1의 멤버 변수만 변경하였지만 list2의 멤버 변수도 같이 변경되었다.
3-2 깊은 복사 (deep copy)
깊은 복사란 객체를 복사할때 객체의 전체 값이 복사되는 방법이다. 객체 전체를 복사했기 때문에 객체의 값을 변경해도 다른 객체에 영향을 미치지 않는다.
val origin = ArrayList<String>()
origin.add("a")
origin.add("b")
var deepCopy = ArrayList<String>()
deepCopy.addAll(origin) // 깊은 복사를 함
deepCopy.removeAt(1) // 1번 요소 삭제
println(origin.toString()) // a,b
kotlin은 기본적으로 2가지 방법을 사용해 깊은 복사가 가능하다.
4. 코틀린 깊은 복사
4-1. Cloneable
Cloneable 인터페이스를 상속받아 clone() 메소드를 오버라이딩하는 것이다. 단, 원시타입의 멤버변수만 깊은 복사가 가능하기 때문에 아래와 같은 경우 리스트는 얕은 복사가 되게 된다.
// Cloneable 상속은 원시타입만 깊은 복사가 되게 된다.
class SampleClass(var id: Int, var list: MutableList<Int>) : Cloneable {
public override fun clone(): SampleClass {
return super.clone() as SampleClass
}
}때문에 모든 멤버 변수를 깊은 복사해주기 위해선 clone 메소드를 재정의 해줘야한다.
4-2 Copy
data class가 제공해주는 메소드 중에 copy를 사용하는 방법이 있다. 단, data class의 copy도 원시타입만 깊은 복사를 해주기 때문에 재정의해주는 과정이 필요하다. 하지만 copy는 Any의 메소드가 아니기 때문에 정의하려면 override가 아닌 일반 함수로 정의해줘야한다.
data class SampleClass(val id: Int, val list: MutableList<Int>) {
// override가 아닌 일반 함수로 정의
fun copy(): SampleClass {
return SampleClass(id, list.toMutableList())
}
}'CS > 자료구조' 카테고리의 다른 글
| 연결 리스트 (Linked List) (0) | 2023.06.03 |
|---|---|
| 재귀(Recursion) (0) | 2023.04.25 |
| 자료구조와 알고리즘의 이해 (0) | 2023.04.24 |
