[Data Structure] 선형 자료구조

참고 :
https://uuukpyo.tistory.com/3
https://wpunch2000.tistory.com/28

 

1. 선형 구조란?

선형구조란, 데이터를 연속적으로 연결하는 방법이다. 자료의 원소들을 순서대로 나열한 형태로 앞뒤 관계가 명확하다.

대표적인 선형 구조에는 배열, 연결된 리스트, 스택, 큐, 덱이 있다.

 

2. 배열 (Array)

변수 이름으로 같은 타입을 가진 데이터들을 모아놓은 집합체이다.

• 가장 간단하고 접근 속도가 빠름
• 배열의 크기는 한 번 지정한 후 변경할 수 없기 때문에 비효율적
• 인덱스 가지고 있음 (접근 시간 : O(1))
• 순차적으로 데이터가 삽입, 삭제

 

3. 연결된 리스트 (Linked List)

자료항목의 순서에 따라 노드(node, 리스트의 데이터)들이 포인터로 연결된 구조이다. 

• 링크 필드의 조정으로 삽입, 삭제 작업이 용이
• 접근 속도가 느림 (O(n))
• 논리적 순서 ≠ 물리적 순서
• 중간 노드 연결이 끊어지면 그 다음 노드 찾기가 힘듦

 

4. 스택 (Stack)

LIFO (Last In First Out) 형태의 선형 리스트이다. 즉, 가장 먼저 입력된 데이터가 가장 뒤에 출력된다.

• 삽입, 삭제가 한 방향에서만

• pop() : 가장 위에있는 데이터를 빼내서 출력 (top이 한 칸 아래로)
• push() : top이 가리키는 위치에 데이터 삽입 (top을 한 칸 위로)
• peek() : 가장 위에 있는 데이터를 빼내지않고 출력
• isEmpty() : 스택이 비어있을 경우 true

 

5. 큐 (Queue)

FIFO (First In First Out) 형태의 선형 리스트이다. 즉, 가장 먼저 입력된 데이터가 가장 먼저 출력된다.

• 한 쪽에서는 삽입, 한 쪽에서는 삭제
• 삭제 포인터 : front / head, 삽입 포인터 : rear / tail
• 대기행렬처리, 운영체제 작업 스케줄링에 사용됨

• add(x) : x을 리스트 끝부분에 추가
• remove() : 첫번째 항목 제거
• peek() : 맨 위 항목 반환
• isEmpty() : 큐가 비어있을 경우 true

 

6. 덱 (Deque)

양방향에서 삽입과 삭제가 가능한 큐이다. 스택과 큐의 특징을 갖춘 자료구조라고 볼 수 있다.

• push_front(x) : 첫 번째 위치에 x 삽입
• push_back(x) : 마지막 위치에 x 삽입
• pop_front() : 첫 번째 위치의 데이터 삭제
• pop_back() : 마지막 위치의 데이터 삭제
• front() : 첫 번째 요소 조회
• back() : 마지막 요소 조회

• 캐시 구현 등에 사용됨

감사합니다 ผ(•̀_•́ผ)