자료구조

 

목차

 

 

1. 자료 구조

1) 자료 구조 란?

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

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

(1) 단순 구조 (Simple)

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

(2) 선형 구조 (Linear)

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

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

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

(4) 파일 구조 (File)

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

2. 선형 구조

스택 (Stack) , 큐 (Queue) , 데크 (Deque) , 선형 리스트 (Linear List) , 연결 리스트 (Linked List)

1) 스택 (Stack)

stack

(1) 스택의 구조

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

(2) 스택의 특징

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

2) 큐 (Queue)

queue

(1) 큐의 구조

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

(2) 큐의 특징

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

3) 데크 (Deque)

deque

(1) 데크의 구조

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

(2) 데크의 특징

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

4) 선형 리스트 (Linear List)

(1) 선형 리스트의 개념

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

(2) 배열 (Array) 의 구조

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

(3) 배열의 특징

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

(4) 배열로 구현하는 연결 리스트

• 필요한 노드 (Node ) 수를 예측하기 어렵기 때문에 배열의 크기를 실제 양보다 크게 잡는다.
  • 노드 (Node) -- 자료구조에서 노드는 레코드(튜플) 한 줄 , 한 행 , 하나의 데이터 구조를 의미
• 배열 내에 선언된 노드들은 프로그램이 수행되는 동안 계속 할당된다.
• 정적 메모리 할당 방법을 사용하여 메모리 효율이 떨어진다.
  • 정적 메모리 할당 : 배열처럼 레코드의 개수를 미리 선언하면 그 개수를 변경하지 못하는 할당방법
  • 동적 메모리 할당 : 연결 리스트 처럼 데이터가 발생할 때마다 레코드를 생성하여 연결하는 할당 방법

5) 연결 리스트 (Linked List)

(1) 연결 리스트의 개념

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

(2) 연결 리스트의 구조

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

(3) 연결 리스트의 특징

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

(4) 연결 리스트의 종류

• 단일 연결 리스트 (Single Linked List)
• 단일 환형 연결 리스트 (Single Circular Linked List)
• 이중 연결 리스트 (Double Linked List)
• 이중 환형 연결 리스트 (Double Circular Linked List)

3. 비선형 구조