생활코딩 DataStructure -1

1. DataStructure의 필요성

1-1 현실을 프로그래밍적으로 표현하는 것 

 ex) 현실에서의 Tree는 뿌리에서부터 가지가 뻗어나가는 구조, 이러한 현실세계의 Tree구조를 프로그래밍적으로

 조직도나 디렉터리로 표현할 수 있다. 

 ex2) Set은 집합을 나타내는데, set구조를 통하여 프로그래밍적으로 집합간(영어스터디, 프로그래밍스터디 등) 교집합, 합집합을 구할 수 있다.

 - 이러한 구조들을 공부하고, 프로그래머들이 짜놓은 데이터구조를 익히면서 나만의 데이터구조를 만들 수 있다. 

 

 1-2 큰 데이터를 효율적으로 관리할 수 있다. 

 ex) 1권의 책을 관리하는 것은 쉽다, 하지만 100권 이상일 경우, 정리를 하지 않으면 원하는 책을 찾는 건 쉽지 않다.

 따라서 책을 다양한 기준으로 정렬하면 원하는 책을 손쉽게 찾을 수 있다. 프로그래밍에서도 데이터를 어떻게 정리하느냐가 프로그래밍의 효율성을 좌우한다.

 ex2) 책 -> 책장 -> 도서관 /  파일 -> 데이터베이스

 

2. 배열 (Array)

 - 많은 DataStructure들이 Array를 부품으로 사용.

 - 데이터가 많을 때 이용 

 - 여러데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 DataStructure (반복문 while, for, iterator등과 자주 사용)

 - index(색인)이 data를 식별함. (저장하거나 불러오는 등)

 

2-1 배열의 생성 및 초기화

 - []: 단순한 datatype이 아닌, datatype을 담은 배열임을 나타냄
 - new: 객체를 생성할때 사용하는 키워드, 즉, 배열은 Java에서 객체임을 나타냄.

 - 배열을 선언하는 것과, 값을 넣는 초기화를 동시에 할 수도 있음.

 

int[] arr = new int[4];


int[] arr = {10, 20, 30, 40};
//int[] arr = new int[]{10, 20, 30, 40}; 처럼 쓸 수 도 있음.

 

 

2-2 배열의 값 가져오기

 - 값을 지정하지 않은 number1[3]값을 불러오려고 하면, java가 설정한 defalut값을 리턴한다.
 - 숫자일 경우는 0. 객체일 경우는 null등

int[] numbers1 = new int[4];

numbers1[0] = 1;
numbers1[1] = 1;
numbers1[2] = 1;

System.out.println(numbers1[3]); // 0

2-3 .length 배열의 길이 가져오기(배열의 크기를 정수로 리턴)

 - we can obtain the size of the array.

 - 자바의 배열의 길이는, value가아니라 설정한 크기를 정수로 리턴한다.

 - 따라서 배열의 size가 아니라 초기화한 값의 개수를 알고 싶으면 직접 알고리즘을 짜야 한다. 

 

public class practice {
	public static void main(String[] args) {
		
		int[] arr = new int[4];
		
		arr[0] = 1;
		arr[1] = 1;
		arr[2] = 1;
		
		System.out.println(arr.length); // 4
	}
}

 

2-4 Iteration 반복 

 - 컴퓨터를 사용하는 이유 -> 단순작업을 피하기 위해 

 - 배열을 더 효율적으로 사용하기 위해 반복문과 함께 사용

 

1) while문을 통한 배열의 element 출력 

 - while문을 통한 출력의 단점은 반복문을 움직이는 중요한 변수 i가 응집돼있지 않고 흩어져 있다는 것.

public class practice {
	public static void main(String[] args) {
		
		int[] numbers1 = {1, 2, 3, 4};
		
		int i = 0;
		while (i < numbers1.length) {
			
			System.out.println(numbers1[i]); //while문안의 코드가 길어지면 i끼리 멀어짐 
			
			i = i + 1;
		}
		
		
	}
}

 

2) for문

 - while문의 단점을 보완하기 위해 for문 사용

 - 반복문을 움직이는 중요 변수들이 for () 형식으로 괄호 안에 응집돼있음.

 

public class practice {
	public static void main(String[] args) {
		
		int[] numbers1 = {1, 2, 3, 4};
		
		
		for (int i = 0; i < numbers1.length; i++) { // 변수 i의 코드들이 응집
			
			System.out.println(numbers1[i]);
		}
		
		
	}
}

 

2-5 배열의 장점이자 단점

 - 크기가 확정되어 있다. 

 - 기능이 없다. (추가, 삭제, 이동 등)

 - 위의 두 특징은 장점이자 단점이 될 수 있다.

 - 장점: 좋은 부품이 될 수 있다.

 - 좋은 부품 = 작고, 가볍고, 단순한 것 즉, 배열의 크기가 정해져 있기 떄문에 메모리를 효율적으로 사용할 수 있고, 다른 데이터 구조에서 부품으로 사용하며 프로그래밍을 효율적으로 할 수 있다. 

 

3. List 

 - 데이터가 순서대로 저장된다, 중복을 허용한다.

 

3-1 Array vs List 

 - 공통점: 둘 다 순서대로 저장할 수 있고 중복을 허용함.

 - 차이점: 1)List의 기능이 Array보다 많다.  2)List는 데이터를 direct로 접근할 수 있게하는 '주소'를 중시하고 Arrray를 주변 위치를 확인하여 데이터를 찾기 때문에 데이터끼리의 '순서'를 중시한다.

 

1) element추가시의 차이점.

 - 배열의 경우 새로운 element를 기존의 위치에 넣는 행위는 덮어쓰는 행위와 비슷하다 

int[] numbers1 = {1, 2, 3, 4};

numbers1[3] = 5; // numbers1[3]의 값을 4 -> 5 (덮어씌워짐)

numbers1 = {1, 2, 3, 5};

- List의 경우 numbers1[3]에 원하는 값을 넣고, 기존 index 3번에 해당하는 값은 뒤로 옮겨 index를 4번으로 변경한다

 (List 코드 삽입하기)

 

 

 

2) element 삭제시의 차이점

 - Array는 삭제하고자하는 index에 있는 요소를 비우고(빈값으로 놔둔다), 자리는 그대로 유지한다.

 

 - List는 요소와, 주소도 삭제하고 그 뒤에 다른 요소가 있다면 앞으로 당겨 이전 주소로 변경한다 (마지막 요소이면 그냥 삭제)

 (List 코드 삽입하기)

 

 - 삭제의 과정에서 List는 element를 삭제하기 때문에, 반복문과 같이 사용할 때, 비어있는 요소를 Check하지 않아도 됨. Array의 경우에는 element를 삭제하지 않고 값만 비워놓기 때문에 반복문을 통해 element를 순회하는 과정에서 값이 비어있는 공간을 Check해야 하고, 그만큼 메모리를 더 차지함.

 - Array는 삭제시 다른 element의 index값이 바뀌지 않기 때문에, index가 유일무이한 식별자로서의 기능을 충실히 이행함. (index 3번의 요소가 사라져도 다음 요소의 인덱스는 여전히 index 4) 

 

3-2 List의 기능 

 - DataStructure의 타입을 결정하는 것은 해당 구조의 동작방법(operation)임.

 - List의 기능 : 1)처음, 끝, 중간에 엘리먼트를 추가 또는 삭제함. 2)리스트에 데이터가 있는지 체크 3)리스트의 모든 데이터에 접근할 수 있음 (추가하면 한칸 밀려나고, 삭제하면 뒤에서 채운다!)

 - C: 기본적으로 리스트 지원안함, JavaScript: 배열이 리스트, Python: 리스트가 배열 (최근의 언어는 리스트를 기본적으로 지원) 

 - Java: 배열과 리스트를 둘다 지원하며 엄격히 구분한다. (각 장점을 둘다 활용하기 위해) , 리스트를 2개 지원한다 LinkedList, ArrayList 

 

1) List와 Array의 생성 비교 

import java.util.ArrayList;

public class practice {
	public static void main(String[] args) {
		
		int[] numbers1 = {1, 2, 3, 4};
		
		ArrayList numbers = new ArrayList();
		
		numbers.add(10);
		numbers.add(20);
		numbers.add(30);
		numbers.add(40);
		numbers.add(50);
		numbers.remove(3);
		

		
	}

 2) LinkedList, ArrayList 

 - 각각의 장점이 다르다 (trade off가 존재) 

 - 구현하고자하는 프로그램에 맞추어 직접 효율적인 데이터 구조를 선택할 수 있다. 

 - Java는 List도 나뉘어져있다.. 즉, 알고 있어야 할 데이터 구조가 많다. 하지만 그만큼 자유도가 높다.

4. Array List

 - List를 만들 때, 내부적으로 Array를 사용함 

 - 데이터의 추가와 삭제시 data를 하나씩 당기거나 밀어야 하기 때문에 시간이 많이 걸림

 

4-1 데이터의 추가

 - 추가되는 데이터가 자리를 차지하면, 한칸씩 데이터가 뒤로 밀린다.

 

 

4-2 데이터의 삭제

 - 삭제된 데이터의 자리를 뒤에서 한싹 앞으로 당긴다.

 

 

4-3 데이터 가져오기 (Get)

 - 내부적으로는 배열을 사용하여 인덱스가 존재하기 때문에 데이터를 가져오는 시간이 빠름.

 

1) Size 데이터 크기 

 - ArrayList는 내부적으로 size라고하는 변수를 유지하고 있음. 따라서 데이터를 추가하면 size의 값을 1 올리고 삭제하면 1 내림으로서 변수를 변경하고 크기를 나타냄.

 

4-4 Java에서 ArrayList 사용법

 - 컬렉션프레임워크라는 자체적인 라이브러리안에 ArrayList데이터 스트럭쳐를 기본적으로 내장하고 있음.

 

1) ArrayList의 선언과 데이터의 추가

 - ArrayList를 사용하기 위해서는 import java.util.ArrayList;를 import하여 외부라이브러리의 데이터를 불러와야함.

 - 데이터의 추가는 .add(), 원하는 위치에 데이터를 추가는 .add(index, 값)

package arrayList;

import java.util.ArrayList;

public class Main {
	
	public static void main(String[] args) {
		
		ArrayList<Integer> numbers = new ArrayList<>();
		
		numbers.add(10);
		numbers.add(20);
		numbers.add(30);
		numbers.add(40);
		System.out.println("add(값)");
		System.out.println(numbers);
		
		numbers.add(1, 50);
		System.out.println("\nadd(인덱스, 값)");
		System.out.println(numbers);
	}

}

 

2) get(), remove(), .size()

 - 데이터를 가져오고, 제거하고, 배열의 size를 반환하는 함수들

 

		numbers.remove(2);
		System.out.println("\nremove(인덱스)");
		System.out.println(numbers);
		
		System.out.println("\nget(인덱스)");
		System.out.println(numbers.get(2)); //값을 참조할 뿐 , 배열안의 값을 변화시키진 않음
		
		System.out.println("\nsize()");
		System.out.println(numbers.size());

 

 

* 추가 자료

 - ArrayList는 내부적으로 배열을 사용하지만, (크기에 제한되지 않고)계속해서 element를 추가할 수 있는 이유 

https://yeonwooya.tistory.com/14  

 -> ArrayList를 통해 element를 추가 할 때, ArrayList가 담을 수 있는 최대 용량인 capacity보다 element의 개수 size가 클 경우 내부적으로 grow()메서드를 통해 capacity를 늘려주기 때문에, Array와는 다르게 자료의 추가가 자유롭다. 

 -> size = 배열에 담긴 element의 개수, capacity = 선언된 배열의 크기 (총 담을 수 있는 element의 개수)

 - > Java에서 ArrayList를 생성하면 default 크기는 10으로 선언된다.