자바와 자료구조 (선형자료구조, 비선형자료구조, 매핑형자료구)

자료구조(Data Structure)?

- 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들

- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨

- 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음

- 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해 중요

 

선형자료구조 (앞의 요소와 뒤의 요소의 관계가1:1의 관계)

종류- 배열, 링크드리스트, 스택, 큐

 

1. 배열 (Array)

: 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음

메모리 상에 중간이 빌 수 없다.(삽입시 밀어내고, 삭제시 당겨낸다)

 

2. 링크드리스트(LinkedList)

: 선형으로 자료를 관리, 자료가 추가될 때 마다 메모리를 항당 받고, 자료는 링크로 연결된다. 자료의 물리적위치와 논리적 위치가 다를 수 있다. 

 

배열과 링크드 리스트의 차이

- 배열은 처음에 쓰기전에 물리적으로 몇개를 쓰겠다고 공간을 할당 받고 사용

- 링크드 리스트의 경우는 노드가 필요할 때 메모리를 할당(allocation) 받아서 이전 노드에 다음노드에 대한 주소를 가리킴(포인터,참조변수에 대한 주소)

- 추가 삭제시에는 링크드 리스트가 수행 속도가 빠름. 링크드 리스트 수행시: O(1), 배열의 경우 : O(N)

- 조회 시 배열의 경우 index를 통해 찾아갈 수 있다. O(1), 링크드 리스트의 경우 일일이 찾아가야하기 때문에 O(N)

 

3. 스택(stack) : 함수의 메모리가 스택메모리(로컬변수,메서드에쓰는 메모리들)를 사용

ex) 무르기(장기,체스), 미로찾기, DFS 탐색

: 가장 나중에 입력된 자료가 가장 먼저 출력되는 자료 구조) Last in Last out 

top에서만 자료의 추가와 삭제가 일어난다.

 

4. 큐(Queue) : 

ex) 어레이, 연결리스트(노드)로 구현 가능

: 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 First in First out

추가되는 operation : enqueue, 삭제되는 operation : dequeue

 

비선형자료구조 (앞의 요소와 뒤의 요소의 관계가1:1의 관계가 아님)

종류 - 트리, 그래프

 

1.트리 : 부모 노드와 자식 노드 간의 연결로 이루어진 자료구조로

jdk 클래스 : TreeSet, TreeMap (Tree로 시작되는 클래스, 정렬지원)

보통 우리는 이진 트리를 많이 사용(Binary Tree)

 

1-1. Heap(Complete binary Tree)

Max Heap : Root 노드의 Element값이 가장 크고 sub 트리의 Element값이 부모보다 작을 때

Min Heap : Max 힙과 반대

- Heap sort (우선순위 큐에(Priority Queue) 이용)

 

1-2. 이진 검색 트리(Binary search Tree) 

: 검색을 위해서 만들어진 트리(중복을 허용하지 않는 유일한 key값)

루트를 중심으로 left child는 자신보다 작은값 right child는 자신보다 큰 값

검색 속도 O(log2N)

-inorder traversal 탐색 : left 부모 right (자료가 정렬되어 출력됨)

-preorder 

-postorder

 

 

2. 그래프(Graph) : 정점과 간선들의 유한 집합 G=(V,E)

ex)응용 : 네비게이션, 구글맵

-정점(Vertex) : 트리에서 노드 개념, 여러 특성을 가지는 객체

-간선(Edge) :  정점간의 연결 관계를 나타냄(Link)

간선은 방향성이 있는 경우와 없는 경우가 있음. 

- 그래프 구현 방법 :

인접행렬(Adjacency matrix) : 행렬로 나타내는 방법(연결되어있으면 1(or비용) 안되어있으면(0)

인접 리스트(adjacency list) : 각 노드랑 연결된 노드를 표현

- 그래프 탐색하는 방법

BFS(Breadth First Search)

DFS(Depth First Search)

 

매핑형자료구조

1. 해싱(Hashing) : 자료 검색을 위한 자료 구조

jdk 클래스 : HashMap, Properties

: key에 대한 자료를 검색하기 위한 Dictionary 개념의 자료구조 (key값은 유일) 

: key:value,

index=h(key) : 해시함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨.

 

해시알고리즘을 사용하면 Collision(충돌)이 발생할 수 있지만, 사용하는 이유는 검색에 들어가는 속도가 산술적으로 가능하다.

Collision을 해결하기 위한 방법(chaining)

1. 저장되는 메모리 구조를 해시테이블이라고 함.

2. 링크드 리스트를 이용한 chaining