자료 구조

01. 자료 구조

1) 자료 구조의 개념

프로그램에서 쉽게 사용될 수 있도록 구성된 데이터 간의 논리적인 관계
컴퓨터상에 자료를 저장하기 위해서 만들어진 논리적인 틀
자료를 효율적으로 사용할 수 있도록 컴퓨터에 저장하는 방법
프로그램에서 처리되는 데이터는 구조를 어떻게 구성하느냐에 다라 성능에 많은 영향을 미치게 됨
데이터를 처리하는 입장에서 데이터 사이에 존재하는 관계
효과적으로 설계된 자료 구조는 실행 시간 혹은 기억 장치 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 함
신중히 선택한 자료 구조는 보다 효율적인 프로그래밍을 할 수 있게 함
데이터의 추가, 삭제, 검색을 효율적으로 할 수 있는 적절한 데이터 구조를 사용하는 게 중요
데이터를 조직하고 구조화하며 연산하는 일련의 활동
대표적인 자료 구조에는 선형 리스트(Linear List), 스택(Stack), 큐(Queue), 트리(Tree) 등이 있음

2) 데이터의 형태에 따른 자료 구조 분류

1. 단순 구조(Simple)

프로그래밍 언어에서 제공하는 기본 데이터 타입
int(정수형), float(실수형), double(배정도 실수형), char(문자형) 등이 있음

2. 선형 구조(Linear)

데이터들 사이의 선후 관계가 일 대 일인 구조
데이터를 저장시키는 데 있어 데이터와 데이터를 1:1 대응 구조로 관계를 맺어 저장시키는 형태의 구조
선형 구조는 크게는 순차(Sequential) 구조와 연결(Linked) 구조로 나눌 수 있음
순차 구조는 삽입과 제거가 자주 일어날 때 처리 시간이 가장 많이 소요되는 자료 구조이며, 연결 구조인 연결 리스크(Linked List)는 데이터의 삽입, 삭제가 가장 용이한 방법
스택(Stack), 큐(Queue), 데크(Deque), 선형 리스트(Linear List), 연결 리스트(Linked List)가 있음
선형 리스트는 배열을 이용하는 연속 리스트(Contiguous List)와 포인터(Pointer)를 이용하는 연결리스트(Linked List)로 구분

3. 비선형 구조(Non-Linear)

데이터들 사이의 선후 관계가 계층 또는 그물 형태를 가지는 구조
데이터를 저장시키는 데 있어 데이터와 대응되는 다른 데이터가 여러 개 존재하는 경우의 관계성을 1:N, N:M 구조로 저장시키는 형태 구조를 비선형 구조라고 함
트리(Tree) 구조, 그래프(Graph) 구조가 있음

4. 파일 구조(File)

보조 기억 장치에 데이터값이 실제로 기록되는 자료 구조
순차 파일, 색인 파일 등이 있음

02. 선형 구조

1) 스택(Stack)

1. 스택의 구조

데이터를 저장하는 기억 장치가 한쪽으로만 입구와 출구가 있음
데이터가 저장될 때 입력된 데이터의 위치를 스택 포인터(TOP)가 가리키고 있음
스택 포인터는 데이터가 입력(PUSH)될 때마다 1씩 증가하며 스택 크기보다 큰 값을 갖게 되면 데이터를 더 이상 기억할 수 없는 오버플로우(Overflow) 상태가 됨
스택에 데이터가 출력(POP)될 때에는 1씩 감소하며 저장된 데이터가 없을 경우에는 스택 포인터는 0값을 기억하게 됨

2. 스택의 특징

데이터의 삽입과 삭제가 같은 쪽에서 이루어지는 구조
나중에 입력된 데이터가 먼저 출력하는 메모리 사용 방법
스택은 가장 나중에 삽입된 데이터가 가장 먼저 삭제되므로 후입 선출(LIFO : Last-In First-Out) 구조라고 함
데이터와 데이터 사이는 1:1 관계
스택은 입출력이 한쪽 끝으로만 제한된 리스트로 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로우(Underflow)가 발생
함수를 호출하여 복귀할 때 사용
깊이 우선 탐색(DFS)에서 사용
재귀적(Recursion) 함수를 호출 사용할 때 사용
인터럽트 수행 시 현재 수행 중인 프로세스의 복귀 주소를 저장할 때 사용
수식을 우선적으로 연산하기 위한 방법으로 사용
0-주소 명령어 방법으로 사용

2) 큐(Queue)

1. 큐의 구조

한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 데이터 구조
큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO : First-In First-Out) 구조라고 함
데이터를 저장하는 기억 장치가 양쪽으로 있으며 한쪽으로는 입구, 다른 한쪽으로는 출구가 있음
데이터가 저장될 때 입력된 데이터의 위치를 삽입 포인터(Rear)가 가리키고 있고, 출력된 데이터는 삭제 포인터(Front)가 가리키고 있음
삽입 포인터는 데이터가 입력될 때마다 1씩 증가하며 큐 메모리 크기보다 큰 값을 갖게 되면 데이터를 더 이상 기억할 수 없는 오버플로우 상태가 됨
삭제 포인터는 데이터가 삭제될 때마다 1씩 증가하며 삽입 포인터와 같게 되면 큐 메모리에 데이터가 비어있는 상태가 됨

2. 큐의 특징

먼저 입력된 데이터가 먼저 출력되는 메모리 사용 방법
대기 행렬이라고 하며 FIFO 구조라고 함
데이터와 데이터 사이는 1:1 관계
프린터 스풀(Spool)이나 입출력 버퍼(Buffer)에 적합한 자료 구조
일상생활에서의 응용으로 은행에서 번호표 서비스에 가장 적합한 자료 구조
키보드를 입력하면 바로 CPU로 전달되지 않고 큐 구조의 버퍼에 대기했다가 CPU에 전달됨
인터넷에서 동영상을 실시간으로 받아보는 스트리밍 서비스에서 사용하는 버퍼도 큐 구조를 가지고 있음

3) 데크(Deque)

1. 데크의 구조

데이터를 저장하는 기억 장치가 양쪽 모두에 입출구가 있음
데이터의 입출력이 일어나는 위치를 왼쪽에서 가리키면 Left 포인터, 우측에서 가리키면 Right 포인터
두 포인터는 데이터가 입력되거나 출력될 때마다 1씩 증가하거나 1씩 감소함

2. 데크의 특징

가장 많이 사용하는 메모리 사용 방법
데이터가 메모리에 가득 차 있을 경우나 비어있을 경우 스크롤(Scroll) 또는 자체(Self) 방법을 이용하여 조절함
- 스크롤 : 출력은 양쪽에서 모두 가능하지만, 입력은 한쪽에서만 사용하는 방법
- 셀프 : 입력은 양쪽에서 모두 가능하지만, 출력은 한쪽에서만 사용하는 방법

4) 선형 리스트(Linear List)

1. 선형 리스트의 개념

배열(Array)과 같이 연속되는 기억 공간에 저장되는 리스트 구조
선형 리스트의 대표적인 구조는 배열이고, 대부분 선형 리스트는 배열이라고 지칭하기도 함
가장 간단한 구조이며 접근 속도가 빠름
중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 함
자료의 삽입, 삭제 시 자료의 이동이 필요하기 때문에 삽입, 삭제가 많은 처리에는 적당하지 않음
선형 리스트의 연속적인 공간이 모두 같은 유형이라면, 레코드(Record)는 연속적인 공간이 모두 다른 유형이라고 할 수 있음

2. 배열(Array)의 구조

같은 데이터 타입의 요소들이 동일한 크기로 순차적으로 나열되어 있는 집합
같은 이름을 사용하고 첨자에 의해 서로 구분되는 집단적인 데이터 저장 영역을 의미
같은 크기에 데이터를 연속적인 기억 장치에 저장하여 처리하는 구조
데이터의 크기와 유형이 같은 데이터 집단
따라서 데이터마다 변수 이름을 따로 두지 않아 처리가 훨씬 간편하다는 장점이 있음
배열 각각의 요소는 arr[i]로 표현
i를 첨자라고 하며, arr와 같은 요소의 묶음을 배열 이름이라고 함
배열은 첨자의 수에 따라 구분되는 데 첨자를 1개 사용하면 1차원 배열, 2개 사용하면 2차원 배열, 3개 사용하면 3차원 배열이라고 함

3. 배열의 특징

고정 크기의 메모리 공간을 사용
연속적인 기억 장치를 사용하므로 액세스 시간이 짧고 구조가 간단함
연속적인 공간을 사용하므로 중간에 삽입, 삭제가 어려움
주어진 데이터를 찾을 때 가장 좋은 방법
논리적인 순서와 물리적인 순서가 같음
같은 항목들의 집합으로 각 데이터마다 개별적인 변수를 사용하는 번거로움을 줄일 수 있음
1차원 배열, 2차원 배열, 3차원 배열은 모두 연속적인 공간에 존재하는 연접 리스트 구조(List Structure)

5) 연결 리스트(Linked List)

1. 연결 리스트의 개념

연결 리스트는 자료들을 선형 리스트처럼 연속으로 배열시키지 않고, 임의의 공간에 기억시키되 각 자료의 포인터를 이용하여 연결한 구조
자료의 삽입과 삭제가 용이함
기억 공간이 연속적이지 않아도 자료를 저장할 수 있음
다음 자료를 가리키기 위한 포인터 기억 공간이 추가적으로 필요함
연결을 위한 포인터를 찾는 시간이 필요하기 때문에 선형 리스트에 비해 느림

2. 연결리스트의 구조

데이터끼리 연결할 포인터를 포함해서 기억 장치를 구성
두 번째 데이터가 입력되면 첫 번째 데이터가 두 번째 데이터의 포인터를 기억하게 함

3. 연결 리스트의 특징

포인터를 포함한 자료 구조를 노드(Node)라고 하고, 노드에는 연결을 해주기 위한 포인터의 추가 공간이 필요함
포인터는 실제 데이터를 기억하는 공간이 아니므로 기억되는 실제 데이터의 수와 저장되는 저장 밀도를 고려해 노드를 설계해야 함
데이터의 삽입, 삭제가 가장 용이한 표현 방법
노드들이 포인터로 연결되어 있어 검색이 느림
중간 노드의 연결이 끊어지면 다음 노드를 찾기 힘듦
연결 리스트에 비하여 배열은 원소를 임의의 위치에 삽입하는 비용이 큼
연결 리스트에 비하여 배열은 임의의 위치에 있는 원소를 접근할 때 효율적

4. 연결 리스트의 종류

단일 연결 리스트(Single Linked List)
- 현재 노드에서 이전 노드로의 접근은 항상 리스트의 첫 번째 노드부터 다시 시작함
- 1개의 포인터를 사용하기 때문에 이중 연결 리스트보다는 기억 장소를 적게 차지함
- Atom의 위치를 나타내는 포인터가 오직 1개
  - Atom : 노드를 구성하고 있는 요소, 항목이지만 노드로 판단해도 무방함
- 논리적인 순서와 물리적인 순서가 다를 수 있음
- 노드의 삽입은 어디서든 이루어짐
- 마지막 노드의 포인터에는 NULL 값이 기억되어 있음
단일 환형 연결 리스트(Single Circular Linked List)
- 최종 노드의 포인터가 최초 노드를 가리키도록 구성되어 있음
- 1개의 포인터를 사용하기 때문에 이중 연결 리스트보다는 기억 장소를 적게 차지함
- Atom의 위치를 나타내는 포인터가 오직 1개
- 터미널 서비스에 사용되는 처리 방식의 라운드 로빈(Round Robin) 구조와 동일함
- 노드의 삽입은 어느 위치에서나 가능함
- NULL 포인터가 존재하지 않는 리스트 구조
이중 연결 리스트(Double Linked List)
- 한 노드에 2개의 포인터가 있음
- Atom의 위치를 나타내는 포인터가 2개
- 노드의 삽입과 제거가 쉬움
- 선행 노드를 찾는 데 매우 효율적
- 2개의 포인터를 사용하기 때문에 기억 장소를 많이 차지함
- 어떤 노드의 포인터가 파괴되었을 때 이를 복구할 수 있음
이중 환형 연결 리스트(Double Circular Linked List)
- 한 노드에 2개의 포인터가 있음
- Atom의 위치를 나타내는 포인터가 2개
- 노드의 삽입과 제거가 쉬움
- 오른쪽과 왼쪽 링크를 두고 양방향으로 탐색이 가능하도록 만든 연결 리스트
- 선행 노드를 찾는데 찾고자 하는 레코드를 다른 연결 리스트보다 쉽게 찾을 수 있음
- 2개의 포인터를 사용하기 때문에 기억 장소를 많이 차지함
- NULL 포인터가 존재하지 않는 리스트 구조
- 단순, 원형, 이중 연결 리스트의 메모리 요구 방법은 동일함

저작자표시 비영리 변경금지