22. 11. 04 - [ 플러스 알파 ] 자료구조 - ArrayList 직접 구현해보기

 

 

 

-- INDEX --

 

 

1. 자료구조 - Data Structure	2. ArrayList 구현	3. 실습 코드 Check
자료(Data)의 집합 논리적으로 정의된 규칙에 의해 나열	add , doubling , get size , remove , printInfo generics	AraayList 직접 구현 구현한 메서드 사용해보기

 

 

 

---

 

 

 

1. 자료구조 - Data Structure

• 자료(Data)의 집합의 의미
• 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며
• 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것
• # 목적
• 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며,
• 잘 선택된 자료구조는 실행시간을 단축시켜주거나
• 메모리 용량의 절약을 이끌어 낼 수 있습니다.

 

 

 

 

 

# 자료(Data)의 집합의 의미

• 어떤 물건을 찾기 쉽게 정리해놓은 것
• 데이터를 조회, 삽입, 삭제하는 것을 좀 더 편하게 하려고 자료구조라는 어떤 서랍 같은 것을 활용하는 것

 

 

 

 

---

 

 

 

 

2. ArrayList 구현

• 어떤 수납 형태가 있나 알아볼 것이다.
• List, Set, Map, Stack, Queue
• 자료구조의 종류 중 하나인 List 그중에서도 ArrayList를 직접 구현해보자.

 

 

 

---

 

2-1 :  ArrayList 란?

• 배열 리스트 - Array List
• List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형 리스트
• 일반적인 배열과 같은 순차 리스트이며 인덱스로 내부의 객체를 관리한다는 점이 유사하지만
• 한번 생성되면 크기가 변하지 않는 배열과는 달리
• ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과한다면
• 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징을 가지고 있다.

 

 

 

 

---

 

 

2-2 : add 작업

• ArrayList의 값 추가하기

 

 

 

---

 

2-3 : doubling

• length 2배로 늘리기
• 저장용량이 부족하면 기존의 배열을 신규 배열로  복사
• 신규 배열의 길이는 기존 배열 길이의 2배로 늘려주기

 

 

 

# 이러면 길이만 늘어난 비어있는 배열이다. #

 

---

 

 

# 현재 가지고 있는 array를 newArr 로 변경해주는 작업도 필요하다. #

 

 

 

---

 

2-4 : get

• ArrayList 특정 인덱스의 값 출력

 

 

 

 

---

 

2-5 : size

• ArrayList의 크기를 구하기

 

---

 

 

---

 

2-6 : remove()

• ArrayList 값 삭제하기

 

---

 

 

 

---

 

 

2-7 : printInfo()

• ArrayList 모든 요소 출력

 

 

 

서치는 index 로 한 번에 찾아갈 수 있으므로

시간 복잡도가 1이구나 굉장히 빠르구나 

 

Check !

 

 

---

 

 

2-8 : 제네릭스(Generics)

• 타입의 안정성을 제공
• 타입 체크와 형 변환을 생략
• 와일드 카드 [ T  ] 활용하여 매개변수의 다형성 이용 가능

 

 

 

 

 

 

---

 

 

 

 

3. 실습 코드 Check

 

 

3-1 : AraayList 직접 구현

 

package main;

import java.util.Arrays;

public class myList {
	
	private Object[] arr;
	private int emptyIdx;
	
	
	public myList() {
		arr = new Object[1];
		emptyIdx = 0;
	}

	//add
	//비어있는 칸에다가 데이터 넣기
	//만약에 데이터 넣었는데, 빈칸이 없으면? => 사이즈 2배로 늘리기
	public void add(Object data) {
		arr[emptyIdx] = data;
		
		if(emptyIdx == arr.length-1) {
			doubling();
		}
		
		emptyIdx++;
		
	}
	
	//arr 2배로 늘리기
	private void doubling() {
		Object[] newArr = new Object[arr.length * 2];
		
		//기존배열 -> 신규배열
		for(int i=0; i<arr.length; i++) {
			newArr[i] = arr[i];
		}
		
		this.arr = newArr;
	}

	//get
	public Object get(int index) {
		return arr[index];
	}

	
	
	//size
	public int size() {
		//return arr.length; 랭스는 더블링으로 인해 아니다. 빈칸의 인덱스 해주면된다.
		return emptyIdx;
	}
	
	
	//remove
	//뒤에있는 요소들 앞으로 쭉 한칸씩 당기기
	//emptyIdx 1 감소
	public void remove(int index) {
		
		if(index < 0) {
			//throw new Exception("음수 ㄴㄴ");
		}
		
		for (int i = 0; i < emptyIdx-1; i++) {
			arr[i] = arr[i+1];
		}
		
		emptyIdx--;
	}
	
	
	//배열 모든 요소 출력
	public void printInfo() {
		
		for (int i = 0; i < emptyIdx; i++) {
			System.out.println(arr[i]);
		}
		
	}
	
	
	
}//class

 

 

---

 

 

3-2 : 구현한 메서드 사용해보기 

 

package main;

public class myListMain {

	public static void main(String[] args) {

		myList list = new myList();
		
		list.add("zero");
		list.add("one");
		list.add("two");
		list.add("three");
		list.add("four");
		list.add("five");
		System.out.println(list.size());
		
		list.remove(3);
		System.out.println(list.size());
		
		list.printInfo();
		
		Object x= list.get(1);
		System.out.println(x);
		
	}

}

 

 

 

 

 

---