Java 1.여러가지 자료구조(배열, 연결리스트, 스택, 큐 / 트리, 그래프, 해싱)

자료구조란 무엇인가? (Data Structure)

• 프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법들
• 효율적인 자료구조( 프로그램의 수행속도와 밀접한 관련 0)가 성능 좋은 알고리즘의 기반이 됨

 

자료구조에는 어떤 것들이 있나?

1. 한 줄로 자료를 관리하기 (선형 자료구조)

ex) 배열, 연결리스트, 스택, 큐

배열 (Array)_

• 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음
• 중간이 비면 안됨 (배열은 논리적, 물리적 순서가 동일함) -> 중간에 element 넣으면 뒤에껀 밀어야 함. 특정요소 넣고빼기 쉬움
• 사이즈만큼 할당받고 시작함
• 수행속도 : O(n) -> 자료의 추가삭제에는 느림, 특정요소 위치 찾기는 빠름

연결 리스트 (LinkedList)

• 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음
•  배열처럼 처음부터 할당을 받는것이 아닌, 노드가 필요할때 메모리를 할당받아서 사용
• 자료는 '링크'를 가지고 있음. 앞에있는게 뒤에있는거만 알고있음(더블링크드리스트 : 앞뒤에서 서로의 링크 알고있음)
• 데이터가 추가되고 삭제되는데 소요되는 수행속도가 배열보다 빠름 : O(1)
• 몇번째 요소를 찾는것에 대한 수행속도 : O(n)

스택 (Stack) 

• 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First OUt)
• 상자 쌓아놓는것
• 자료가 추가되고 삭제되는 일이 맨 끝(top)에서만 일어남
• 지역변수들(로컬변수), 메소드에서 쓰는 메모리는 스택메모리에 저장됨
• 예시) 가장 최근의 데이터 꺼내거나, 바둑같은 게임에서 최근의 수 무를때, 미로찾기, BFS깊이우선탐색 시 활용

큐 (Queue) 

• 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First In First Out)
• 한줄로 쓰는, 선착순!
• 맨앞 : front, 맨뒤 : rear
• 자료를 추가하고 삭제하면 메모리가 앞뒤로 비게 되므로, circular queue 로 구성하기도 함
• 스택, 큐 모두 array, linkedlist로 구현할 수 있음

 

2. 비선형 자료구조

ex) 트리, 그래프 

트리 (Tree)

• 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조

이진트리중 가장 많이쓰는 힙 & 이진트리

  힙(heap)

• 트리가 채워질때 항상 왼쪽자식부터 채워짐 
• Priority queue를 힙을 사용하여 구현함 (우선 큐: 가장 우선순위가 높은값부터 꺼낼 수 있으므로)
• Max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우 : 루트값이 가장 큼
• Min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우 : 루트값이 가장 작음
• 루트가 하나씩 꺼내지면 큰수부터 reordering 함 => heap sort(정렬)에 활용 할 수 있음
• 요소의 값이 중복될 수 있음. 루트값이 자식값과 비교하여 작거나, 크거나 '같아도 ' 됨

  이진 트리 (binary tree) 

• 부모노드에 자식노드가 두 개 이하인 트리
• 목적 : 검색
• 자료(key) 가 중복되면 안됨. 유일한값만 들어갈수있음
• 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐
• fully completed binary tree의  depth = n, 요소개수 = 2의n제곱 -1 -> 찾아가는 시간 : log2n -> 자료를 검색에 걸리는 시간 : 평균 log(n) 임 (다른것에비해 검색속도가 빠름)
• 편향된 트리(squid tree)의 검색속도 : n -> binary search tree는 avl tree, red black tree로 구현함
• jdk 클래스 : TreeSet, TreeMap (Tree로 시작되는 클래스는 정렬을 지원 함) 

 

• inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨 

    -> 7 10 15 22 23 28 56 (오름차순 출력)

 

 

 

 

 

 

 

 

그래프 (Graph)

• 정점과 간선들의 유한 집합 G = (V,E)
• 정점(vertex) = 노드(node) : 여러 특성을 가지는 객체
• 간선(edge) : 이 객체들을 연결 관계를 나타냄. 링크(link)
• 간선은 방향성이 있는 경우와 없는 경우가 있음
• 그래프를 구현하는 방법 : 1) 인접 행렬(adjacency matrix), 2) 인접 리스트(adjacency list)
• 그래프를 탐색하는 방법 : BFS(bread first search), DFS(depth first search)
• ex) google map, 네비게이션

 

해싱 (Hashing) 

• 자료를 검색하기 위한 자료 구조
• 검색을 위한 자료 구조
• 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조
• key는 유일하고 이에 대한 value를 쌍으로(페어로) 저장
• index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨
• 해시 함수에 의해 인덱스 연산이 산술적으로 가능 O(1) (속도가 굉장히 빠름)
• 저장되는 메모리 구조를 해시테이블이라 함(자바에서는 해쉬테이블이 75%정도 차면 충돌을 방지하기위해 재구성하도록 구현되어있음)
• 들어가는 순서와 나오는 순서 등 '순서'는 상관없음 (순서대로 인덱스값을 부여하는것이 아님)
• jdk 클래스 : HashMap, Properties

해시테이블

 

버켓이 크고 슬롯이 크면  : 오버헤드 발생

-> 링크드리스트를 활용한 '체이닝' 방식이 나타남

체이닝 : 노드에대한 인접노드들을 링크드리스트 형식으로 표현 :  각 해시테이블의 키에대한 인덱스값들을 옆에다가 링크드리스트처럼 구현(필요할때마다 allocation받음 )