[Do it 자바 프로그래밍 입문] 12. 자료구조

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

 

• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
• 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함

 

 

 

---

 

 

 

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

 

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

- 배열 (Array) : 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음. 인덱스 연산을 할 수 있어 편리하다.

 

- 연결 리스트 (LinkedList) : 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 뎐ㄱㄹ됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음. 자료 추가/삭제 용이.

 

- 스택 (Stack) : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last in First Out)

 

- 큐 (Queue) : 가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First in First Out)

 

 

 

• 트리 (Tree) : 부모 노드와 자식 노드 간의 연결로 이루어진 자료 구조

- 힙 (heap)  : Priority queue를 구현 (우선 큐)

 

   Max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우

   Min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우

   heap 정렬에 활용 할 수 있음

   이진 트리 (binary tree) : 부모노드에 자식노드가 두 개 이하인 트리

   이진 검색 트리 (binary search tree)

 

자료(key)의 중복을 허용하지 않음 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐 자료를 검색에 걸리는 시간이 평균 log(n) 임 inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨

 

 

 

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

       - 정점(vertex) : 여러 특성을 가지는 객체, 노드(node)

       - 간선 (edge) : 이 객체들을 연결 관계를 나타냄. 링크(link)

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

         그래프를 구현하는 방법 : 인접 행렬 (adjacency matrix), 인접 리스트(adjacency list)

         그래프를 탐색하는 방법 : BFS(bread first search), DFS(depth first search)

 

 

 

• 해싱 (Hashing) : 자료를 검색하기 위한 자료 구조

       검색을 위한 자료 구조

       키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조

       key는 유일하고 이에 대한 value를 쌍으로 저장

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

       해시 함수에 의해 인덱스 연산이 산술적으로 가능 O(1)

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

       jdk 클래스 : HashMap, Properties

 

 

 

 

---

 

 

 

배열(Array)

 

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 정해진 크기가 있음
• 요소의 추가와 제거 시 다른 요소들의 이동이 필요함
• 배열의 i 번째 요소를 찾는 인덱스 연산이 빠름
• jdk 클래스 : ArrayList, Vector

 

 

 

---

 

 

 

연결 리스트 (LinkedList)

 

• 동일한 데이터타입을 순서에 따라 관리하는 자료 구조
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
• 연결 리스트의 i 번째 요소를 찾는 게 걸리는 시간은 요소의 개수에 비례 : O(n)
• jdk 클래스 : LinkedList

 

 

 

---

 

 

스택 (Stack)

 

• 맨 마지막 위치 (top) 에서만 자료를 추가, 삭제, 꺼내올 수 있음 (중간의 자료를 꺼낼 수 없음)
• Last In First Out (후입선출) 구조
• 택배 상자가 쌓여있는 모양
• 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 무를 때 사용할 수 있음
• 함수의 메모리는 호출 순서에 따른 stack 구조
• jdk 클래스 : Stack

 

 

 

---

 

 

 

큐(queue)

 

• 맨 앞 (front) 에서 자료를 꺼내거나 삭제하고, 맨 뒤 (rear) 에서 자료를 추가 함
• Fist In First Out (선입선출) 구조
• 일상 생활에서 일렬로 줄 서 있는 모양
• 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용 되는 자료구조
• 콜센터에 들어온 문의 전화, 메세지 큐 등에 활용됨
• jdk 클래스 : ArrayList