정보처리기사 선형 자료구조 종류 스택, 큐, 데크, 선형리스트, 링크드리스트 stack, queue, deque, linear list, linked list

 

 

what is linear data structure?

 

 

1. 스택 Stack

• 스택의 구조
  - 데이터의 입구와 출구가 같다
  - 삽입과 삭제가 한쪽에서만 일어나는 자료구조다
  - 스택 포인터가 가장 마지막에 삽입된 데이터의 위치를 가리킨다
  - 스택 포인터는 데이터가 삽입(PUSH)될 때 마다 1씩 증가한다
  - 스택 크기를 넘어서게 되면 스택오버플로우(stack overflow) 오류를 반환한다
  - 스택 포인터는 데이터를 추출(POP)할 때 마다 1씩 감속한다, 0보다 작아지면 스택 언더플로우(Stack Underflow)오류를 반환한다
• 스택의 특징
  - 가장 나중에 삽입된 데이터가 가장 먼저 추출되는 후입선출(LIFO) 방식이다
  - 프로그램의 함수 호출, 깊이 우선탐색, 재귀 호출, Linear List, POST-fix등에 사용된다
  - 0-주소 명령어 방식에서 활용된다

2. 큐(Queue)

• 큐의 구조
  - 데이터의 입구와 출구가 달라서 삽입과 삭제가 반대쪽에서 일어나는 자료구조
  - 삽입 포인터가 저장된 데이터중 가장 마지막에 삽입된 데이터의 위치를 가리킨다
  - 삽입 포인터는 데이터가 입력될 때마다 1씩 증가하며 큐의 크기를 넘어서게 되면 오류(Overflow)를 발생시킨다
  - 삭제 포인터가 저장된 데이터 중 가장 처음에 삽입된 데이터의 위치를 가리킨다
  - 삭제 포인터는 데이터를 삭제할 때마다 1씩 증가하며 삽입 포인터와 같은 위치를 가리키게 되며 큐에 데이터가 비어있는 상태를 의미한다 
• 큐의 특징
  - 가장 먼저 삽입된 데이터가 가장 먼저 출력되는 선입선출(FIFO) 방식이다
  - 프린터 스풀이나 입출력 버퍼와 같은 대기 행렬에 적합한 자료구조다

3. 데크(Deque)

• 데크의 구조
  - 데이터의 출입구가 양쪽 모두에 있는 구조다
  - 각각의 포인터(Left, Right)가 데이터 삽입, 삭제에 따라 1씩 증가하거나 감소한다
• 데크의 특징
  - 입출력 제한 유형에 따라 스크롤 방식과 쉘프 방식이 있다
  - 입력 제한 데크(Scroll): 출력은 양쪽에서 가능하지만 입력은 한쪽에서만 가능하다
  - 출력 제한 데크(Shelf): 입력은 양쪽에서 가능하지만 출력은 한쪽에서만 가능하다

4. 선형 리스트

• 선형리스트 특징
  - 동질형 데이터(같은 유형의 데이터)가 연속되는 기억공간에 저장되는 데이터구조다
  - 가장 간단한 구조이며, 접근 속도가 비교적 빠르다
  - 삽입, 삭제 시 나머지 자료들의 이동이 필요하기 때문에 시간이 오래걸린다
  - 선형 리스트의 대표적인 구조에는 배열(Array)이 있다
• 배열의 특징
  - 같은 데이터 타입의 요소들이 같은 크기의 공간에 순차적으로 나열되어 있는 구조다
  - 같은 이름을 사용하고 첨자(데이터의 상대적인 위치를 구분하는 값)에 의해 서로의 위치를 구분한다
  - 첨자를 2개 이상 사용하면 다차원 배열이라고 한다
  - 고정 크기의 메모리 공간을 사용하며 논리적인 순서와 물리적인 순서가 같다
  - 데이터 탐색에 가장 효과적인 자료구조다
  - 배열의 데이터삽입
      1) 배열의 중간에 데이터를 삽입하는 경우엔 삽입될 위치부터 오른쪽에 있는 모든 요소가 한칸씩 오른쪽으로 이동
      2) 데이터의 수를 N이라고 할 때, 평균 이동횟수 = (N+1)/2
• 배열의 데이터 삭제
  - 배열의 중간에 위치한 데이터를 삭제하는 경우엔 삭제될 위치의 오른쪽에 있는 모든 요소가 한칸씩 왼쪽으로 이동
  - 데이터의 수를 N이라고 할 때, 평균 이동횟수 = (N-1)/2

 

5. 연결리스트(Linked List)

• 연결리스트의 특징
  - 데이터의 삽입과 삭제가 어려운 배열의 단점을 보완한 자료구조다
  - 다음 데이터의 위치를 첨자를 사용한 상대적 위치값으로 구분하는 것이 아니라 데이터마다 포함된 포인터를 이용해 가리킨다
  - 데이터의 삽입과 삭제가 용이하며 기억 공간이 연속적이지 않아도 문제가 없다
  - 데이터마다 포인터가 필요하므로 기억 공간이 추가로 필요하며 탐색 속도는 비교적 느린편이다
• 연결 리스트의 구조
  - 데이터와 포인터를 묶어서 노드라고 표현한다
  - 임의의 기억 공간에 생성된 노드들이 각 노드의 포인터에 의하여 연결된다
  - 중간 노드의 연결이 끊어지면 다시 복구할 수 없다
• 연결 리스트의 종류
  - 단일 연결리스트
     * 1개의 포인터를 사용하여 자신의 다음 노드의 위치를 기억한다
     * 마지막 노드의 포인터는 NULL값을 가진다
     * 노드의 접근은 항상 첫 노드부터 다시 시작해야 한다
     * 노드의 포인터가 훼손되면 복구가 거의 불가능하다
  - 단일 원형 연결리스트(Single Circular Linked List)
     * 1개의 포인터를 사용하여 자신의 다음 노드의 위치를 기억한다
     * 마지막 노드는 첫 노드의 위치값을 가지므로 NULL값을 갖지 않는다
     * 어떤 노드에서 시작해도 전체 노드를 탐색할 수 있다
     * 노드의 포인터가 훼손되면 복구가 거의 불가능하다
  - 이중 연결리스트(Double Linked List)
     * 2개의 포인터를 사용하여 자신의 다음 노드와 이전 노드의 위치를 기억한다
     * 2개의 포인터를 사용하기 때문에 기억장소를 많이 차지한다 
     * 탐색의 방향을 바꾸어 이전 노드를 탐색할 수 있다
     * 특정 노드의 포인터가 훼손되었을 때 복구의 가능성이 있다
     * 첫 노드의 포인터와 마지막 노드의 포인터는 NULL 값을 가진다
  - 이중 원형 연결 리스트(Double Circular Linked List)
     * 2개의 포인터를 사용하여 자신의 다음 노드와 이전 노드의 위치를 기억한다
     * 2개의 포인터를 사용하기 때문에 기억장소를 많이 차지한다
     * 탐색의 방향을 바꾸어 이전 노드를 탐색할 수 있다
     * 특정 노드의 포인터가 훼손되었을 때 복구의 가능성이 있다
     * 첫 노드의 포인터와 마지막 노드의 포인터는 각각 마지막 노드와 첫 노드의 위치값을 가지므로 NULL값을 가지지 않는다