[자바/ 자료구조] 컬렉션 프레임워크 공부 전, 자료구조를 간단히 정리해보자!

컬렉션 프레임워크 공부 전 자료구조 개념 정리의 필요성을 느꼈다!

지금부터 간단하고 확실하게 개념을 짚고 넘어가보자!

배열 Array

 

같은 형의 데이터 타입을 메모리에 저장하는 선형적 자료구조

논리적 구조와 물리적 구조가 동일하다.

-> 배열은 Fixed-length이다. (고정된 길이) 

-> 인덱스 연산이 가능하다. 데이터의 크기 만큼의 오프셋으로 요소의 위치 계산이 가능하다. 논리적, 물리적 주소가 동일하니까 계산 가능!

-> Insert / Delete 에 필요한 연산이 배열 전체 요소의 개수에 의존한다. (n개에 Dependent 하다.) / O(n)

-> ArrayList / Vector

 

 

연결 리스트 Linked List 

 

데이터와 링크로 구성되어 있다.

-> IO가 많이 일어나는 경우 사용하면 용이하다.

-> 배열의 요소의 개수가 유동적일때 사용하면 용이하다.

 

 

스택 stack

"쌓다."는 의미

선형 자료구조

나중에 들어간 것이 먼저 나온다 = 후입선출 (LIFO) Last In First Out

들어가는 것: PUSH

꺼내는 것: POP

스택의 맨 위에 있는 원소를 반환하는 것: PEEK - 제거하는 것이 아님(일종의 GET())

 

 

큐

대기열

먼저 들어간 것이 먼저 나온다 = 선입선출 (FIFO) First In First Out

 

트리

BST | Binary Search Tree 이진탐색트리의 특성

 

유일한 키 값을 가진다.

루트노드의 키 값을 기준으로 한다.

왼쪽 서브트리 키 값 < 루트 노드의 키 값

오른쪽 서브트리 키 값 > 루트 노드의 키 값

 

 

해싱 Hashing

검색을 위한 알고리즘

평균 시간 복잡도 = 자료가 N개 일 때, O(1) <- 자료가 몇 개인지는 상과 없음. 해시 함수(산술연산)를 통해 값을 구할 수 있다.

 

 

검색 키 (KEY)

 

해싱 함수(Hashing Function)

 

검색 자료의 주소(Addrerss)

 

해시테이블