공부했던 자료 정리하는 용도입니다.
재배포, 수정하지 마세요.
ArrayList 구현
Java에는 이미 컬렉션 프레임워크로 ArrayList 가 구현되어 있지만 직접 구현해보는것이 공부에 도움이 될 것 같아서 직접 구현해보기로 했다. Java 에서 ArrayList 는 List 인터페이스를 구현한 클래스이기 때문에 저장 순서가 유지되고 중복을 허용한다는 특징이 있다. 중간 위치의 자료를 추가/삭제할 경우 삭제한 뒤에 재 정렬해서 빈 공간을 없앤다. 또한 자동적으로 크기가 조절되지만 내부적으로는 배열을 이용해서 구현한다.
| ArrayList를 구현할 때 필요한 기능 * 처음, 끝, 중간에 element 를 추가/삭제하는 기능 * 리스트에 데이터가 있는지를 체크하는 기능 * 리스트의 모든 데이터에 접근할 수 있는 기능 |
ArrayList 를 구현하기 전에 먼저 어떤 기능들이 필요한지 살펴본다.
1. 파일 생성
먼저 적절한 이름의 Pakage( list.arraylist.implementtion )를 만들어주고
ArrayList 를 구현할 ArrayList 클래스와 이를 실행시킬 Main 클래스를 만들어준다.
2. 구현
■ 멤버 변수(인스턴스 변수) 선언
ArrayList.java
package list.arraylist.implementation;
public class ArrayList {
//내부에서 사용할 변수와 배열을 선언, 접근제어자를 private으로 지정한다.
private int size = 0; //저장된 데이터의 개수를 세기 위한 변수,
private Object[] elementData = new Object[100]; //내부에서 사용할 배열
}ArrayList 는 내부적으로 배열을 사용하기 때문에 ArrayList 클래스 내부에서 사용할 배열인 elementData 와 저장된 데이터의 개수를 세기 위한 size 변수를 선언한다. 이들은 내부에서만 사용되는 것이기 때문에 접근 지정자를 private 으로 지정한다.
Main.java
package list.arraylist.implementation;
public class Main {
public static void main(String[] args) {
ArrayList numbers = new ArrayList();
}
}Main 에서 new 연산자로 인스턴스를 생성하면 앞으로 구현할 메서드들을 사용할 수 있다.
■ 데이터 추가 (add)
ArrayList.java
//1. 데이터 추가
//1-1. 첫 번째에 데이터를 추가하는 메서드
public boolean addFirst(Object element) {
return add(0, element); //미리 구현한 add메서드를 사용한다.
}
//1-2. 마지막에 데이터를 추가하는 메서드
public boolean addLast(Object element) {
elementData[size] = element;
size++;
return true;
}
//1-3. 지정된 위치에 데이터를 추가하는 메서드
public boolean add(int index, Object element) {
//지정된 위치 뒤의 데이터들을 한칸씩 미는 작업
for(int i = size ; i >= index; i--) {
elementData[i + 1] = elementData[i];
}
//미는 작업이 끝나면 지정된 위치에 데이터 저장
elementData[index] = element;
size++;
return true;
}데이터를 추가하는 메서드를 구현해준다.
ArrayList 는 중간에 빈 공간이 없어야 하기 때문에 중간 위치에 데이터를 추가할 경우 먼저 데이터들을 한 칸식 뒤로 이동시킨 다음에 데이터를 추가해야 한다. 그래서 for 문을 이용해서 데이터를 이동시키는 작업을 했다.
첫 번째에 데이터를 추가하는 addFirst( ) 메서드의 경우에는 첫 번째에 데이터를 추가한다는 것만 빼면 add( ) 메서드와 기능이 동일하기 때문에 add( ) 메서드를 재사용했다.
■ 출력 (toString)
ArrayList.java
//2. ArrayList를 출력하는 메서드
//toString을 오버라이딩하면 객체를 출력할 때(print메서드를 사용한다던지) 원하는 형식으로 출력된다.
public String toString() {
String str = "[";
//저장된 데이터를 str에 추가함
for(int i = 0 ; i < size ; i++) {
str += elementData[i];
if(i < size - 1) {
str += ", ";
}
}
return str + "]"; //최종 문자열 반환
}원래의 ( Object 클래스의) toString( ) 메서드는 현재 객체의 클래스 이름과 객체의 해시 코드 값을 리턴 하지만
오버 라이딩하면 원하는 형식으로 객체를 출력할 수 있다.
Main.java
System.out.println(numbers);
System.out.println(numbers.toString());리턴 값이 String 이므로 메인에서 사용할 때는 print 문을 쓰거나 객체이름.toString( ) 으로 호출해서 사용하면 된다.
■ 데이터 삭제 (remove)
ArrayList.java
//3. 데이터 삭제 메서드
//메서드를 사용하면 삭제된 데이터를 반환한다.
public Object remove(int index) {
Object removed = elementData[index]; //삭제될 데이터를 removed에 임시저장한다.
//빈공간을 메꾸는 작업(뒤의 데이터들을 앞으로 당겨옴)
for(int i = index + 1 ; i <= size - 1 ; i++) { //뒤부터 당기면 전부 같아지기 때문에 앞부터 해야함
elementData[i - 1] = elementData[i];
}
//마지막 데이터 삭제
size--;
elementData[size] = null;
return removed; //삭제된 데이터를 반환
}
//3-2. 첫번째 데이터 삭제
public Object removeFirst() {
return remove(0); //이미 구현된 remove() 메서드를 사용한다.
}
//3-3. 마지막 데이터 삭제
public Object removeLast() {
return remove(size - 1); //마찬가지로 구현되어있는 remove() 메서드를 사용한다.
}
데이터를 삭제하는 메서드를 구현한다.
데이터를 삭제할 때도 마찬가지로 중간 위치의 데이터를 삭제할 경우 빈 공간이 생기면 안 되기 때문에 뒤에 있는 데이터들을 한 칸씩 앞으로 이동시키는 과정이 필요하다. 그래서 for 문으로 데이터들을 이동하는 작업을 했다.
반환 값을 void 로 해서 데이터만 삭제해도 되지만 removed 라는 변수를 사용해서 삭제될 데이터를 임시로 저장했다가 메서드가 끝날 때 반환해서 어떤 데이터가 삭제되었는지 확인할 수 있게 했다.
마지막으로 removeFirst( ) 메서드와 removeLast( ) 메서드는 위지가 지정된 것만 빼면 remove( ) 메서드와 처리과정이 동일하기 때문에 이미 구현되어있는 remove( ) 메서드를 사용하도록 했다.
■ 저장된 데이터를 반환 (get)
ArrayList.java
//4. 지정된 위치에 저장된 데이터를 반환하는 메서드
public Object get(int index) {
return elementData[index];
}인덱스를 파라미터로 주면 해당 인덱스에 저장되어있는 값이 반환된다.
■ 데이터가 저장된 개수를 반환 (size)
ArrayList.java
//5. ArrayList에 저장된 데이터의 개수를 반환하는 메서드
public int size() {
return size;
}위의 메서드를 사용하면 ArrayList 에 저장된 데이터의 개수를 반환한다.
size 를 private 으로 지정한 뒤 특정한 메서드를 통해서만 접근하게 함으로써
데이터의 변조나 허용되지 않은 접근을 막을 수 있다.
■ 데이터의 인덱스를 반환 (indexOf)
ArrayList.java
//6. 데이터의 인덱스를 반환하는 메서드
public int indexOf(Object element) {
for(int i = 0 ; i < size ; i++) {
if(element.equals(elementData[i])) {
return i;
}
}
return -1;
}데이터 값을 파라미터로 주면 데이터가 ArrayList 의 몇 번째 인덱스에 있는지 반환하는 메서드이다. 객체끼리의 비교이므로 == 연산자가 아닌 equals( ) 메서드를 사용했다. 해당하는 값이 없다면 -1 을 반환하도록 구현하였다.
■ 객체에 접근 (iterator - next / previous, hasNext / hasPrevious, add / remove)
ArrayList.java
/*
7. Iterator
* next / hasNext
* previoushasPrevious
* add / remove
*/
public ListIterator listIterator() {
return new ListIterator(); // ListIterator 객체를 새로 생성해서 반환
}
class ListIterator{
private int nextIndex = 0; //접근할 때 사용할 인덱스변수
public boolean hasNext() {
return nextIndex < size; //다음에 가리킬 인덱스가 사이즈의 값을 넘어가면 false 반환
}
public Object next() {
return elementData[nextIndex++];
}
public Object previous() {
return elementData[--nextIndex];
}
public boolean hasPrevious() {
return nextIndex > 0; //다음에 가리킬 인덱스가 0보다 작아지면 false 반환
}
public void add(Object element) {
ArrayList.this.add(nextIndex++, element);
}
public void remove() {
//※이전의 인덱스를 지우는 것이기 때문에 최소 한번 next()를 호출한 다음에 remove()를 사용해야 한다.
ArrayList.this.remove(nextIndex - 1);
nextIndex--;
}
}listIterator( ) 메서드를 호출하면 새로운 ListIterator 객체가 생성되어 자료에 접근할 수 있다.
- hasNext( ) 메서드는 다음에 가리킬 인덱스가 ArrayList 에 저장되어있는 데이터 개수를 넘어가는지 비교한다. 만약 넘어갈 경우 false 를 반환한다.
- next( ) 메서드는 호출될 때마다 인덱스가 1 씩 증가하면서 ArrayList 에 저장된 데이터들을 불러온다.
- previous( ) 와 hasPrevious( ) 는 next( ) , hasNext( ) 와 반대 역할을 하는 메서드들이다.
- add( ) 와 remove( ) 메서드는 앞쪽에서 구현한 메서드들을 재사용해서 구현했다.
Main.java
//Iterator - (next / hasNext)
ArrayList.ListIterator li = numbers.listIterator();
System.out.print("next / hasNext : ");
while(li.hasNext()) {
System.out.print(li.next() + " ");
}
//Iterator - (previous / hasPrevious)
System.out.printf("\nprevious / hasPrevious : ");
while(li.hasPrevious()) {
System.out.print(li.previous() + " ");
}
//Iterator - add
while(li.hasNext()) {
int number = (int)li.next();
if(number == 30) {
li.add(35);
}
}
System.out.print("\nadd(35)호출 후 : " + numbers);
//Iterator - remove
while(li.hasNext()) {
int number = (int)li.next();
if(number == 30) {
li.remove();
}
}
System.out.println("\nremove()호출 후 : " + numbers);main 에서 사용할 때는 while 문의 조건으로 hasNext( ) 나 hasPrevious( ) 메서드를 넣고, 반복문 안에서 next( ) 나 previous( ) 함수를 호출하면 자료의 처음부터 끝까지 순차적으로 접근할 수 있다.
이런 식으로 iterator 를 사용해서 객체에 접근하는 방식을 iterator pattern이라고 한다.
iterator pattern
- 컬렉션 구현 방법을 노출시키지 않으면서도 그 집합체 인에 들어있는 모든 항목에 접근할 수 있는 방법을 제공한다.
- 컬렉션 객체 안에 들어있는 모든 항목에 접근하는 방식이 통일되어 있으면 어떤 종류의 집합체에 대해서도 사용할 수 있는 다형적인 코드를 만들 수 있다.
- iterator pattern을 사용하면 모든 항목에 일일이 접근하는 작업을 컬렉션 객체가 아닌 반복자 객체에서 맡게 된다. 집합체의 인터페이스 및 구현이 간단해지고, 집합체에서는 반복 작업이 아닌 객체 컬렉션 관리에만 전념할 수 있다는 장점이 있다.
4. 전체 코드 & 실행 결과
앞에서 구현한 ArrayList 의 전체 코드들과 실행 결과이다.
ArrayList.java
package list.arraylist.implementation;
public class ArrayList {
//내부에서 사용할 변수와 배열을 선언, 접근제어자를 private으로 지정한다.
private int size = 0; //저장된 데이터의 개수를 세기 위한 변수,
private Object[] elementData = new Object[100]; //내부에서 사용할 배열
/*
1. 데이터 추가
1-1. 첫 번째에 데이터를 추가하는 메서드
*/
public boolean addFirst(Object element) {
return add(0, element); //구현되어 있는 add() 메서드를 사용한다.
}
//1-2. 마지막에 데이터를 추가하는 메서드
public boolean addLast(Object element) {
elementData[size] = element;
size++;
return true;
}
//1-3. 지정된 위치에 데이터를 추가하는 메서드
public boolean add(int index, Object element) {
//지정된 위치 뒤의 데이터들을 한칸씩 미는 작업
for(int i = size ; i >= index; i--) {
elementData[i + 1] = elementData[i];
}
//미는 작업이 끝나면 지정된 위치에 데이터 저장
elementData[index] = element;
size++;
return true;
}
/*
2. ArrayList를 출력하는 메서드
toString을 오버라이딩하면 객체를 원하는 형식으로 출력할 수 있다.
*/
public String toString() {
String str = "[";
//저장된 데이터를 str에 하나씩 추가함
for(int i = 0 ; i < size ; i++) {
str += elementData[i];
if(i < size - 1) {
str += ", ";
}
}
return str + "]";
}
/*
3. 데이터 삭제 메서드
3-1. 지정된 위치의 데이터 삭제
메서드를 사용하면 삭제된 데이터를 반환한다.
*/
public Object remove(int index) {
Object removed = elementData[index]; //삭제될 데이터를 removed에 임시저장한다.
//빈공간을 메꾸는 작업(뒤의 데이터들을 앞으로 당겨옴)
for(int i = index + 1 ; i <= size - 1 ; i++) { //뒤부터 당기면 전부 같아지기 때문에 앞부터 해야함
elementData[i - 1] = elementData[i];
}
//마지막 데이터 삭제
size--;
elementData[size] = null;
return removed; //삭제된 데이터를 반환
}
//3-2. 첫번째 데이터 삭제
public Object removeFirst() {
return remove(0); //이미 구현된 remove() 메서드를 사용한다.
}
//3-3. 마지막 데이터 삭제
public Object removeLast() {
return remove(size - 1); //마찬가지로 구현되어있는 remove() 메서드를 사용한다.
}
//4. 지정된 위치에 저장된 데이터를 반환하는 메서드
public Object get(int index) {
return elementData[index];
}
//5. ArrayList에 저장된 데이터의 개수를 반환하는 메서드
public int size() {
return size;
}
//6. 데이터의 인덱스를 반환하는 메서드
public int indexOf(Object element) {
for(int i = 0 ; i < size ; i++) {
if(element.equals(elementData[i])) {
return i;
}
}
return -1;
}
/*
7. Iterator
* next / hasNext
* previoushasPrevious
* add / remove
*/
public ListIterator listIterator() {
return new ListIterator(); // ListIterator 객체를 새로 생성해서 반환
}
class ListIterator{
private int nextIndex = 0; //접근할 때 사용할 인덱스변수
public boolean hasNext() {
return nextIndex < size; //다음에 가리킬 인덱스가 사이즈의 값을 넘어가면 false 반환
}
public Object next() {
return elementData[nextIndex++];
}
public Object previous() {
return elementData[--nextIndex];
}
public boolean hasPrevious() {
return nextIndex > 0; //다음에 가리킬 인덱스가 0보다 작아지면 false 반환
}
public void add(Object element) {
ArrayList.this.add(nextIndex++, element);
}
public void remove() {
//※이전의 인덱스를 지우는 것이기 때문에 최소 한번 next()를 호출한 다음에 remove()를 사용해야 한다.
ArrayList.this.remove(nextIndex - 1);
nextIndex--;
}
}
}
Main.java
package list.arraylist.implementation;
public class Main {
public static void main(String[] args) {
ArrayList numbers = new ArrayList();
// 마지막에 데이터 추가 (1-2)
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
numbers.addLast(40);
System.out.println("ArrayList : " + numbers);
//지정된 위치에 데이터 추가 (1-3)
numbers.add(1, 15);
System.out.println("add(1, 15)호출 후 : " + numbers);
//첫 번째에 데이터 추가(1-1)
numbers.addFirst(5);
System.out.println("addFirst(5)호출 후 : " + numbers);
//출력(2)
System.out.println(numbers);
//지정된 위치의 데이터 삭제(3-1)
numbers.remove(1);
System.out.println("remove(1)호출 후 : " + numbers);
//첫번째 데이터 삭제(3-2)
numbers.removeFirst();
System.out.println("removeFirst()호출 후 : " + numbers);
//마지막 데이터 삭제(3-3)
numbers.removeLast();
System.out.println("removeLast()호출 후 : " + numbers);
//지정된 위치에 저장된 데이터를 반환(4)
System.out.println("get(1) : " + numbers.get(1));
//ArrayList의 크기(5)
System.out.println("size : " + numbers.size());
//데이터의 인덱스를 반환(6)
//찾는 값이 ArrayList에 없으면 -1을 반환한다.
System.out.println("indexOf(20) : " + numbers.indexOf(20));
System.out.println("indexOf(300)(없는 값일 경우) : " + numbers.indexOf(300));
//Iterator - (next / hasNext)
ArrayList.ListIterator li = numbers.listIterator();
System.out.print("next / hasNext : ");
while(li.hasNext()) {
System.out.print(li.next() + " ");
}
//Iterator - (previous / hasPrevious)
System.out.printf("\nprevious / hasPrevious : ");
while(li.hasPrevious()) {
System.out.print(li.previous() + " ");
}
//Iterator - add
while(li.hasNext()) {
int number = (int)li.next();
if(number == 30) {
li.add(35);
}
}
System.out.print("\nadd(35)호출 후 : " + numbers);
//Iterator - remove
ArrayList.ListIterator li2 = numbers.listIterator();
while(li2.hasNext()) {
int number = (int)li2.next();
if(number == 30) {
li2.remove();
}
}
System.out.println("\nremove()호출 후 : " + numbers);
}
}
'Back end > Java 문제' 카테고리의 다른 글
| [Java] 배열회전 (0) | 2019.07.10 |
|---|---|
| [Java] 빙고게임 (0) | 2019.07.08 |
| [Java] 빈도수 구하기 (0) | 2019.07.05 |
| [Java] 배열 정렬(sort) (0) | 2019.07.03 |
| [Java] 총합, 평균, 최대, 최소 (0) | 2019.06.26 |