#자료구조의 분류 #선형리스트(Linear List) #연속리스트, 연결리스트 #노드(Pointer)
자료구조의 분류
효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다. 자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의관계, 처리 방법 등을 연구 분석하는 것을 말한다.
① 자료 구조의 분류
② 선형 리스트(Linear List)의 형태
* 연속리스트(Contiquous List) - 배열(Array)과 같이 연속되는 기억장소에 저장되는 자료구조 - 밀도가 1로서(연속적) 가장 좋다 - 데이터 삽입을 위해서 연속된 빈 공간이 있어야 하며 삽입/삭제시 자료 이동 필요
* 연결리스트(Linked List)
위 그림 에서 "연결리스트, 노드(Pointer)" 부분을 보면, 요일은 순차적이지 않은 형태로 리스트에 배치되어있다. 처음 노드 가 시작되는 시작점인 "월요일"의 위치와 관계없이 월요일에 연결된 노드(2) 를 따라 2번째 칸의 화요일로 이동하고, 그 다음은 화요일이 가리키는 노드(6)을 따라 6번째 칸의 수요일로 이동되며 월->화->수->목->금->일(^) 까지 차례대로 이동할 수 있음을 알 수 있다.
- 배열X 임의의 기억공간에 기억, 순차적이지 않음 - 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간 효율 안좋음 - 접근속도 느림
* 스택(Stack) - 한쪽 끝으로만 자료 삽입/삭제 - 가장 나중에 삽입된 자료(TOP)가 가장 먼저 삭제되는(Last in First Out) 방식으로 자료 처리 - 데이터가 꽉 채워진 상태에서 삽입(Push)되면 오버플로우(Overflow) 발생 - 데이터가 다 비워진 상태에서 삭제(Pop)되면 언더플로우(Underflow) 발생
* 큐(Queue) - 한쪽에서는 삽입, 다른 한쪽에서는 삭제 - 가장 먼저 삽입된 자료가 가장 먼저 삭제되는(First in First Out) 방식으로 자료 처리 - 가장 먼저 삽입된 자료(Front)과 가장 마지막에 삽입된 자료(Rear)를 가리키는 두 개의 포인터 존재 - 프론트 포인터는 삭제 작업시, 리어 포인터는 삽입 작업을 할 때 사용 - 운영체제의 작업 스케쥴링에 사용
