자료구조 (Data Structure)

 

자료구조란

• 자료구조 (data structure) : 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미, 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미 - 신중하게 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 함. 

 

 

자료구조가 중요한 이유

자료구조에는 여러 종류가 있는데 각각 자료구조는 각각의 연산 및 목적에 맞춰짐

B-트리는 데이터 베이스에 효율적이며, 라우팅 데이블은 네트워크(인터넷, 인트라넷)에 일반적이다.

프로그램을 설계할 때 어떤 자료구조를 선택할지 가장 우선적으로 고려해야 한다.

큰 시스템을 제작할 때 구현의 난이도나 최종 결과물의 성능이 자료구조에 크게 의존한다.

자료구조가 선택되면 적용할 알고리즘은 상대적으로 명확해진다.

 

 

 

자료구조 특징

자료구조의 특징은 효율성, 추상화, 재사용성이다. 

• 효율성 : 상황에 맞는 알고리즘을 사용하여 자료를 구조화시키기 때문에 효율적으로 동작한다.
• 추상화 : 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것 
• 재사용성 : 자료구조를 이용하여 데이터를 처리할 경우 해당 자료구조의 인터페이스만 이용하여 데이터를 처리하도록 하므로 모듈화가 가능하다. 

 

 

 

자료구조 분류

자료구조는 구현, 형태로 분류된다.

 

* 구현에 따라 

• 배열 : 가장 일반적인 단위, 메모리 상에 같은 타입의 자료가 연속적으로 저장된다.

배열 Array - 여러 데이터를 그룹핑해서 관리하기 위한 자료구조 , 배열 안에 여러 정보를 담을 수 있고, 반복문과 결합하면 정보 효율적 관리, 크기가 정해짐 , 인덱스 식별 + 조회 가능

 

Array

 

 

• 튜플 :  둘 이상의 자료형을 묶음으로 다루는 구조

 

Tuple

 

 

• 연결 리스트(linked List) : 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성
• 원형 연결 리스트 : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 원형 리스트이다.
• 이중 연결 리스트 : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
• 환형 이중 연결 리스트 :  처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.

리스트 List - 배열이 갖는 인덱스 구조의 장점을 버린 대신 각 데이터의 빈틈을 없애는 방법 선택 , 데이터의 삽입과 삭제에 대한 데이터의 낭비가 줄고, 검색시간이 증가한 것이 특징

 

List

 

 

 

 

 

* 형태에 따라

(선형구조)

• 스택 : 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다.  반대로 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 

스택(Stack) - 흔히 스택을 쌓는다고 이야기 하는것처럼 스택은 하나의 바구니에 데이터를 순차적으로 담겨있는 형태 

LIFO (Last In First Out) 예) 웹브라우저 앞으로 가기 뒤로가기

 

Stack

 

 

• 큐 : 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다. 

큐(Queue) - FIFO(First-In-First-Out) 줄을 서서 기다리다는 뜻, 컴퓨터 과학 전반에 자주 쓰이는 자료구조, 예 ) 버퍼

일반적인 큐는 선형이지만 크기가 제한되어있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 한 칸씩 옮겨야 한다는 단점이 있음.

 

 

Queue

 

 

 

• 덱 : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

덱(Deque) - 덱은 큐와 스택을 합친 것. 큐는 뒤에만 삽입이 가능하고 스택은 위에만 삽입이 가능하지만 덱은 앞뒤 모두 삽입과 삭제가 가능하다.

 

 

Deque

 

 

 

(비선형 구조)

• 그래프  : 꼭짓점과 꼭짓점을 잇는 변으로 구성 (유향 그래프 - 변의 방향은 보통 부모를 가리킴/ 무향 그래프 - 순환이 없는 연결 그래프)

그래프(Gragh) - 단순히 노드와 그 노드를 연결하는 에지를 하나로 모아 놓은 자료구조, 연결돼있는 객체 간의 관계를 표현할 수 있는 자료구조 , 예 ) 지도, 지하철, 노선도 최단경로, 전기회로, 도로

 

 

Graph

 

 

• 트리 : 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현 (이진트리 - 자식이 최대 두 개인 트리 / 힙 - 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것)

트리(Tree) - 트리는 그래프의 특별한 케이스며 '최소 연결 트리'라고 불린다. 두 개의 정점 사이에 반드시 1개의 경로만 가진다. 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다. 

 

Tree

 

 

 

 

 

 

 

programmers.co.kr/learn/courses/17

자바로 배우는 자료구조(with 생활코딩)

opentutorials.org/module/1335

Data Structure (자료구조)