정보처리기사 필수 학습: 선형구조 완전 정복!

자료 구조

1. 자료구조의 정의

데이터를 효율적으로 관리,사용,저장 하는 시스템

자료구조의 특징

• 효율성
• 추상화
• 재사용성

자료구조의 구조

 

분류	설명
선형구조	- 데이터를 연속적으로 연결한 구조 (배열같은거)
비선형구조	- 데이터를 비연속적으로 연결한 구조 - 하나의 자료 뒤에 여러개의 자료가 존재할수있다. (트리,그래프)

 

선형구조

배열

• 메모르 상에 데이터를 연속으로 배치한거
• 자료공간 크기같음
• 고유한이름은 없고 물리적 순서와 동일

리스트

• 선형 리스트  = 배열같은거 인덱스 사용 

 

장점	- 가장 간편함 - 저장 효율 뛰어남 - 접근 속도 빠름
단점	- 자료의 삽입 삭제가 어려움(위치 찾아야함,하나 지우면 다이동됨 index)

 

• 연결 리스트 : 하나의 자료에 데이터와 링크를 가진형태

장점	- 자료의 삽입 및 삭제가 용이 (중간에 삭제되도 연결하면됨) - 희소행렬을 표현할떄 좋다.
단점	- 데이터 접근시 시간이 필요해서 느림 - 포인터를 위한 추가공간이 필요 - 중간에 연결이 끊어지면 다음 노드 찾기가 힘들다

분류	설명
단순 연결 리스트	- 한방향으로 앞에서 뒤로만 연결된 리스트 마지막 노드의 link  값은 null
단순 연결 환형리스트	- 끝노드가 제일 앞의 노드를 가르킨다 (순환선 노선같은거)
이중 연결 리스트	- 각노드는 앞뒤 정보를 가지고있는다 마지막 노드의 link  값은 null
이중 연결 환형리스트	- 앞뒤정보가지고 있고 순환하는애

 

• 스택: 한쪽 끝에서만 자료의 삽입과 삭제가 이뤄지는 구조(push - 삽입 , pop - 삭제)
• 후입선출 (아래 이미지처럼 통에 넣으니까 마지막으로 넣은게 삭제하면 제일먼저나감)
• top 포인터가 0 이나 -1 로 설정해 push 하면 +1 Pop하면 -1 

분류	설명
Overflow	- 스택이 가득차서 있을떄  push 하면 발생
Underflow	- 스택이 비어있을떄 pop 하면 발생
스택의 용도 ★	인터럽트처리/수식의계산/서브루틴의 복귀번지저장,웹브라우저 방문기록,재귀호출,깊이우선탐색

탑 포인트에서 삽입할떈 먼저 더하고 데이터 

뺼떈 데이터 뺴고나서 탑포인트 뻄

 

 

• 큐 :  한쪽 끝에서 삽입이 이루어지고 반대쪽끝에서 삭제가 이뤄짐 (한줄 줄서기)
• 선입 선출 구조,FIFO(먼저 in 먼저  out)
• 삽입은 enQeue ( Rear  포인터이용), 삭제는 deQeue(Front 포인터이용)

 

• 데크 : 양쪽방향으로 입출력이 발생하는구조
• 스택과 큐 반반 섞음
• Scroll(입력제한데크) : 입력이 한쪽에만 일어나고 출력은 양쪽
• Sheif(출력제한데크) 입력은 양쪽 출력은 한쪽