자료구조

정의

효율적인 프로그램 작성 시, 가장 고려해야 할 점은 저장공간의 효율성과 실행시간의 신속성

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

자료구조의 정의

1. 자료의 표현과 그것과 관련된 연산
2. 일련의 자료들을 조직하고 구조화
3. 어떠한 자료 구조에서도 필용한 모든 연산들을 처리
4. 자료구조에 따라 프로그램 실행시간이 달라진다.

분류

선형구조와 비선형구조로 구분

선형 구조

• Linear Structure
• 배열, 선형 리스트 (연결 리스트, 연속 리스트), 스택, 큐, 데크,

비선형 구조

• Non Linear Structure
• 트리, 그래프

배열 (Array)

동일한 자료형의 데이터들이 같은 크기로 나열

순서를 갖고 있는 집합

• 정적인 자료 구조
  • 기억장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장됐던 기억장소는 빈 공간으로 남아있어 메모리 낭비 발생
• 첨자, 인덱스를 활용해서 데이터에 접근
• 반복적인 데이터 처리 작업에 적합한 구조
• 데이터마다 동일한 이름의 변수를 사용해야 처리가 간편
• 사용한 첨자의 개수에 따라 n차원 배열

선형 리스트 (Linear List)

배열을 이용하는 연속 리스트 와 포인터를 이용하는 연결 리스트

연속 리스트 (Contiguous List)

• 연속되는 기억공간에 저장
• 기억장소 이용효율은 밀도가 1 로 가장 좋다.
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 필요
  • 삽입, 삭제 시 자료의 이동이 필요

연결 리스트 (Linked List)

• 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간에 기억

  • 자료 항목의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시킨 자료구조

• 노드의 삽입, 삭제가 용이

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

• 연결을 위한 포인터가 필요

  • 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.

  • 접근 속도가 느리다.

• 중간 노드가 끊어지면 그 다음 노드를 찾기 힘들다.

스택 (Stack)

리스트의 한쪽 끝으로만 삽입, 삭제

• LIFO (Last In First Out) 방식

  • 가장 나중에 삽입된 자료가 가장 먼저 삭제

• 오버플로우 : 꽉 차있는 상태에서 새로운 자료를 삽입할 때

• 언더플로우 : 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제할 때

• TOP : 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치

• BOTTOM : 스택의 가장 밑바닥

큐 (Queue)

리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제

• FIFO (First In First Out)
  • 가장 먼저 삽입된 자료가 먼저 삭제
• 시작과 끝을 표시하는 두개의 포인터가 존재
• Front 포인터
  • 가장 먼저 삽입된 자료의 기억공간울 가리키는 포인터
  • 삭제 작업에 용이
• Rear 포인타
  • 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터
  • 삽입 작업에 용이

Tree (트리)

정점 (Node), 선분 (Branch) 을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수 형태

• 노트 : 하나의 기억 공간
• 링트 : 노드와 노드를 연결하는 선
• 가족의 계보, 조직도를 표현하기에 적합
• Node : 트리의 기본 요소. 자료항목과 다른 항목에 대한 가지를 합친 것
• Root Node : 트리의 맨 위에 있는 노드
• Degree : 각 노드에서 뻗어 나온 가지의 수
• Leaf Node, Terminal Node : 자식이 하나도 없는 노드, Degree가 0인 노드
• Son Node, 자식 노드 : 어떤 노드에 연결된 다음 레벨의 노드들
• Parent Node, 자식 노드 : 어떤 노드에 연결된 이전 레벨의 노드들
• Brother Node, Sibling, 형제 노드 : 동일한 부모를 갖는 노드들
• Tree의 Degree : 노드들의 디그리 중에서 가장 많은 수