1. ArrayList 직접 구현하여 사용하기
ArrayList는 이전 포스팅에서도 설명하였듯이 배열(Array)를 기반으로 하는 자료구조이다. 하나의 객체로써 사용되며 배열의 크기를 미리 설정하지 않아도 자료를 쉽게 넣고 뺄 수 있는 자료구조 이다.
그러나 배열을 기반으로 하기 때문에 LinkedList와는 달리 삽입 / 삭제 시에 시간 복잡도가 걸릴 수 있다.
아래의 코드를 통해 직접 구현한 코드를 확인해보자.
package com.test;
public class ArrayListImpl<T>{
// ArrayList는 배열을 기반으로 하는 자료구조
// 요구조건 : 객체로써 생성되어 배열의 재생성 없이 자료의 저장 / 삭제 / 참조가 가능해야 함
private Object element[];
private int size;
private int capacity;
private static final int default_capacity = 10;
public ArrayListImpl(){
element = new Object[default_capacity];
capacity = default_capacity;
this.size = 0;
}
public ArrayListImpl(int capacity){
if(capacity == 0){
this.element = new Object[this.default_capacity]{};
capacity = this.default_capacity;
} else {
element = new Object[capacity];
}
this.capacity = capacity;
this.size = 0;
}
private void sizeUp(){
if(this.capacity == 0){
element = new Object[default_capacity];
this.capacity = default_capacity;
} else {
Object temp[] = new Object[this.capacity*2];
System.arraycopy(this.element, 0, temp, 0, size);
this.capacity *= 2;
}
}
// Data를 특정 index 값에 집어 넣는 함수
public boolean add(int index, T data){
if(index < 0 || index > this.size){
throw new IllegalArgumentException();
}
if(this.element.length == this.size){
this.sizeUp();
}
for(int i=this.size-1; i >= index; i--){
element[i+1] = element[i];
}
element[index] = data;
this.size++;
return true;
}
// Data를 앞에서 집어 넣는 함수
public boolean addFront(T data){
return this.add(0, data);
}
// Data를 뒤에서 집어 넣는 함수
public boolean addBack(T data){
return this.add(this.size, data);
}
public T poll(int index){
if(index < 0 || index >= this.size){
throw new IllegalArgumentException();
}
T temp = (T) this.element[index];
for(int i=index+1; i < this.size; i++){
this.element[i-1] = this.element[i];
}
this.element[size-1] = null;
this.size--;
return temp;
}
// Data를 앞에서 빼내는 경우
public T pollFront(){
return poll(0);
}
// Data를 뒤에서 빼내는 경우
public T pollBack(){
return poll(this.size-1);
}
// 특정 index에 있는 값을 참조하고 싶은 경우
public T get(int index){
if(index < 0 || this.size <= index){
throw new IllegalArgumentException();
}
return (T) this.element[index];
}
// 제일 첫 데이터를 참조 하는 경우
public T peekFront(){
return get(0);
}
// 제일 끝 데이터를 참조하는 경우
public T peekBack(){
return get(this.size-1);
}
// 현재 배열이 비어있는지 확인하고 싶은 경우
public boolean isEmpty(){
return this.size == 0;
}
// 현재 배열의 크기를 알고 싶은 경우
public int getSize(){
return this.size;
}
// 현재 배열을 비우고 싶은 경우
public void clear(){
this.element = new Object[this.capacity];
}
// Iterator 가져오기
public Iterator getIterator(){
return new Iterator();
}
class Iterator{
// 현재 탐색할 순서를 가리키는 Index
private int nextIndex = 0;
// next 값이 있는지 확인하는 메소드
public boolean hasNext(){
return nextIndex < getSize();
}
// next 값을 반환하는 메소드
public T next(){
if(!hasNext()){
throw new IllegalArgumentException();
}
return (T)element[nextIndex++];
}
// previous 값이 있는 확인하는 메소드
public boolean hasPreviousr(){
return size > 0 && nextIndex > 0;
}
// previous 값을 반환하는 메소드
public T previous(){
return (T)element[--nextIndex];
}
// 현재 index에 element를 추가한다.
public boolean add(T element){
return ArrayListImpl.this.add(nextIndex++, element);
}
// 현재 index의 element를 제거한다.
public T poll(){
T temp = ArrayListImpl.this.poll(nextIndex-1);
nextIndex--;
return temp;
}
}
}
각각의 Method들에 대해서 간단히 이해해보자.
① 생성자
코드의 상단에 생성자가 두 가지 있는 것을 확인할 수 있다. ArrayList는 배열을 기반으로 구현되었기 때문에 배열의 크기를 지정해 생성하기 위한 내용으로 구성된다.
| Method | 내용 |
| ArrayListImpl() | DEFAULT 값을 기반으로 배열의 크기를 정해 생성 |
| ArrayListImpl(int capacity) | 전달된 capacity 값을 기반으로 배열을 생성 |
② 기타 Method
각 Method들은 배열에 값을 넣고 빼내기 위한 Method로 구현되어 있다.
삽입 method : add, addFront, addBack
추출 method : poll, pollFront, pollBack, get
기타 method : sizeUp, isEmpty, clear, getSize
삽입 Method는 배열에 값(data)을 넣기 위한 동작을 수행한다. add는 현재 index에 값을 넣기 전, index의 값이 적절한 범위 내에 있는 값인지 확인 하고 기존의 값들을 한 칸씩 밀어낸 뒤 해당 index에 값을 삽입한다.
addFront / addBack은 0번, size-1번 위치에 값을 삽입하는 함수로 구성되어 있다. 아래의 코드를 통해 다시 확인해보자.
// Data를 특정 index 값에 집어 넣는 함수
public boolean add(int index, T data){
if(index < 0 || index > this.size){
throw new IllegalArgumentException();
}
if(this.element.length == this.size){
this.sizeUp();
}
for(int i=this.size-1; i >= index; i--){
element[i+1] = element[i];
}
element[index] = data;
this.size++;
return true;
}
// Data를 앞에서 집어 넣는 함수
public boolean addFront(T data){
return this.add(0, data);
}
// Data를 뒤에서 집어 넣는 함수
public boolean addBack(T data){
return this.add(this.size, data);
}
추출 Method 중 poll 함수는 전달 된 index 값의 유효한 범위를 확인하고 해당 index에 저장된 배열 값을 별도로 저장한 뒤 그 뒤의 배열 값을 한 자리씩 앞당겨 저장하고 반환한다.
pollFront / pollBack은 0번, size-1번 index의 데이터를 반환하도록 구성되어 있으며, get 함수는 index내 값을 빼내지 않고 값 자체만 반환한다.
public T poll(int index){
if(index < 0 || index >= this.size){
throw new IllegalArgumentException();
}
T temp = (T) this.element[index];
for(int i=index+1; i < this.size; i++){
this.element[i-1] = this.element[i];
}
this.element[size-1] = null;
this.size--;
return temp;
}
// Data를 앞에서 빼내는 경우
public T pollFront(){
return poll(0);
}
// Data를 뒤에서 빼내는 경우
public T pollBack(){
return poll(this.size-1);
}
// 특정 index에 있는 값을 참조하고 싶은 경우
public T get(int index){
if(index < 0 || this.size <= index){
throw new IllegalArgumentException();
}
return (T) this.element[index];
}
그 외의 method는 현재 값이 들어간 숫자(size)를 가져오거나(getSize), 배열이 비어있는지를 반환(isEmpty)하거나 새로운 배열을 생성(clear)하거나 iterator를 반환하도록 구성되어 있다.
// 현재 배열이 비어있는지 확인하고 싶은 경우
public boolean isEmpty(){
return this.size == 0;
}
// 현재 배열의 크기를 알고 싶은 경우
public int getSize(){
return this.size;
}
// 현재 배열을 비우고 싶은 경우
public void clear(){
this.element = new Object[this.capacity];
}
// Iterator 가져오기
public Iterator getIterator(){
return new Iterator();
}
class Iterator{
// 현재 탐색할 순서를 가리키는 Index
private int nextIndex = 0;
// next 값이 있는지 확인하는 메소드
public boolean hasNext(){
return nextIndex < getSize();
}
// next 값을 반환하는 메소드
public T next(){
if(!hasNext()){
throw new IllegalArgumentException();
}
return (T)element[nextIndex++];
}
// previous 값이 있는 확인하는 메소드
public boolean hasPreviousr(){
return size > 0 && nextIndex > 0;
}
// previous 값을 반환하는 메소드
public T previous(){
return (T)element[--nextIndex];
}
// 현재 index에 element를 추가한다.
public boolean add(T element){
return ArrayListImpl.this.add(nextIndex++, element);
}
// 현재 index의 element를 제거한다.
public T poll(){
T temp = ArrayListImpl.this.poll(nextIndex-1);
nextIndex--;
return temp;
}
}
2. 간단히 구현하기
알고리즘이나 여러 문제를 해결하기 위해 보통 자료구조를 많이 사용하게 된다. 대부분 자바의 JDK에 구현된 Collection Framework를 사용해 구현하는 경우가 많다. 그러나 대회 등에서는 직접 구현해야 하는 경우도 많고 자료구조를 이해하기 위해서는 직접 구현해보는 노력을 하는 것이 좋다.
위에서 구현한 방식은 실제 구현된 자바의 Collection Framework 내 코드를 참고하여 만들었는데, 알고리즘과 같이 빠르게 문제를 해결해야 하는 경우가 있다면 다양한 경우에 대해 모두 상정하지 않고 필요한 내용만 구현하는 것도 나쁘지 않다. 아래와 같은 코드로 주로 사용할 수 있다.
package com.teset;
public class ArrayListImpl<T>{
private Object element[];
private int size;
private int capacity;
private static final int default_capacity = 10000000;
public ArrayListImpl2(){
element = new Object[default_capacity];
capacity = default_capacity;
this.size = 0;
}
// Data를 특정 index 값에 집어 넣는 함수
public boolean add(int index, T data){
for(int i=this.size-1; i >= index; i--){
element[i+1] = element[i];
}
element[index] = data;
this.size++;
return true;
}
public boolean addLast(T data){
return this.add(this.size-1, data);
}
// 특정 index의 data를 반환하는 함수
public T poll(int index){
T temp = (T) this.element[index];
for(int i=index+1; i < this.size; i++){
this.element[i-1] = this.element[i];
}
this.element[size-1] = null;
this.size--;
return temp;
}
public T pollLast(){
return this.poll(this.size-1);
}
// 특정 index에 있는 값을 참조하고 싶은 경우
public T get(int index){
return (T) this.element[index];
}
// 현재 배열이 비어있는지 확인하고 싶은 경우
public boolean isEmpty(){
return this.size == 0;
}
// 현재 배열의 크기를 알고 싶은 경우
public int getSize(){
return this.size;
}
// 현재 배열을 비우고 싶은 경우
public void clear(){
this.element = new Object[this.capacity];
}
}
이전의 ArrayList Collection Framework 포스팅은 아래의 링크를 참고 부탁 드립니다.
https://hongjw1938.tistory.com/4?category=884192
자료구조(Java) - Collection Framework
자바(Java)에서는 다양한 자료구조를 사용자가 쉽게 활용하도록 성능적으로도 우수하며 코딩에 할애하는 시간을 줄일 수 있는 Collection Framework를 제공하고 있다. 이 Collection Framework는 자료를 저장
hongjw1938.tistory.com
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - HashMap 들여다보기(1) (0) | 2020.08.19 |
|---|---|
| LinkedList 직접 구현해보기 (Java) (0) | 2020.08.15 |
| 자료구조(Java) - Comparable / Comparator (2) | 2020.07.27 |
| 자료구조(Java) - Iteration (0) | 2020.07.26 |
| 자료구조(Java) - Collection Framework 2 (2) | 2020.07.26 |
