[Java][자료구조]ArrayList 구현해보기

생활코딩 자료구조를 개인 공부 후 자료를 남기기 위한 목적이기에 내용 상에 오류가 있을 수 있습니다.

---

목표

• ArrayList 기본메소드 구현해보기
• ListIterator 구현하여 ArrayList에 다음 객체 반복문 실행하기
• ArryList와 ListIterator를 구현하는 ArrayLIst 클래스, 직접 제작한 ArrayList 클래스를 테스트 해볼 Main 클래스로 구성하여 실습

* 한계 : ArrayList는 정해진 크기를 넘어선 데이터를 넣을시 자동으로 데이터가 커지지만 실습에서 구현한 ArrayList는 이부분은 구현하지 못함

목차

1. ArrayList 클래스

2. Main 클래스(구현한 ArrayList 클래스 테스트)

3. Main 클래스 실행 결과

 

 

1. ArrayList 클래스

package list.arraylist.implementation;

public class ArrayList {

	/* ArrayList 구현해보기 */
	// 공부 홈페이지 https://opentutorials.org/module/1335/8715
	// 참고 http://tcpschool.com/java/java_collectionFramework_iterator
	
	/* 값이 들어간 크기 변수 */
	// 초기 변수 0 으로 셋팅
	private int size = 0;
	
	
	/* Object타입의 배열 (크기100)생성 */
	private Object[] elementData = new Object[100];
	
	
	/* add구현 */
	//해당 객체 마지막 요소 추가
	public boolean addLast(Object element) {
		
		elementData[size] = element;
		//첫번째 요소를 채웠기때문에 다음 요소를 향하게 size를 +1
		size++;
		return true;
		
	}//addLast()종료
	
	
	/* 제일 첫요소에 데이터추가 */
	public boolean addFirst(Object element) {
		//add(int index, Object element)메서드 활용
		return add(0, element);
	}
	
	
	/* 지정요소 추가 */
	public boolean add(int index, Object element) {
		//지정위치에 값을 넣기 위해서 맨 마지막요소부터 뒤로 하나씩 해당 지정 인덱스까지 값을 이동 시켜야함
		
		//ex. 10(index 0), 20(index 1), 30(index 2), 40(index 3)의 요소를 가지고 있는 ArrayList
		//객체가 있다고 가정합니다. index 1에 15의 값을 넣을려고 합니다.
		// 그렇다면 먼저 index3에 있는 40을 index4에 옮겨야합니다.
		// index2의 값 30을 index3 으로 이동
		// index1의 값 20을 index2으로 이동
		// 값을 옮기는 과정 아래와 같음
		/*
			elementData[4] = elementData[3];
			elementData[3] = elementData[2];
			elementData[2] = elementData[1];
		*/
		//위의 코드는 규칙성을 보이기 때문에 for을 사용
		for(int i = size-1;i>=index;i--) {
			elementData[i+1] = elementData[i];
		}
		
		// 다옮긴 후 새로운 값을 index1에 넣음
		elementData[index] = element;
		
		//크기가 커졌으므로 size또한 +1
		size++;
		
		return true;
	}//add()종료
	
	
	/* toString()을 통한 데이터확인 */
	public String toString() {
		
		String str = "[ ";
				
		for(int i = 0; i< size; i++) {
			str += elementData[i];
			if(i<size-1) {
				str += ",";
			}
			
		}
		
		return str + " ]";
	}//toString() 종료
	
	
	/* 지정 요소 데이터 삭제 */
	public Object remove(int index) {
		
		Object removed = elementData[index];
		
		// 중간의 요소를 삭제시 List는 빈공간을 허용하지 않기대문에 빈공간을 매우기 위해 요소가 한칸씩 앞으로 이동합니다.
		// 실질적으로는 없앨려고하는 index에 있는값을 해당 index뒤의 값으로 덮어씌움으로서 제거하고자 하는 값을 없앱니다.
		//ex. 10(index 0), 20(index 1), 30(index 2), 40(index 3)의 요소를 가지고 있는 ArrayList
		//객체가 있다고 가정합니다. index 1의 값을 제거하는 것을 목표로합니다.
		// 그렇다면 먼저 index2에 있는 30을 index1에 옮겨 덮어 씌웁니다.
		// index3의 값 30을 index2 으로 이동
		// 값을 옮기는 과정 아래와 같음
		/*
			elementData[1] = elementData[2];
			elementData[2] = elementData[3];
		*/
		// 위의 코드를 for을 통해 구현
		for(int i = index + 1; i <= size -1; i++) {
			elementData[i-1] = elementData[i];
		}
		
		//한요소가 없어졋기 때문에 size -1
		size--;
		
		//맨마지막 index는 아직 값이 남아 있으므로 null값을 저장
		elementData[size] = null;
		
		//삭제된 데이터를 반호나
		return removed;
	}
	
	
	/* 첫 요소 삭제 */
	public Object removeFirst() {
		//remove(int index)를 활용
		return remove(0);
	}
	
	
	/* 마지막 요소 삭제 */
	public Object removeLast() {
		//remove(int index)를 활용
		//맨마지막 요소 index는 size-1 입니다.따라서 size-1을 활용합니다.
		return remove(size-1);
	}

	
	/* 지정 index 요소 데이터 가져오기 */
	public Object get(int index) {
		return elementData[index];
	}
	
	
	/* size 가져오기 */
	public int size() {
		return size;
	}
	
	
	/* 데이터의 index 검색 */
	// 데이터가 존재시 해당 index반환
	// 데이터가 존재하지 않을 시 -1반환
	public int indexOf(Object o) {
		//객체 전체를 size 크기만큼 for을 도렬 탐색
		for(int i = 0; i < size; i++) {
			//찾고자 하는 데이터(o)와 해당 index의 데이터(elementData[i])가 일치시
			if(o.equals(elementData[i])) {
				//해당 index 값을 반환
				return i;
			}
		}
		
		// for을 돌려 탐색을 하였지만 일치하는 데이터를 찾지 못했을시 -1 int값을 반환
		return -1;
	}
	
	
	/* ArrayList 객체 Iterator객체로 변환 */
	public ListIterator listIterator() {
		return new ListIterator();
	}
	
	/* ListIterator Class */
	public class ListIterator{
		
		//Index 변수 0부터 시작
		private int nextIndex = 0;
		
		
		//다음 요소가 존재할 시에 true를 반환, 없을시 false를 반환
		//현재의 index는 변수 nextIndex
		public boolean hasNext() {
			return nextIndex < size();
		}
		
		
		//다음 요소 데이터를 반환
		public Object next(){
			//nextIndex 자체가 다음의 Index기 대문에 해당 Index를 elementData[index]를 사용하여 데이터를 반환 후
			// index를 +1 진행
			return elementData[nextIndex++];
		}
		
		
		//앞의 요소가 존재할 시 true를 반환
		//현재의 index는 변수 nextIndex
		public boolean hasPrevious() {
			return nextIndex>0;
		}
		
		
		//이전 요소 데이터를 반환
		public Object previous() {
			//앞의 요소데이터를 반환해야하기대문에 index에 먼저 -1을 해준 후 elementData[index]를 통해 데이터 반환
			return elementData[--nextIndex];
		}
		
		
		// next() 혹은 previous()에서 반환된 가장 마지막 요소  다음 요소에 데이터를 추가
		// 실제 ListIterator에서의 remove는 next(), previous() 둘다 가능한 메소드
		public void add(Object element) {
			//ArrayList에서 정의한 add(int index, Object element)를 사용
			//다음 Index인 nextIndex를 사용 후 +1을함
			ArrayList.this.add(nextIndex++, element);
		}
		
		
		// next() 에서 반환된 가장 마지막 요소를 제거 
		// 실제 ListIterator에서의 remove는 next(), previous() 둘다 가능한 메소드
		public void remove() {
			// next(), 메서드 실행 후 nextIndex가 다음 요소의 Index기 때문에 
			// 현재의 Index를 표현하기 위해 -1을 해줌
			ArrayList.this.remove(nextIndex-1);
			
			//다음의 index또한 한칸 앞으로 당겨졌기때문에 -1을 진행해줌
			// 예를들어보면 0, 1, 2, 3, 4의 index가 있습니다.
			// 현재의 ListIterator의 next()메소드를 통해 index1의 값이 반환이 된경우 nextIndex는 2일것입니다.
			// (nextIndex는 다음의 Index를 가리키는 변수 이기 때문입니다.)
			// 여기서 remove()를 사용하게되면 index1에 저장되어 있던 데이터가 없어지면서 index2의 값이 저장됩니다.
			// 다음의 Index값이 idnex2였지만 index1로 당겨져왔기 때문에 idnex또한 앞으로 이동하기 위해서 -1을 해줍니다.
			// 만약 이렇게 해주지 않을 경우 next()메소드를 진행시 index1로 당겨져온 값은 분명히 존재함에도 반환이 되지 못하기 때문입니다.
			nextIndex--;
		}
	}
	
}

 

2. Main 클래스

package list.arraylist.implementation;

import list.arraylist.implementation.ArrayList.ListIterator;

public class Main {

	/* 구현한 ArrayList클래스 사용해보기 */
	/*한계점 : 요소가 늘어나면 해당 배열의 크기가 늘어난 것은 구현하지 못함*/
	public static void main(String[] args) {
		
		/* ArrayList를 개체화 시켜 ArrrayList numbers 참조변수에 저장 */
		ArrayList numbers = new ArrayList();
		
		// 10, 20, 30, 40 차례로 데이터 집어넣기
		//addLast(Object element)
		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		numbers.addLast(40);
		System.out.println("* 10,20,30,40 데이터 집어넣기");
		System.out.println(numbers);
		System.out.println();

		
		// index1에 15넣기
		// add(int index, Object element)
		System.out.println("* index1에 15값 넣기");
		System.out.println("기존 numbers 객체 : " + numbers);
		numbers.add(1, 15);
		System.out.println("추가 이후 numbers 객체 : " + numbers);
		System.out.println();
		
		// 제일 첫 요소에 1 값 넣기
		// addFirst(Object element)
		System.out.println("* 첫 요소(index0)에 15값 넣기");
		System.out.println("기존 numbers 객체 : " + numbers);
		numbers.addFirst(1);
		System.out.println("추가 후 number 객체 : " + numbers);
		System.out.println();
		
		
		// index 3의 데이터 삭제
		// remove(int index)
		System.out.println("* index 3의 데이터 삭제");
		System.out.println("기존 numbers 객체 : " + numbers);
		numbers.remove(3);
		System.out.println("적용 후 number 객체 : " + numbers);
		System.out.println();
		
		
		// 맨 앞의 요소(index 0) 데이터 삭제
		// removeFirst()
		System.out.println("* 맨 앞의 요소(index 0) 데이터 삭제");
		System.out.println("기존 numbers 객체 : " + numbers);
		numbers.removeFirst();
		System.out.println("적용 후 number 객체 : " + numbers);
		System.out.println();
		
		
		// 마지막 요소 데이터 삭제
		// removeLast()
		System.out.println("* 마지막 요소 데이터 삭제");
		System.out.println("기존 numbers 객체 : " + numbers);
		numbers.removeLast();
		System.out.println("적용 후 number 객체 : " + numbers);
		System.out.println();
		
		
		// index 1의 데이터 가져오기
		// get(int index)
		System.out.println("* index 1의 데이터 가져오기");
		System.out.println("numbers 객체 : " + numbers);
		System.out.println("index1 데이터 : " + numbers.get(1));
		System.out.println();
		
		
		// 현재 size(크가, 길이) 가져오기
		// size()
		System.out.println("* 현재 size(크가, 길이) 가져오기");
		System.out.println("numbers 객체 : " + numbers);
		System.out.println(" size : " + numbers.size());
		System.out.println();
		
		// 데이터 15(존재 o), 60검색(존재 x) (일치하는데이터 찾을 시 해당 index 반환/ 없을시 -1 반환)
		// indexOf(Object o)
		System.out.println("* 데이터 15 검색");
		System.out.println("numbers 객체 : " + numbers);
		System.out.println(" 15 데이터 index(-1일 경우 값 없음) : " + numbers.indexOf(15));
		System.out.println("------------------------------------");
		System.out.println("* 데이터 60 검색");
		System.out.println("numbers 객체 : " + numbers);
		System.out.println(" 60 데이터 index(-1일 경우 값 없음) : " + numbers.indexOf(60));
		System.out.println();
		
		
		// for을 통해 반복
		System.out.println("* for을 통한 반복");
		System.out.println("numbers 객체 : " + numbers);
		for(int i = 0; i < numbers.size(); i++) {
			System.out.println("index" + i + " : " + numbers.get(i));
		}
		System.out.println();
		
		
		
		
		
		
		/* Iterator을 통한 반복 */
		// 명확히 테스트 하기위해 새로운 ArrayList 객체 선언 후 5개의 값(10, 20, 30, 40, 50)을 순서대로 넣음
		ArrayList numbers2 = new ArrayList();
		numbers2.addLast(10);
		numbers2.addLast(20);
		numbers2.addLast(30);
		numbers2.addLast(40);
		numbers2.addLast(50);
		
		System.out.println("* Iterator을 통한 반복");
		System.out.println("numbers 객체 : " + numbers2);
		
		// ArrayList를 ListIterator객체로 변환
		ListIterator li = numbers2.listIterator();
		
		while(li.hasNext()) {
			int i = 0;
			System.out.println(li.next());
		}
		System.out.println();
		
		
		
		
		
		/* ListIterator add()메소드를 테스트하기위해 새로운 ArrayList와 ListIterator 생성 */
		// 명확히 테스트 하기위해 새로운 ArrayList 객체 선언 후 5개의 값(10, 20, 30, 40, 50)을 순서대로 넣음
		ArrayList numbers3 = new ArrayList();
		numbers3.addLast(10);
		numbers3.addLast(20);
		numbers3.addLast(30);
		numbers3.addLast(40);
		numbers3.addLast(50);
		
		ListIterator li2 = numbers3.listIterator();
		
		
		// 요소중 30데이터 다음 요소에 35데이터를 추가
		System.out.println("* 요소중 30데이터 다음 요소에 35데이터를 추가");
		System.out.println("numbers 객체 : " + numbers3);
		while(li2.hasNext()) {
			
			//next() 반환값이 Object 타입이기때문에 int로 형변환 후 int 변수에 저장
			int value = (int)li2.next();
			if(value == 30) {
				li2.add(35);
			}
		}
		System.out.println("변경 후 numbers 객체 : " + numbers3);
		
		
		
		
		/* ListIterator remove()메소드를 테스트하기위해 새로운 ArrayList와 ListIterator 생성 */
		// 명확히 테스트 하기위해 새로운 ArrayList 객체 선언 후 5개의 값(10, 20, 30, 40, 50)을 순서대로 넣음
		ArrayList numbers4 = new ArrayList();
		numbers4.addLast(10);
		numbers4.addLast(20);
		numbers4.addLast(30);
		numbers4.addLast(40);
		numbers4.addLast(50);
		
		ListIterator li3 = numbers4.listIterator();
		
		
		// 요소중 30데이터 삭제
		System.out.println("* 요소중 30데이터 삭제");
		System.out.println("numbers 객체 : " + numbers4);
		while(li3.hasNext()) {
			
			//next() 반환값이 Object 타입이기때문에 int로 형변환 후 int 변수에 저장
			int value = (int)li3.next();
			if(value == 30) {
				li3.remove();
			}
		}
		System.out.println("변경 후 numbers 객체 : " + numbers4);
		
		
		
	}

}

 

3. Main 클래스 실행결과

* 10,20,30,40 데이터 집어넣기
[ 10,20,30,40 ]

* index1에 15값 넣기
기존 numbers 객체 : [ 10,20,30,40 ]
추가 이후 numbers 객체 : [ 10,15,20,30,40 ]

* 첫 요소(index0)에 15값 넣기
기존 numbers 객체 : [ 10,15,20,30,40 ]
추가 후 number 객체 : [ 1,10,15,20,30,40 ]

* index 3의 데이터 삭제
기존 numbers 객체 : [ 1,10,15,20,30,40 ]
적용 후 number 객체 : [ 1,10,15,30,40 ]

* 맨 앞의 요소(index 0) 데이터 삭제
기존 numbers 객체 : [ 1,10,15,30,40 ]
적용 후 number 객체 : [ 10,15,30,40 ]

* 마지막 요소 데이터 삭제
기존 numbers 객체 : [ 10,15,30,40 ]
적용 후 number 객체 : [ 10,15,30 ]

* index 1의 데이터 가져오기
numbers 객체 : [ 10,15,30 ]
index1 데이터 : 15

* 현재 size(크가, 길이) 가져오기
numbers 객체 : [ 10,15,30 ]
 size : 3

* 데이터 15 검색
numbers 객체 : [ 10,15,30 ]
 15 데이터 index(-1일 경우 값 없음) : 1
------------------------------------
* 데이터 60 검색
numbers 객체 : [ 10,15,30 ]
 60 데이터 index(-1일 경우 값 없음) : -1

* for을 통한 반복
numbers 객체 : [ 10,15,30 ]
index0 : 10
index1 : 15
index2 : 30

* Iterator을 통한 반복
numbers 객체 : [ 10,20,30,40,50 ]
10
20
30
40
50

* 요소중 30데이터 다음 요소에 35데이터를 추가
numbers 객체 : [ 10,20,30,40,50 ]
변경 후 numbers 객체 : [ 10,20,30,35,40,50 ]
* 요소중 30데이터 삭제
numbers 객체 : [ 10,20,30,40,50 ]
변경 후 numbers 객체 : [ 10,20,40,50 ]

 

Reference

• https://opentutorials.org/module/1335/8715

 

 

Date

• 2020.05.07 작성