책에는 정리되어있지 않지만, 컬렉션 프레임워크에 들어가기 전에 알아두면 좋을 내용.
목차
<자료 구조(data structure)>
프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론, 혹은 과목. 컴퓨터과학에서 알고리즘과 함께 가장 중요한 기초이론.
<배열(array)>
같은 형의 데이터 타입을 메모리에 저장하는 선형적 자료구조.
논리적 구조와 물리적 구조가 동일하다.
배열의 특징
- fixed length : 배열의 길이가 정해져 있음.
- 인덱스(index)연산 : 배열의 길이가 정해져 있기 때문에 요소를 찾기 수월함.
- in/out, insert/delete가 n개(요소의 개수)에 종속 : 연산의 횟수가 n개(요소의 개수)에 종속되어있다.
JDK
- ArrayList : 알고리즘에 최적화
- Vector : 자바 1.2부터 등장. 동기화를 지원,
동기화를 위해 싱크로나이즈드가 지원됨.
단일 쓰레드일 경우 추천되지 않음.
<링크드 리스트(linked list)>
배열의 단점을 보완한 자료 구조
여러 개의 노드(node)가 연결된 구조
링크드 리스트의 구조
하나의 노드(node)는 데이터와 링크로 구성됨
- 데이터(data) : 배열의 요소가 들어감
- 링크(link) : 다음 배열 요소를 가리킴
배열과 비교
- 물리적 위치와 논리적인 위치가 같지 않다.
물리적 위치는 떨어져있지만, 논리적으로는 바로 옆에 연결됨. - insert/delete가 용이하다.
중간에 요소가 바뀔때는 이전의 노드와 연결하고, 다음 노드와 연결하면 됨.
<스택(stack)>
선형 자료구조. (그림으로는 주로 수직으로 쌓는 모양으로 표현함)
LIFO (Last In First Out) : 나중에 들어온 것이 먼저 나가는 구조. (후입선출)
가장 나중에 들어온 것을 Top이라고 칭함.
집어 넣을 때 push()
꺼낼때 pop()과 peek()이 있음
pop() : 꺼내고 요소를 제거.
peek() : top의 요소를 반환 (스택에서 제거 X)
항상 top위치에 push()와 pop()이 이루어진다.
ArrayList
remove(size() - 1) 맨 뒤에서 꺼내는 것
활용
가장 최근 정보를 참조할 때,
바둑에서 무르기 등
<큐(queue)>
선형 자료구조 (그림으로는 주로 가로로 정렬해놓은 모양)
FIFO(First In First Out) : 먼저 들어온 것이 먼저 나간다 (선입선출)
자료는 무조건 뒤에서 들어감.
가장 앞을 front, 가장 뒤를 rear라고 칭함.
뒤에서 집어 넣을 때 enqueue() / 앞에서 꺼낼 때 dequeue()
중간에 요소가 비어지는 경우도 있기 때문에 circular queue를 쓰기도 함.
ArrayList로 Stack이나 Queue의 자료 구조를 구현하기도 함.
add(),remove()
remove(0)이면 맨 앞에서 꺼내는 것 /
활용
주로 대기열.
<트리(tree)>
(BST: Binary Search Tree)
자료의 검색을 위한 자료 구조
계층 자료 구조
BST: Binary Search Tree : 이진 탐색 트리
노드로 구성되어 있음.
노드에 들어가는 값을 key값이라고 칭함.
위에 위치한 노드를 parent노드, 아래에 위치한 노드를 child노드.
하나의 parent노드를 기준으로 왼쪽의 child를 left child, 오른쪽의 child를 right child로 부름
left child는 parent보다 작은 값.
right child는 parent보다 큰 값.
BST는 key값의 중복이 허용되지 않음.
트리의 구조
트리는 가장 상위 노드를 기준으로 좌, 우의 Balance가 중요한데, 이를 위해 고안된 Tree는 두 가지.
AVL Tree
Red-Black Tree : 자바에서 쓰이는 트리 형식.
트리의 정렬(Sorting)
트리를 구성하는 노드를 하나씩 순회하면서(traversal) 차례로 정렬(Sorting)한다.
트리순회
in-order traversal : 오름차순 정렬 (left child - parent - right child 순으로 서치함.)
pre-order traversal :
post-order traversal :
JDK
Treeset, TreeMap(Red-Black Tree)
<해싱(hashing)>
산술 연산을 이용한 검색 방식
평균 시간 복잡도 = 자료가 N개 일때, 0(1)
자료의 개수에 종속되지 않는다는 의미
탐색 속도가 굉장히 빠름.
해싱함수가 얼마나 잘 만들어졌느냐에 따라서 충돌(collision)이 덜 발생할 수 있고, 알고리즘의 수행속도에 직결되어있음.
index = h(key)
JDK
HashMap, HashSet