자료구조에 관한 설명
https://hyennis-room.tistory.com/73
[JAVA] 자료구조와 알고리즘
자료구조(data structure) : 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미함. 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령.
hyennis-room.tistory.com
▶ArrayList
: java에서 제공하는 동적 배열기반의 리스트 구현 클래스(컬렉션).(인터페이스 List를 구현한다.)
크기가 가변적으로 변하는 선형리스트이며 값의 중복을 허용한다.
- 내부 배열로 Object[]로 사용하고 최초 할당 크기는 10이다.
- 동적으로 크기 조절이 가능 => 요소의 삽입 삭제에 따라 자동으로 크기가 조절되서 유연한 요소 관리 가능
- 인덱스 기반 요소 접근 => 내부 배열을 사용하여 요소를 인덱스를 통해 접근. 임의의 요소 빠르게 접근 가능
- 순차적인 데이터 저장
- 중복 요소 허용
- 배열기반의 구현으로 중간 삽입/삭제의 경우 느릴것..
- 내부 변수 modCount : ArrayList 클래스에서 내부적으로 사용되는 변수로 리스트의 수정횟수를 추적하는 역할.
이를 통해 구조 변경 여부를 확인하고, 반복 도중에 구조가 변경되는 것을 방지한다.
▶ArrayList의 메서드
- add : 배열에서 순차적으로 요소를 넣음, 인덱스 인자를 받으면 해당 인덱스 자리에 요소를 넣고 기존 값을 뒤로 미룬다. addAll(Collection) 다른 컬렉션은 넣을 수 있다.
- set : 전달받은 인덱스 요소의 값을 바꿈 반환값은 바꾸기 전의 원본요소를 반환한다.
- get : 전달받은 인덱스의 요소를 반환해준다. // 리스트의 메서드를 구현할 때 클래스 내부에서 배열에서 직접 꺼내 쓰는것이 성능에 더 좋다.
- remove : 특정요소 및 인덱스 위치의 요소를 찾아 삭제한다. removeAll(Collection) 컬렉션 요소를 찾아서 해당 값을 삭제한다.
- retainAll(Collection) : 컬렉션 요소를 비교해서 해당값 외의 요소를 삭제한다.(중복 가능)
- contains : indexOf를 사용하여 해당 요소(및 컬렉션 요소)의 값이 있으면 true 없으면 false 반환
- isEmpty : 리스트(배열)의 크기를 확인해서 해당 크기가 0 이면 true, 0 이상이면 false 반환
- clear : 배열의 값을 새로 생성해줘도 되지만 반복문을 돌려서 null로 할당해야 가비지 컬렉터(GC)가 수거해간다.
- indexOf : 배열을 반복문을 돌려서 해당 요소의 값과 동일하면 해당 값의 인덱스위치를 반환, 없으면 -1 반환. 동일한 값 비교시 equals를 사용하여 값 비교를 한다.(Object) / null 값비교도 포함되어야 하기 때문에 if문으로 null값을 먼저 체크한다.
- toArray : Object 배열로 변환 및 전달받은 타입의 배열로 바꿔준다.
- subList : 원본 리스트의 일부분을 보여주는 view의 리스트로 반환한다. ArrayList 클래스의 내장 객체를 사용한다. 해당 subList의 값이 변동되면 원본리스트에도 반영된다.
- Iterator : 해당 리스트의 요소를 순차적으로 접근하고 삭제하는데 사용. Iterator를 사용하여 컬렉션의 요소를 반복하는 것은 안전하고 효율적이다. 컬렉션의 내부구조에 직접 접근하므로, 컬렉션이 수정되는 경우 ConcurrentModificationException라는 예외 방지할 수 있다.
MyArrayList 간단한 것만 구현해보기...
- Object [ ] items : 배열 초기 크기 10 할당.
- int size : 배열 크기
- indexOf 먼저 구현해서 활용하는게 더 쉬움
- 배열의 크기가 넘어가면 배열 크기를 늘리는 리사이징 부분을 메서드로 만들어 활용
- 되도록이면 시간복잡도 최소를 고려하도록
▶ size( ), isEmpty( ) : size 변수 그대로 반환, size == 0 이면 isEmpty == true
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
// isEmpty() 비어있으면 true == 0
if (size == 0) return true;
return false;
}
▶ indexOf / lastIndexOf
- null 값에 대한 체킹 : Object 클래스의 equals 메서드로 null을 비교할수 없으니 직접 null값을 따로 빼서 비교
- 나머지 값 : Object 클래스의 equals 메서드로 비교
@Override
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++) {
if (items[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (o.equals(items[i])) {
return i;
}
}
}
return -1;
}
@Override
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size - 1; i >= 0; i--) {
if (items[i] == null) {
return (size - 1) - i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (o.equals(items[i])) {
return (size - 1) - i;
}
}
}
return -1;
}
▶ contains(Object o) / containsAll(Collection c)
- indexOf메서드를 사용하여 해당 값이 있으면(값이 0 이상) true
- collection 반복문을 돌려서 indexOf 메서드 사용
@Override
public boolean contains(Object o) {
if (indexOf(o) > -1) return true;
return false;
}
@Override
public boolean containsAll(Collection<?> c) {
// 반복문으로 요소 하나하나 indexOf로 해당 요소가 있는지 판단한다.
for(Object o : c.toArray()){
if(indexOf(o) < 0){
return false;
}
}
return true;
}
▶ clear
- 배열의 초기화 및 size 변수를 0 초기화 해도 되지만
- 반복문을 돌려서 배열을 null로 해야지 JVM의 가비지컬렉터GC 가 수거해간다고 한다.
// 수정전
@Override
public void clear() {
Object[] newItem = new Object[10];
items = newItem;
size = 0;
}
// 수정후
public void clear() {
for (int i = 0; i < items.length; i++) {
items[i] = null;
}
size = 0;
}
▶ get(int index) / set(int index, E e)
- 배열에 대한 인덱스 범위 체킹
- 해당 배열에서 인덱스 값으로 찾음
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " is out of bounds.");
}
E rs = (E) items[index];
return rs;
}
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " is out of bounds.");
}
E rs = (E) items[index];
items[index] = element;
return rs;
}
▶ add(E e)
- 배열에 삽입하기 전에 배열의 크기 확인
- 배열의 크기가 다 차면 2배 크기의 배열을 새로 생성
- 배열에 추가하면 size 변수 증가
- 보완할 점 : 배열 리사이징하는 것을 따로 메서드로 구현
@Override
public boolean add(E e) {
if (size >= items.length) {
Object[] newItem = new Object[size * 2];
for (int i = 0; i < items.length; i++) {
newItem[i] = items[i];
}
items = newItem;
}
items[size] = e;
size++;
return true;
}
▶ add(int index, E element)
- 인덱스 예외처리
- 기존 배열 크기 다 찼을 경우 리사이징
- 배열에 추가하면 size 변수 증가
// 수정전
@Override
public void add(int index, E element) {
Object[] newItem = new Object[size + 1 > items.length ? size * 2 : items.length];
// index 앞, index 뒤, 해당 요소 복사
for (int i = 0; i < index; i++) {
newItem[i] = items[i];
}
for (int i = 0; i < size - index; i++) {
newItem[index + i + 1] = items[index + i];
}
newItem[index] = element;
size++;
}
▶ addAll(Collection c) / addAll(int index, Collection c)
- 해당 배열에 컬렉션 요소 삽입하기.
- 배열의 크기가 다 찼을 경우 Object 배열 리사이징
- index 중간삽입경우 앞, 뒤 요소 따로 복사하고 그 중간에 컬렉션 요소 하나씩 복사
- 보완할 점 : 위에서 구현했던 add(E e) 메서드 사용
// 수정전
@Override
public boolean addAll(Collection<? extends E> c) {
// c를 array로 변환
Object[] cArr = c.toArray();
// 기존 데이터 + 추가하려는 데이터 > 더 크다면 배열 크기 늘리기
if (size + c.size() > items.length) {
Object[] newItem = new Object[size + c.size()];
// 기존배열 복사하고 그 이후에 넣기
for (int i = 0; i < size; i++) {
newItem[i] = items[i];
}
for (int i = 0; i < cArr.length; i++) {
newItem[size + i] = cArr[i];
size++;
}
items = newItem;
} else {
// 기존 배열 크기가 크다면 다음 인덱스부터 넣기
for (int i = 0; i < cArr.length; i++) {
items[size] = cArr[i];
size++;
}
}
return true;
}
// 수정후
@Override
public boolean addAll(Collection<? extends E> c) {
// 반복문을 돌려서 add(E e) 메서드 사용
for(Object o : c.toArray()){
add((E) o);
}
return true;
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
// add(index, E e) 메서드 활용하기
for(Object o : c.toArray()){
add(index + 1, (E) o); // 해당 인덱스 다음부터 넣기
}
return true;
}
▶ remove(int indext)
- 인덱스 예외처리
- 반환값 따로 빼기
- 해당 인덱스 배열의 값 한칸씩 땡기기
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " is out of bounds.");
}
E rs = (E) items[index];
items[index] = null;
for (int i = index; i < size - 1; i++) {
items[i] = items[i + 1];
items[i + 1] = null;
}
size--;
return rs;
}
▶ remove(Object o)
- 해당 요소의 인덱스를 찾음
- 위에서 구현했던 remove(index) 메서드를 사용하여 삭제
@Override
public boolean remove(Object o) {
int targetIdx = indexOf(o);
if (targetIdx == -1) {
return false;
}
remove(targetIdx);
return true;
}
▶ removeAll(Collection c)
- 위에서 구현했던 remove(index)를 사용하여 해당 요소의 index찾아서 삭제
// 수정전
@Override
public boolean removeAll(Collection<?> c) {
if (containsAll(c)) {// 값이 있는지 확인
// 지정한 값만 삭제
Object[] cArr = c.toArray();
for (int i = 0; i < cArr.length; i++) {
int targetIdx = indexOf(cArr[i]);
remove(targetIdx);
}
return true;
} else {
return false;
}
}
// 수정후
@Override
public boolean removeAll(Collection<?> c) {
if(contains(c)){
for(Object o : c.toArray()){
remove(o);
}
return true;
}
return false;
}
▶ retrainAll(Collection c) : 해당 컬렉션 요소를 제외하고 나머지 요소는 삭제
// 수정전
@Override
public boolean retainAll(Collection<?> c) {
if (containsAll(c)) {
Object[] cArr = c.toArray();
for (int i = size -1 ; i >= 0 ; i--) {
if (c.contains(items[i])) {
continue;
}else {
remove(i);
}
}
return true;
} else {
return false;
}
}
▶ toArray() / toArray(T[ ] a)
@Override
public <T> T[] toArray(T[] a) {
if (a.length > items.length) {// 전달받은 배열의 공간이 더 크다면
// a라는 배열에 원본 items 배열을 0인덱스부터 size까지 복사한다.
//이때, a 배열의 인덱스 this.size 이후에 null을 추가로 삽입해주어야 하기 때문에
//추가적인 작업이 수행됩니다. 마지막 요소 이후에 null을 삽입하여 반환
System.arraycopy(items, 0, a, 0, size);
if(a.length > size){
a[this.size] = null;
}
/* for (int i = 0; i < a.length; i++) {
a[i] = (T) items[i];
} */
} else {// 전달받은 배열 공간이 작다면 새로운 배열로 복사하여 반환
/* a = (T[]) new Object[size];
for (int i = 0; i < size; i++) {
a[i] = (T) items[i];
} */
return (T[]) Arrays.copyOf(items, size, items.getClass());
}
return a;
}'JAVA' 카테고리의 다른 글
| [JAVA] 자료구조와 알고리즘 (0) | 2023.07.31 |
|---|---|
| URL Encodeing / Decoding 정리 (0) | 2023.07.27 |
| Wrapper 클래스 Integer의 값 비교 (0) | 2022.12.17 |
| [java] 예외처리 Exception / Finally / Throw (0) | 2022.12.06 |
| JAVA - 객체 지향 복습 (7장) : 추상클래스와 인터페이스 (0) | 2022.12.02 |
