선형구조와 비선형구조

자료구조는 크게 3가지 선형 구조, 비선형 구조, 파일 구조로 분류할 수 있는데

이번 글에서는 선형구조와 비선형구조의 자료구조 특징을 알아보자 ㄱㄱ

 

 

1. 선형구조

- 배열(선형 리스트), 연결 리스트, 스택, 큐, 데크

- 데이터가 연속적으로 연결되어 있는 모양으로 구성하는 방법

- 포인터 등을 사용하여 자료를 연결하면 그 결과가 자료에 일직선상에 표시되거나 하나의 원상에 표시되는 구조

 

 

a) 연결리스트

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

- 노드의 삽입, 삭제 작업이 용이하다

- 기억공간이 연속적으로 놓여있지 않아도 저장이 가능하다

 

- 접근 속도가 느리다 (포인터를 찾아가는 시간이 필요하기 때문에 배열에 비해 접근속도 느림)

- 중간 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들다

 

b) 스택

- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조

- LIFO / 인터럽트가 발생하여 복귀주소를 저장할 때 사용

 

c) 큐

- 한쪽에서는 삽입 작업이, 다른 쪽에서는 삭제 작업이 이루어지도록 구성

- 시작과 끝을 표시하는 두 개의 포인터가 있다

- 창구 업무처럼 서비스 순서를 기다리는 등의 대기 행렬 처리에 사용

 

d) 데크(DEQ : Double Ended Queue)

- 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조

- 스택과 큐의 장점만 따서 구성한 것

- 입력이 한쪽하서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력제한,

  입력은 양쪽에서 일어나고 출력이 한쪽에어만 이루어지는 출력제한이 있다

 

---

2. 비선형구조

a) 트리

- 정점(node)와 선분(brabch)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 형태

- 방향성이 있다 (부모와 자식 계층 구조가 명확)

 

b) 그래프

- 정점(node)와 선분(brabch)을 이용하여 사이클을 이루도록 구성

- 순환이 된다