1.자료구조
(1)자료구조의 정의
①자료를 효율적으로 사용하기 위해 컴퓨터로 자료의 특성에 따라 분류하여 구성하고, 저장 및 처리하는 모든 작업을 말한다.
②문제 해결을 위해 데이터 값들을 연산자들이 효율적으로 접근하여 처리할 수 있도록 체계적으로 조직하여 표현하는 것을 말한다.
③컴퓨터에서 자료를 정리하고 효율적으로 사용할 수 있도록 다양한 구조를 갖는 것이 자료구조이다.
(2)자료구조의 구성
①선형구조
-개념: 데이터 전후 항목 사이 관계가 1:1이며, 선후 관계가 명확하게 한 개의 선의 형태를 갖는 리스트 구조이다.
-선형 구조의 종류: 배열, 연결 리스트, 스택, 큐, 데크
②비선형구조
-개념: 데이터 항목 사이의 관계가 1:n ( 혹은 n:m)인 그래프적 특성을 갖는 형태이다.
-비선형구조의 종류: 트리, 그래프
(3)자료구조 선택 시 고려사항
데이터 양, 데이터 특성, 데이터 활용빈도, 사용 시스템의 기억용량, 처리시간(최선, 최악, 평균), 프로그램 난이도, 데이터 저장방식 등이 있다.
2.선형구조
(1)배열(array)
①동일한 성질을 갖는 자료의 집합으로서 색인(index)과 값(value)의 쌍으로 구성된 순차적인 자료구조를 말한다.
②일반적으로 프로그래밍 언어에서는 변수의 확장에 해당하는 것으로 유사한 성격, 즉 동일한 자료형으로 이루어진 많은 자료를 처리할때 사용한다.
③동일한 자료형을 갖는 자료들의 리스트(list)를 배열이라 하며, 순서에 해당하는 배열의 각각의 요소들은 하나의 변수로 취급된다.
④같은 자료형의 값들이 순서적으로 하나의 이름(배열명)에 모여 있는 것으로서 각각의 자료들을 원소라 하며, 이들은 배열명과 첨자로 구분된다.
⑤배열은 선언형태, 즉 첨자의 개수에 따라 1차원 배열, 2차원 배열, 3차원 배열 등이 있다.
(2)연결 리스트(linked list)
①노드를 크게 데이터 필드와 링크 필드로 나누어 다음 노드가 기억된 공간의 주소를 이전 노드의 링크 필드에 기억시키는 방식으로 모든 노드들을 하나로 연결하는 리스트를 말한다.
②각 노드는 데이터 필드와 링크 필드로 구성되며, 연결 리스트는 첫 번째 노드를 가리키는 포인터가 필요한데, 이를 헤드라고 한다.
③링크 필드에는 다음 노드가 기억된 주소(포인터)가 수록되며, 가르키는 노드가 없는 노드의 포인터를 Null(또는 Nil)이라 한다.
④각 노드는 포인터를 통해 연결되므로 기억장소에서 서로 이웃하지 않아도 된다.
⑤장점: 노드의 삽입/ 삭제 작업이 용이하고 기억공간이 연속되지 않아도 저장할 수 있음, 희소행렬을 연결 리스트로 표현 시 기억장소가 절약됨
단점: 포인터 저장을 위한 기억장소가 추가로 요구되므로 기록 밀도가 낮고, 임의의 문자를 접근하기 위해서는 처음부터 순차 탐색을 해야 함
⑥단순 연결 리스트: 하나의 링크 필드를 이용하여 연결하며, 마지막 노드의 링크 값은 null을 가지는 리스트를 말한다.