자료 구조

자료 구조란?

여러 데이터들의 묶음을 저장하고, 사용하는 방법을 말한다.

• 추상화 : 추상화란 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념만 간추려 내는 것을 말한다.
• 재사용성 : 자료구조를 설계할 때, 특정 프로그램에서만 동작하게 설계하지 않는다. 다양한 프로그램에서 사용할 수 있도록 설계하기 때문에 다른 프로그램에서도 사용할 수 있다.

자료구조의 종류

자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 데이터가 일렬로 나열되어 있는 것을 뜻하고, 비선형 구조는 특정한 형태를 띠는 구조를 말한다.

선형 구조

• 배열(Array) : 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적이며 순차적으로 저장된다.
  - 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조
  • 배열은 크기가 고정적
  • 데이터가 삭제되면 배열 전체의 데이터를 재정렬
• 연결리스트(Linked List) : 각 노드가 데이터와 포인터(주소)를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장한다.
  - 배열의 단점이 보안된 형태의 자료구조로, 크기가 가변적인 배열(장점)
  • 노드 : 데이터의 저장단위로, 데이터 값과 포인터를 한싹으로 구성한다.
  • 포인터를 위한 저장공간이 따로 필요함.
  • 점근 속도가 느리다.
  • 크기의 가변성을 구현하기 위해 노드와 포인터를 저장 및 연결한다.
• 스택(Stack) : 먼저 저장된 데이터가 꺼내어 쓸 때는 제일 마지막에 나온다. 반대로 가장 최근에 저장된 데이터가 꺼내어 쓸때는 제일 먼저 나온다. 즉, 후입선출의 특징을 가진다.
  - LIFO 방식으로인해 , 구현이 단순하여 쉽다.
  • LIFO 방식으로 인해, 데이터의 저장 및 검색 속도가 빠르다.
  • 데이터를 쌓는 방식(LIFO)
• 큐(Queue) : 스택과 반대로 먼저 저장된 데이터가 제일 먼저 나온다. 즉, 선입선출의 특징을 가진다.
  - FIFO 방식으로 데이터를 저장하는 자료구조
  • FIFO 방식으로 인해 데이터 삭제시, 재정렬이 필요 없다.
• 덱(Deque) : 양쪽에서 데이터를 넣고 뺄 수 있다. 스택과 큐의 특성이 합쳐졌다고 생각하면 된다.
• 해시(Hash) : 임의의 크기를 가진 데이터를 고정된 크기의 데이터로 변화시켜서 저장한다.
  - Key와 Value를 한 쌍으로 저장하는 자료구조

비선형 구조

• 트리(Tree) : 부모 노드 밑에 여러 개의 지식 노드가 연결되고 , 자식 노드가 다시 부모 노드가 되어 각각의 자식 노드가 연결되는 재귀적 형태를 가진다.
  - 노드와 브랜치를 이용하여 구성한 자료구조로, 사이클이 없는 것이 특징이다.
  • 트리를 기반한 이진트리를 이용하여 탐색 알고리즘 구현에 자주 사용된다.
• 그래프(Graph) : 노드와 그노드를 연결하는 간선을 하나로 모아 놓는 형태로 구성된다.

참고
https://nibble1492.tistory.com/12