자료구조

자료구조

• 정의

  자료구조(Data Structure) 는 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말한다.

  각각의 자료구조에는 장단점이 있으므로 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있다.

  따라서 자료구조를 사용하여 문제를 해결하려면 다양한 자료구조의 장단점을 살펴보며 어떤 자료구조를 사용하는 것이 최선일지 판단해야 한다.

• 추상 데이터 타입

  추상 데이터 타입(Abstract Data Type) 은 데이터와 그 데이터에 대한 연산을 묶어서 하나의 단위로 취급하는 방법을 말하며 이는 데이터의 논리적인 모델을 정의한다.

  즉, 데이터 타입을 추상적으로 정의한 것으로 데이터나 연산이 무엇인지는 정의되지만 어떻게 구현할 것인지는 정의되어 있지 않은 상태를 말한다.

  추상 데이터 타입은 추상화(abstraction)-> 정보은닉기법(information hiding)-> 추상 자료형(ADT) 형태로 유래되었으며 추상화란 사용자에게 중요한 정보는 강조되고, 중요하지 않은 구현 세부 사항은 제거하는 것을 말한다.

  추상 데이터 타입은 다음과 같이 정의된다.

  • 객체 : 추상 데이터 타입에 속하는 객체가 정의된다.
  • 연산 : 이들 객체들 사이의 연산이 정의된다. 이 연산은 추상 데이터 타입과 외부를 연결하는 인터페이스의 역할을 한다.

  이렇게 정의된 추상 데이터 타입을 실제로 구현한 결과가 자료구조이며

  구현된 자료구조를 가지고 또 다른 추상 데이터 타입을 정의하는 등, 추상 데이터 타입과 자료구조는 서로 원활한 상호 작용을 이루고 있다.

• 분류

  

  ### 단순구조(Simple Structure): 단순구조는 하나의 데이터 요소만으로 구성되어 있습니다.

  • 정수(Integer): 정수형 데이터를 나타내는 자료형으로, 양의 정수, 음의 정수, 0을 포함합니다.

  • 실수(Float): 실수형 데이터를 나타내는 자료형으로, 소수점 이하의 값을 가집니다.

  • 문자(Char): 문자 하나를 나타내는 자료형으로, 알파벳, 숫자, 특수 기호 등을 포함합니다.

  • 문자열(String): 문자들의 집합으로, 여러 문자가 순서대로 나열된 자료형입니다.

  ### 선형구조(Linear Structure): 선형구조는 데이터 요소가 순서대로 나열되어 있는 구조입니다.

  • 순차리스트(Sequential List): 배열 등의 연속된 메모리 공간에 데이터를 순서대로 저장합니다.

  • 연결리스트(Linked List): 노드(Node)들이 연결된 구조로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다.

    • 단순 연결 리스트(Singly Linked List): 각 노드가 다음 노드를 가리키는 단일 포인터로 구성된 연결 리스트입니다.

    • 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터로 구성된 연결 리스트입니다.

    • 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 형태의 연결 리스트입니다.

  • 스택(Stack): 후입선출(LIFO) 구조로, 데이터를 삽입(push)하거나 삭제(pop)할 때 한쪽 끝(top)에서만 이루어집니다.

  • 큐(Queue): 선입선출(FIFO) 구조로, 데이터를 삽입(enqueue)하거나 삭제(dequeue)할 때 한쪽 끝(rear)에서 삽입하고 반대쪽 끝(front)에서 삭제합니다.

  • 데크(Deque): 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조로, 스택과 큐의 특성을 모두 가집니다.

  ### 비선형구조(Nonlinear Structure): 비선형구조는 계층적이지 않고 상호 연결된 구조입니다.

  • 트리(Tree): 부모 노드와 자식 노드 간의 계층적인 구조를 가지며, 최상위 노드를 루트(root)로 하여 아래로 뻗어나가는 형태를 가집니다.

    • 일반 트리(General Tree): 각 노드의 자식 수에 제한이 없는 트리 구조입니다.

    • 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가지는 트리 구조입니다.

  • 그래프(Graph): 정점(Vertex)과 간선(Edge)의 집합으로 이루어진 자료구조로, 정점들이 연결되어 있는 네트워크를 표현합니다.

    • 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프로, 간선은 정점 간의 방향을 나타냅니다.

    • 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프로, 간선은 정점 간의 양방향 관계를 나타냅니다.

  ### 파일구조(File Structure): 파일구조는 데이터를 파일로 저장하는 방법을 말합니다.

  • 순차 파일(Sequential File): 데이터가 순차적으로 저장되며, 순차적인 접근이 주로 이루어지는 파일 구조입니다.

  • 색인 파일(Indexed File): 데이터에 대한 색인을 가지고 있어 빠른 접근이 가능한 파일 구조입니다.

  • 직접 파일(Direct File): 레코드의 주소를 계산하여 직접 접근할 수 있는 파일 구조입니다.