자료구조의 종류와 개념 - 자료구조(1)

자료 구조는 효율적으로 데이터를 조회, 저장, 삭제, 수정하는 데이터 집합을 말한다.

자료 구조의 종류와 특징을 알아보자. 크게 선형 자료구조와 비선형 자료 구조로 나뉜다.

 

1. 선형 자료 구조

---

선형 자료 구조란 데이터가 일렬로 나열되어 있는 자료구조를 말한다. 일반적으로 순서가 있는 즉, 인덱스가 있는 자료구조라고 생각하면 된다.

 

1.1 Array - 배열

배열을 생성하면 메모리에 각 값들이 붙어서 생성

때문에 배열을 생성할 때는 배열의 길이를 지정해줘야 메모리를 할당할 수 있음.

i 번째 값을 찾을 때 첫 번째 주소 + (i * 배열 크기) 해서 찾아가기 때문에 조회가 빠름. 즉, 랜덤 Access가 빠름

대신 한번 선언하면 배열의 크기를 변경할 수 없음

메모리 낭비 가능성, 유연하지 못함

Array

 

1.2 List - 리스트

각 값을 연속되지 않은 메모리에 저장하고 그 둘을 연결시킨 구조

연결만 관리하면 되기 때문에 추가 및 삭제가 자유로움.

i번째 값을 찾을 때 바로 찾지 못하고 링크를 찾아가야 함. 즉, 랜덤 Access 가 느림

i번째 값을 찾으러 갈 때 꼭 0부터 찾아야 한다면 단방향 List. 즉, LinkedList

i번째 값을 찾으러 갈 때 자료 구조의 크기에 따라 끝에서도 찾을 수 있다면 양방향 List. 즉, DoubleLinkedList

LinkedList

Double LinkedList

 

1.3 Vector - 백터

동적으로 요소를 할당할 수 있는 동적 배열

 

1.4 Stack - 스택

먼저 들어오는 것이 나중에 처리(FILO)

재귀 함수, 웹 브라우저 방문 기록 등에 사용

List 개념에서 데이터를 뺄 때 데이터를 뒤에서(넣었던)부터 빼면 스택

Stack

 

1.5 Queue - 큐

먼저 들어오는 것이 먼저 처리(FIFO)

데이터가 삽입되는 쪽을 rear, 반대로 데이터가 삭제되는 front

List 개념에서 데이터를 뺄 때 데이터를 앞에서(넣었던 반대)부터 빼면 큐

Queue

 

---

 

2. 비선형 자료 구조

---

비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다. 일반적으로 트리나 그래프를 말한다.

 

2.1 Set -셋

종복을 허용하지 않는 고유한 요소를 저장하는 자료구조

List 개념에서 데이터를 넣을 때 이미 넣었던 데이터를 못 넣는 다면 셋

 

2.2 Graph - 그래프

장점(vertex)과 간선(edge)으로 이루어진 자료구조

장점을 노드로, 간선을 링크라 생각

List개념에서 에서 링크가 서로 꼬이게 연결되면 그래프

Graph

 

2.3 Tree - 트리

Graph에서 계층을 나눈 자료구조

위아래로만 이동이 가능하고 옆으로는 이동아 안되게 정한 것 것

루프 노드, 내부 노드, 리프 노드 등으로 구성

자식 노드가 2개 이면 binary tree

binary tree에서 좌로는 작은 것 우로는 큰 것을 놓는 규칙을 가지면 binary search tree

Tree

 

2.4 Heap - 힙

완전 이진트리 기반의 자료구조

최소 힙, 최대 힙으로 나뉨

• 최대 힙 : 루트 노드가 가장 모든 노드 중에 가장 큰 트리
• 최소 힙 : 루트 노드가 가장 모든 노드 중에 가장 작은 트리

 

2.5 Priority Queue - 우선순위 큐

대기열에서 우선순위가 높은 요소가 낮은 요소보다 먼저 제공되는 자료 구조

힙을 기반으로 구현

 

2.6 Map - 맵

키와 값으로 조합을 가진 자료 구조

해시 테이블을 이용해 Array의 랜덤 액세스 + List의 자유로운 증가의 장점 둘다를 가짐

Key값을 해시 함수를 통해서 index로 바꿔주면 그 버킷에 있는 index로 주소를 찾아서 그거에 연결된 List를 찾아감

Map

 

 

---

 

3. 시간 복잡도 정리

---

자료 구조를 사용할 때는 시간 복잡도를 고려해야 한다.

다음은 시간 복잡도의 평균과 최악을 표로 나타낸 것이다.

 

 

---

 

4. 마치며

---

이번 글에서는 컴퓨터 언어와 상관없이 자료구조의 종류와 각 개념에 대해서 간략하게 알아보았다. 이후로는 JAVA에서 해당 자료구조가 어떻게 구현되는지, 어떤 특징을 가지는지 시리즈로(?) 알아보겠다.

 

 

 

---

자료구조 시리즈

1. 자료구조의 종류와 개념 - 자료구조(1)

2. JAVA ArrayList - 자료구조(2)

3. JAVA LinkedList - 자료구조(3) 

4. JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

5. JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

6. JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6)

7. JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

8. JAVA HashMap 과 HashSet의 성능 비교 - 자료구조(8)

9. JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)