[자료구조 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를 반환한다.