[자료 구조] 2. 선형 자료 구조

[자료 구조] 2. 선형 자료 구조

 

(1) 선형 자료 구조: 한 줄로 자료를 관리하기

 

1-1. 배열(Array): 선형으로 자료를 저장한다.

-배열은 연속된 메모리 공간에 데이터를 저장하므로, 특정 인덱스에 직접 접근하여 데이터를 읽거나, 쓸 때 매우 효율적이다.

-배열의 크기를 변경하려면 데이터를 추가하거나, 삭제할 때마다 메모리의 다른 위치로 데이터를 이동시켜야 한다. 즉, 추가 및 삭제 작업이 많은 경우 배열을 사용하는 것이 비효율적이다.

-특정 위치에 새로운 데이터를 삽입하거나 삭제할 때에도, 데이터를 이동시켜야 하므로 작업이 번거롭다.

 

=> 배열은 검색이 자주 일어나고 데이터가 변경되지 않는 경우에 적합하다.

추가, 삭제, 수정이 잦은 경우에는 다른 자료 구조를 사용하는 것이 효율적이다!

 

1-2. 연결 리스트 (Linked List): 선형으로 자료를 관리하며, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결된다.

자료의 물리적인 위치와 논리적인 위치가 다를 수 있다.

=> 연결 리스트는 데이터의 추가, 삭제 속도가 배열보다 빠르다.

 

1-3. 스택(Stack): 가장 나중에 입력된 자료가 가장 먼저 출력되는 자료 구조이다. LIFO라고도 부른다. (Last In First Out)

-스택에서 자료를 추가할 때는 push라고 부른다. 삭제할 때(꺼낼 때)는 pop이라고 부른다.

 

 

1-4. 큐(Queue): 가장 먼저 입력된 자료가 가장 먼저 출력되는 자료 구조이다. (First In First Out)

-맨 앞의 자료를 front, 맨 뒤를 rear라고 부른다.

-자료를 추가할 때를 enqueue, 삭제할 때를 dequeue라고 부른다.