자료구조
- 탐색, 삽입, 삭제 등 데이터를 효율적으로 관리하기 위한 데이터 집합
- 시간 복잡도, 공간 복잡도를 고려하여 자료 구조의 효율성을 나타냄
- 시간 복잡도 : input 대비 걸리는 시간
- 공간 복잡도 : 프로그램 실행 시 필요로 하는 자원 공간의 양
- 대표적인 자료구조
- 선형 자료 구조 :
배열(Array)연결 리스트(Linked List)벡터(vector)스택(Stack)큐(Queue) - 비선형 자료 구조 :
그래프(Graph)트리(Tree)
- 선형 자료 구조 :
선형 자료구조
- 요소가 일렬로 나열된 자료 구조
1️⃣ 배열(Array) | 접근(참조): O(1) 삽입, 삭제: O(n)
- 동일 타입 변수들의 집합 | 같은 타입의 데이터만 저장할 수 있음
- 크기가 정적임 ㅣ 한 번 생성된 배열은 길이를 늘리거나 줄일 수 없음
- 중복 허용, 인덱스 사용(순서o), 연속적인 메모리구조
순차적 접근과랜덤 접근모두 가능
💬 순차적 접근이란 앞뒤의 요소를 거쳐서 타겟 요소에 접근하는 방식이고, 랜덤 접근이란 말그대로 랜덤으로(앞뒤 요소를 거치지 않고) 접근할 수 있는 방식이다. 반복문으로 모든 요소를 순회하는건 순차 접근의 예시이고, 인덱스를 사용하여 요소값을 조회하는 것이 랜덤 접근이 예시이다.
배열은 다음과 같이 사용한다.
public class ArrayExample {
public static void main(String[] args) {
int[] scores = {83, 90, 83, 93, 78, 75};
for (int i = 0; i < scores.length; i++) {
System.out.println("인덱스 " + i + "의 값: " + scores[i]); // {83, 90, 83, 93, 78, 75}
}
scores[2] = 95;
System.out.println("\n변경 후 인덱스 2의 값: " + scores[2]); // {83, 90, 95, 93, 78, 75}
}
}💡배열은 랜덤 접근이 가능하여 참조(탐색)에는 O(1)의 시간복잡도가 소요되지만 메모리 구조가 연속적이기 때문에 삽입,삭제에는 O(n)의 시간복잡도가 발생한다.
2️⃣ 연결 리스트(Linked List) | 탐색: O(n) 삽입, 삭제: O(n) or O(1)
-
데이터를 감싼 노드를 포인터로 연결하는 자료 구조, 비연속적 메모리구조 → 유연한 메모리 삽입, 삭제 가능
- 싱글 연결 리스트 :
next포인터만 가짐 - 이중 연결 리스트 :
next,prev포인터를 가짐 - 원형 이중 연결 리스트 : 이중 연결 리스트 + 마지막 노드의 next 포인터가 head 노드를 가리킴
- 싱글 연결 리스트 :
-
LinkedList 노드 구현
public class LinkedList {
// 첫번째 노드를 가리키는 필드
private Node head;
private Node tail;
private int size = 0;
private class Node{
private Object data; // 데이터가 저장될 필드
private Node next; // 다음 노드를 가리키는 필드
public Node(Object input) {
this.data = input;
this.next = null;
}
}
}- 첫번째 요소 추가
public void addFirst(Object input) {
Node newNode = new Node(input);
newNode.next = head;
head = newNode;
size++;
if(head.next == null) {
tail = head;
}
}- 마지막에 요소 추가
public void addLast(Object input) {
Node newNode = new Node(input);
if(size == 0) {
addFirst(input);
}else {
tail.next = newNode;
tail = newNode;
size++;
}
}- 중간에 요소 추가
public void add(int index, Object input){
if (index < 0 || index > size){
throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
}
if (size == 0){
addFirst(input);
return;
}
if (index == size){
addLast(input);
return;
}
Node newNode = new Node(input);
Node temp = head; // 삽입할 위치 이전 노드 찾기 위해 head부터 반복문 실행
for(int i=0; i < index-1; i++){
temp = temp.next;
}
// 새로운 노드를 중간에 삽입
newNode.next = temp.next; // 새로운 노드와 기존 다음 노드 연결
temp.next = newNode; // 새로운 노드와 기존 전 노드 연결
size++;
}💡 연결 리스트는 포인터로 연결되어 있는 탐색, 삽입, 삭제에 O(n)의 시간복잡도가 소요되지만
위의 구현 코드에서 증명했다시피, 리스트의 맨 앞이나 뒤와 같이 삽입 및 삭제의 위치를 알고 있는 경우 O(1)의 시간복잡도가 발생할 수 있다.
✨ 배열과 연결 리스트 비교
-
배열
- 랜덤 접근: O(1) 👍🏻
- 추가, 삭제: O(n)
-
연결 리스트
- 랜덤 접근: O(n)
- 추가, 삭제: O(n) or O(1) 👍🏻
3️⃣ 벡터(Vector) | 탐색, 맨 뒤 요소 삽입,삭제 : O(1) 맨 뒤가 아닌 요소 삽입,삭제 : O(n)
- 동적 배열 | 동적으로 요소 할당 가능
- 중복 허용, 순서 있음, 랜덤 접근 가능
Vector<Integer> v = new Vector<>();
v.add(5);
v.add(4);
v.add(-1);
System.out.println(v); // [5,4,-1]
v.add(1,2);
System.out.println(v); // [5,2,-1]- 사용법은
Array List와 비슷- 컬렉션 프레임워크가 나오기 전에 가변 개수의 배열이 필요할 때 사용되었음(과거) → 현재는 호환성이 필요한 상황 외에는 거의 사용하지 않는다고 함
- ArrayList와 다른 점은 멀티 쓰레드 환경에서 메서드에 lock을 걸어 안전하게 사용할 수 있음
💅🏻💅🏻💅🏻 Array vs ArrayList vs LinkedList
지금까지 총 4개의 선형 자료구조에 대해 살펴봤다. 그 중, 자주 사용되는 자료구조의 특징을 표로 정리해보았다.
| 특징 | Array | ArrayList | LinkedList |
|---|---|---|---|
| 크기 | 고정(정적) | 동적 | 동적 |
| 접근 속도 | 빠름 (O(1)) | 빠름 (O(1)) | 느림 (O(n)) |
| 삽입/삭제 | 느림(O(n)) | 느림(O(n)) | 빠름 (O(1) ~ O(n)) |
| 랜덤접근 | 가능 | 가능 | 불가능 |
| 메모리 구조 | 연속적 | 연속적 | 비연속적 |
| 적합한 경우 | 크기가 고정된 데이터 처리 | 크기가 변하는 배열 사용 시 | 자주 삽입/삭제가 필요한 경우 |
참고
✔️ 순차접근과 랜덤접근
✔️ Vector vs ArrayList
✔️ Array vs ArrayList vs LinkedList
