[자료구조 Java] 선형 자료 구조(연결 리스트, 배열, 스택, 큐)

선형자료구조란?

: 요소가 일렬로 나열되어 있는 자료 구조

1. 연결 리스트

: 데이터를 감싼 노드를 포인터로 연결해 공간적 효율성을 극대화 시킨 자료구조로,

prev 포인터와 next 포인터로 앞과 뒤의 자료들을 연결시킨 것

1-1. 시간 복잡도

- 삽입/삭제 : O(1)

- 탐색 : O(n)

1-2. 종류

1) 싱글 연결 리스트: next 포인터만 가짐

2) 이중 연결 리스트: prev, next 포인터를 둘 다 가짐

3) 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드(맨 앞의 자료)를 가리킴

1-3. 주요 명령어

import java.util.LinkedList;
import java.util.List;

public class Example {

	public static void main(String[] args) {
		
		List<Integer> numList = new LinkedList<>();
		
		// 1-1. 리스트의 맨 뒤에 데이터 추가하기.
		numList.add(3);
		numList.add(5);
		numList.add(8);
		numList.add(32);
		numList.add(100);
		System.out.println(numList.toString()); // [3, 5, 8, 32, 100]
		
		// 1-2. 리스트의 특정 위치에 데이터 추가하기.
		numList.add(2, 200);
		System.out.println(numList.toString()); // [3, 5, 200, 8, 32, 100]
		
		// 2. 리스트에서 특정 인덱스 데이터 삭제하기.
		numList.remove(0);
		System.out.println(numList.toString()); // [5, 200, 8, 32, 100]
		
		// 3. 리스트에서 특정 인덱스 조회하기.
		System.out.println(numList.get(2)); // 8
		
		// 4. 리스트의 크기 조회하기.
		System.out.println(numList.size()); // 5
		
		// 5. 리스트에 특정 값이 있는지 조회하기.
		System.out.println(numList.contains(200)); // true
		
	}
}

2. 배열

: 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합

2-1. 시간복잡도

- 탐색 : O(1) ▶︎ 물리적 인덱스를 알고 있으며 한 번에 접근 가능(random access)
- 삽입/삭제 : O(n) ▶︎ 맨 앞의 자리를 삽입/삭제할 경우, 다른 원소들을 한 칸씩 shift해야하는 비용이 발생

📍랜덤접근과 순차접근
- 랜덤접근(직접접근): 동일한 시간에 배열과 같은 순차적 데이터가 있을 경우 임의의 인덱스에 해당하는 데이터에 바로 접근 가능
- 순차접근: 데이터를 저장된 순서대로 검색해야만 접근 가능

✅ 배열과 연결리스트 비교

구분	배열	연결리스트
크기	정적으로 정해져 있음	동적으로 변화
요소 탐색	인덱스를 알고 있을 경우 바로 접근 가능	처음부터 순차적으로 탐색해야 함
삽입/삭제	요소 삽입/삭제 시 다른 요소들 위치 조정 필요	인덱스를 알고 있을 경우 바로 해당 위치에 삽입/삭제 가능
메모리	필요한 만큼 확보하므로 공간 효율적	포인터의 여분 메모리가 필요

3. 스택

- 입력과 출력이 한 곳으로 제한 되어 있어,
   LIFO(Last In First Out) 성질을 가진 자료구조로, 가장 마지막에 들어간 데이터가 가장 첫 번째로 나옴
- 차곡차곡 데이터가 쌓이는 자료구조

3-1. Stack의 활용

- 함수의 콜스택(함수의 실행 컨텍스트가 호출된 순서로 스택 메모리 공간에 쌓임), 재귀 알고리즘

- 문자열 역순 출력
- 후위 표기법 변환 및 연산
- 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)
- 웹 브라우저 방문 기록(뒤로 가기), 실행 취소(undo)

3-2. 시간 복잡도

- 삽입/삭제 : O(1) ▶︎ 맨 위를 기준으로만 데이터의 삽입/삭제가 가능하므로 항상 O(1) 의 시간복잡도를 가짐

- 탐색 : O(n) ▶︎ 특정 데이터를 찾을 경우, 그 데이터를 찾을 때까지 수행해야하므로 최대 O(n)의 시간 복잡도를 가짐

3-3. 주요 연산

- push(item): TOP에 자료(item) 삽입

- pop(): TOP에 있는 자료 제거

- peek(): TOP에 있는 자료 반환

- isEmpty(): 스택이 비어 있을 때 true 반환

4. 큐

- 선입선출 형태로 먼저 집어 넣은 데이터가 먼저 나오는 (FIFO, First In First Out) 성질을 가진 자료 구조

- Java Collection에서의 Queue는 인터페이스로, 이를 구현하고 있는 Priority Queue등을 사용할 수 있음

3-1. Queue의 활용

- 데이터가 입력된 순서대로 처리해야 할 필요가 있는 상황에 용이 (BFS)

- 캐시 구현

- 우선 순위가 같은 작업 예약(인쇄 대기열)

- 선입 선출이 필요한 대기열 (티켓 카운터)

- 콜센터 고객 대기 시간

- 프린터의 출력 처리

- 윈도우 시스템의 메시지 처리기

- 프로세스 관리

- JS의 Event loop 관리에 필요(비동기 처리)

3-2. 시간 복잡도

- 삽입/삭제 : O(1) ▶︎ 삽입은 맨 뒤에서, 삭제는 맨 앞에서만 가능하므로 항상 O(1) 의 시간복잡도를 가짐

- 탐색 : O(n) ▶︎ 특정 데이터를 찾을 경우, 그 데이터를 찾을 때까지 수행해야하므로 최대 O(n)의 시간 복잡도를 가짐

3-3. Queue의 주요 연산

- add(item): item을 큐 리스트의 끝 부분에 추가한다.

- remove(): 리스트의 첫 번째 항목을 제거한다.

- poll(): 리스트의 첫 번째 항목을 제거한 후, 해당 값을 반환한다.

- peek(): 큐에서 가장 앞에 있는 항목을 반환한다. (front)

- isEmpty(): 큐가 비어 있을 때 true를 반환한다.