[JAVA] 기초문법 - 컬렉션 프레임워크

배열은 fixed-length로 시작함.

인덱스 연산이 가능하다. 시간복잡도 O(1)

첫번째 인덱스는 0부터시작한다.

물리적 위치와 논리적 위치가 같다.

중간에 비어있을 수 없다.(중간 삽입과 삭제할때 연산이 많다. 한칸씩 땡기거나 밀어야하기 때문) 시간복잡도 O(n)

크기가 다 채워져있고 추가하려면 더 큰 배열을 선언하고 기존배열을 복사하는 방식을 사용한다.

자바의 ArrayList가 배열을 구현한 것이다.

링크드리스트

노드 단위로 연결되어 있는 구조이다.

하나의 노드는 값과 다음 노드의 주소 2가지가 저장된다.(가리킬 것이 없으면 null저장)

fixed length가 아니다.

물리적 위치와 논리적 위치가 다르다. 논리적으로는 붙어 있지만 논리적으로는 떨어져 있다.

배열의 단점이었던 중간삽입 중간 삭제에서 연산이 많아지는 것을 보완 가능하다.(해당 경우에 배열보다 빠르다.)

인덱스 연산이 안되어 중간의 값을 찾을때 앞에서부터 순차접근 해야한다.(물리적 위치가 다르기 때문에)

자바 JDK에 LinkedList로 구현되어 있다.

스텍 and 큐

선형 자료구조이다.

배열과 링크드리스트 두 방식으로 구현 할 수 있다.

스텍

Last In first out이다.(가장 나중에 들어온 자료가 가장 먼저 나간다.)

데이터의 입출력은 항상 TOP에서 일어난다.

데이터를 집어 넣을때 push() 데이터를 뺄때 pop()이라 한다.

peek()연산은 스텍에서 꺼내지 않고 마지막 값만 반환하는 역할

자바 JDK에 stack으로 구현되어 있다.

큐

front부분과 Rear부분이 있다. Rear에서 들어가 front로 빠져 나간다. 데이터를 집어 넣을때 Enqueue 데이터를 뺄때 Dequeue라 한다.

현실세계에서 선착순과 유사한 개념이다.

First in First out(먼저 들어온 데이터가 먼저 나간다.)

이진 Tree

자식 노드가 최대 2개인 트리이다.

왼쪽 자식과 오른쪽 자식이 있다.

왼쪽 자식은 부모의 값보다 항상 작고, 오른쪽 자식은 부모 자식보다 항상 크다.

검색을 할때 유용하게 사용된다.

중복을 허용하지 않는다.

순서대로 값을 넣었을대 만들어진 트리 모양이다.

값을 찾을때 시간 복잡도는 log_2(n) 이다.

정렬 방법(트리 탐색 순서)에는

in-order(오름차순 정렬), 트리가 좌우 뒤집혔으면(내림차순 정렬)

pre-order

postorder

가 있다.

자바 JDK에는 Treeset, TreeMap(Red-Black Tree)로 구현되어 있다.

해싱(검색을 위한 자료구조)

해시함수에 key를 넣어서 나온 위치(index)에 값을 저장

해싱함수에 따라 충돌이 일어날 수 있다.

충돌 발생시 여러가지 대응법이 존재한다.

값을 넣고 뺴는 속도가 매우 빠르다. 자료가 N개 일때,시간복잡도 O(1)

JDK에 HashMAP과 HashSet으로 구현되어있다.