[자료구조]선형 구조의 종류와 설명

선형구조란?

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

자료를 구성하는 원소들을 순차적으로 나열시킨 형태

 

선형구조의 종류

1. 선형 리스트(Linear List) ex) 배열(Array)

연속적인 기억공간에 배정하며 각 요소들은 동일 데이터 타입으로 <인덱스, 값>의 쌍으로 표현된다.

정적인 데이터타입으로 배열의 크기는 한번 정하면 크기를 변경 할 수 없다. (데이터 낭비가 될 수 있음!)

 

특징

   · 가장 간단한 자료구조

   · 접근 속도가 빠름

   · 기억장소를 연속으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋음

   · 자료의 개수가 n개 일때, 삽입시 평균 이동 횟수 : n+1/2, 삭제시 평균 이동 횟수 : n-1/2  

   · 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거로움

 

2. 연결 리스트(Linked List)

자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억 공간에 기억시키되, 자료항목의 순서에 따라

노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조이다.

동적인 데이터타입으로 한 노드당 4Byte의 크기를 가지고 있다.

 

특징

 · 삽입, 삭제 작업이 용이하다.

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

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

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

 

 

3. 스택(Stack)

가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO : Last In First Out)구조로 저장하는 형식

특징

 · 자료의 삽입, 삭제 작업이 한쪽 방향에서만 이루어지는 자료구조

 · 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO : Last-In, First-Out)방식으로 처리

 · T(TOP Pointer) - 스택 포인터(SP)라고도 함. Stack으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 공    간을 가리키는 요소

 

메서드

· pop(): 스택에서 가장 위에 있는 항목을 제거한다.
· push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
· peek(): 스택의 가장 위에 있는 항목을 반환한다.
· isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

 

4. 큐(Queue)

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO : First In First Out)

구조로 저장하는 형식

 

특징

선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조

· 큐(Queue)는 연결리스트 로 구현할 수 있다.

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

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

 

메서드

· add(item): item을 리스트의 끝부분에 추가한다.
· remove(): 리스트의 첫 번째 항목을 제거한다.
· peek(): 큐에서 가장 위에 있는 항목을 반환한다.
· isEmpty(): 큐가 비어 있을 때에 true를 반환한다.