[자료구조]

1. 자료구조의 정의

: 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것

• 자료 구조는 자료의 표현과 그것과 관련된 연산이다.

• 자료 구조는 일련의 자료들을 조직하고 구조화하는 것이다.

• 어떠한 자료 구조에서도 필요한 모든 연산들을 처리할 수 있다.

• 자료 구조에 따라 프로그램 실행시간이 달라진다.

2. 자료 구조의 분류

(출처 : 2021 시나공 책)

3. 배열(Array)

: 배열은 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합이다.

• 배열은 정적인 자료 구조로 기억장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 발생한다.

• 배열은 첨자를 이용하여 데이터에 접근한다.
  (첨자 : 배열 중의 요소를 식별하기 위해 배열명에 계속하여「첨가하는」것.)

• 배열은 반복적인 데이터 처리 작업에 적합한 구조이다.

• 배열은 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편하다.

• 배열은 사용한 첨자의 개수에 따라 n차원 배열이라고 부른다.

ex) a[0] 에서 a는 변수의 이름이고 '[숫자]'는 첨자에 해당함.

4. 선형 리스트(Linear List)

: 선형 리스트는 일정한 순서에 의해 나열된 자료 구조이다.

• 선형 리스트는 배열을 이용하는 연속 리스트(Contiguous List)와 포인터를 이용하는 연결 리스트(Linked List)로 구분된다.

• 연속 리스트(Contiguous List)

  • 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.

  • 연속 리스트는 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다. (배정된 기억장소를 빈 공간없이 꽉 차게 사용한다는 의미)

  • 연속 리스트는 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입-삭제 시 자료의 이동이 필요하다.

  
  

• 연결 리스트(Linked List)

  • 연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

  • 연결 리스트는 노드의 삽입-삭제 작업이 용이하다.

  • 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.

  • 연결 리스트는 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.

  • 연결 리스트는 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

  • 연결 리스트는 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

5. 스택(Stack)

: 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.

• 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last In First Out) 방식으로 자료를 처리한다.

• 스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.

• TOP : 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소이다.

• Bottom : 스택의 가장 밑바닥이다.

6. 큐(Queue)

: 큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다.

• 큐는 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First In First Out) 방식으로 처리한다.

• 큐는 시작과 끝을 표시하는 두 개의 포인터가 있다.

• 프런트(F, Front)포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.

• 리어(R,Rear)포인터 : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터로, 삽입 작업을 할 때 사용한다.

• 큐는 운영체제의 작업 스케줄링에 사용한다.

7. 그래프(Graph)

: 그래프 G는 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어진다.

• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.

• 통신망(Network), 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 응용된다.

• 트리(Tree)는 사이클이 없는 그래프(Graph)이다.

• n개의 정점으로 구성된 무방향 그래프에서 최대 간선 수는 n(n-1)/2 이고, 방향 그래프에서 최대 간선 수는 n(n-1) 이다.

출처 : 2021 시나공 정보처리기사 필기책