자료구조의 개념과 특징

1. 자료구조란?

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

효율적인 자료구조가 좋은 알고리즘의 기반이 된다.

 

2. 자료구조의 종류 

자료구조에는 두가지 유형이 존재한다. 

• 선형구조 : 데이터를 한줄로 나열할 수 있다. - 배열, 연결리스트, 스택, 큐
• 비선형 자료구조 : 데이터를 한줄로 나열할 수 없다.- 그래프 , 트리

2.1 배열 (Array)

: 연속된 메모리 공간에 순차적으로 저장된 데이터 모음의 자료구조

 

특징

• 0부터 시작하는 인덱스(index)를 가지고 있다.
• 동일한 타입의 데이터만 저장할 수 있다.
• 크기가 고정되어 있다.

장점

• 인덱스를 통해 접근하기때문에 빠르게 데이터를 가지고 올 수 있기 때문에 검색 성능이 좋다.
• 구현이 쉽다.

단점

• 처음 생성할때 메모리가 할당되기 때문에, 한번 생성된 배열의 길이는 변경할 수 없다.
• 자료의 삽입과 삭제에 비효율적이다.
  • 배열 중간에 항목을 추가하려면 기존 요소를 밀어내고 해당 공간을 비운 후 요소를 추가해야하기때문에 비효율적이다.
  • 배열의 어떤 엘리먼트가 삭제되면 , 삭제된 공간을 빈 공간으로 남겨 둬야하기 때문에 메모리가 낭비된다.
  • (자바에서 배열은 고정된 길이를 갖고 있기 때문에 특정 요소를 제거해 길이를 줄일 수 없다. 이때는 LIst로 변환 후 요소를 삭제, 가변적으로 길이를 변경할 수 있다. )

배열을 사용하는 경우

• 순차적인 데이터를 저장해 값보다 순서가 중요할 때
• 특정 요소를 빠르게 읽어야 할 때

---

2.2 연결리스트 (LinkedList)

: 각 노드가 데이터와 포인터를 가지고 한 줄로 연결(Link)되어 있는 모양의 자료구조.

특징

• 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 이 포인터는 다음 노드의 주소값을 가지고 있다.
• 제일 앞에 있는 노드를 head, 끝에 있는 노드를 tail 이라고 한다.
• 데이터를 추가/삭제하면 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
• 메모리 상에서 순차적으로 저장되지 않는다.

장점

• 길이가 가변적이다. 길이가 변하지 않는 배열의 단점을 링크드리스트가 커버할 수 있다.
• 데이터의 숫자만큼만 메모리를 사용하면 되기때문에 메모리 낭비가 적다.
• 데이터를 추가/삭제할때 앞 뒤 링크만 변경되기 때문에 배열보다 추가/삭제가 쉽다.

단점

• 배열과 달리 인덱스가 존재하지 않아 특정 요소에 접근할때는 모든 요소를 탐색해야 할 수 있어 탐색 속도가 느리다.

 

---

2.3 스택(Stack)

데이터를 차곡차곡 쌓아올린 형태의 자료구조이며 LIFO(Last In First Out)구조 즉, 최근에 스택에 추가한 항목이 가장 먼저 나온다.

 

특징

• 한쪽 끝에서만 자료를 넣고 뺄수 있는 구조로 ex) 프링글스
• 삽입 연산을 Push , 삭제연산을 pop 이라고 한다.

장점

• 구조가 단순해서 구현이 쉽다
• 데이터 저장/읽기 속도가 빠르다.

단점

• 데이터의 최대 개수를 미리 정해야 한다.
• top 데이터외에 접근할 수 없기 때문에 탐색하려면 모든 데이터를 꺼내서 탐색해야 한다.

스택을 사용하는 경우

• 브라우저의 뒤로가기 : 내가 방문한 주소들을 하나씩 스택에 저장해두었다가 뒤로가기를 눌렀을 대 가장 맨 위에 (최신) 주소를 사용한다.

---

2.4 큐(Queue)

: 스택과 반대로 먼저 들어온 것이 먼저 나가는 FIFO(Fist in First Out)구조

특징

• 선입선출 ex) 카페에서 내가 먼저 주문하면 나 먼저 커피 받음
• front에서는 Dequeue(데이터 꺼냄) 를 , rear(끝 )에서는 Enqueue(데이터 삽입)연산이 이루어진다.
• 가득 찬 큐에 요소를 추가하려고하면 Overflow, 빈 큐에 요소를 삭제하려고 하면 Underflow가 발생한다

장점

• 생산자/소비자가 동일한 속도로 동작할 필요가 없다. 큐에서 대기 가능.
• 데이터를 입력 순서대로 처리해야 할 상황에 유리하다.

단점

• 스택과 같이 중간 요소에 대한 접근이 불가능하다 .

큐를 사용하는 경우

• 대기 순서 관리
• BFS 알고리즘

---

2.5 해시테이블(Hash Table)

: 해시 테이블은 해시함수를 사용해 변한환 값을 index로 삼아 Key(키)- Value(값) 형태로 데이터를 저장하는 자료구조이다.

임의의 길이의 값을 해시함수(Hash Function)를 사용해 고정된 크기의 값으로 변환하는 작업을 해싱(Hashing) 이라고 한다.

 

특징

• 키 값을 이용해 빠르게 데이터를 검색할 수 있다.
• 두 개의 다른 key가 동일한 해시 값을 같는 경우 충돌이 발생할수 있다. 이때 해결방법이 존재하는데
  • Chaining
  • Open Addressing
• 해시 충돌이 없는 상태에서 배열, 리스트 같은 선형 구조보다 더 빠르게 탐색이 가능하다.
• 해시를 사용하기 때문에 해시 값을 알아도 key를 알기 어렵다.

장점

• 구조가 단순하다.
• 키 값을 이용해 빠르게 value값을 찾을 수 있다.
• 키와 해쉬값이 연관성이 없어 보안에 유리하다.

단점

• 순서가 있는 배열과는 맞지 않는다.
• 해쉬 값 충돌 발생 가능성

해시 테이블을 사용하는 경우

• 검색을 많이 하는 구조일때
• 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 하드디스크나 클라우드에 존재하는 많은 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.

 

---

2.6 트리(Tree)

: 계층적인 자료를 표현하는 데 이용되는 자료구조이다. 노드로 이루어져 있다.

특징

• 나무를 거꾸로 뒤집어 놓은 모양
• 컴퓨터의 딕셔너라 구조가 트리 구조의 대표적 예
• 하나의 루트노드와 0개 이상의 하위 트리로 구성되어 있다.
• 노드 간 부모-자식 관계를 갖고있는 계층형 자료구조이다.
• 모든 자식 노드는 하나의 부모 노드만 갖는다.
• 비선형 구조
• 깊이, 높이, 레벨 등을 측정할 수 있다.
• 노드가 N개인 트리는 항상 N-1개의 링크를 가진다.

기본용어

• 노드(Node) : 트리를 구성하는 기본 요소
• 간선(Edge) : 노드와 노드 간의 연결선
• 루트 노드(Root Node): 트리에서 부모 노드가 없는 최상위 노드.
  • 2,3의 부모 노드는 1
• 자식 노드(Child Node): 부모 노드의 하위 노드
  • 1의 자식 노드는 2,3
• 형제 노드(Sibling node): 같은 부모를 가지는 노드
  • 2,3은 형제 노드
• 외부노드(External node), 단말노드(Terminal node), 리프노드(Lead node) : 자식 노드가 없는 노드
  • 8,9,10,11,13,14
• 내부노드(Internal nnode), 비 단말노드(non-terminal node) , 가지노드(branch node) : 자식 노드가 하나 이상인 노드
  • 1,2,3,4,5,6,7
• 깊이 (depth) : 루트에서 특정 어떤 노드까지 도달하기 까지의 간선 수
  • 루트의 깊이는 무조건 0
  • 4라면 깊이 2
  • 9라면 깊이 3
• 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이
  • 3
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
  • A의 레벨 1
  • B의 레벨 2,3
  • C의 레벨 4,5,6,7

이진트리(Binary Tree) :

: 트리의 일종으로 자식노드가 최대 두개인 노드로 구성된 트리이다.

이진탐색트리(Binary Search Tree)

• 말 그대로 어떠한 값을 찾는것에 특화된 자료구조.
• 왼쪽 자식노드가 나보다 작고, 오른쪽 자식노드는 나보다 커야한다는 특징이 있다.
• 중복된 노드가 없어야 한다.

 

 

 

 

 

 

 

참고 및 출처 

https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks