Array vs ArrayList vs LinkedList

Array

• Array는 논리적인 저장순서와 물리적인 저장순서가 일치하는 자료구조
• Array의 사이즈는 초기에 설정 -> 변경 불가
  • ex) int[] arr = new int[5];
• index를 활용한 random access 가능

시간 복잡도
조회 : O(1)
추가/삭제 : O(N)

ArrayList

• 배열을 이용해 구현한 리스트
• Array와 달리 사이즈가 가변적
  • 원소가 가득 찼을 경우 기존 사이즈 1.5배의 새로운 ArrayList를 생성해 복사
• Array와 마찬가지로 index를 활용한 random access 가능

시간 복잡도
조회 : O(1)
추가/삭제 : O(N)

LinkedList

• 노드를 연결시켜 구현한 리스트
• index가 없어서 random access 불가능 -> 순차 탐색
• 원소 삽입/삭제시 연관된 노드들만 연결을 이어주거나 끊어주면 되기 때문에 간단

시간 복잡도
조회 : O(N)
추가/삭제 : O(1) -> But 삭제하려는 원소까지 접근하는데 O(N) 소요

자료구조 선택 기준

Array

• 데이터 개수가 고정적이고 삽입, 삭제가 빈번하지 않은 경우
• 데이터 접근이 빈번한 경우
• 기본 자료형(int, char, double..) 사용하고 싶은 경우

ArrayList

• 삽입, 삭제가 빈번하지 않은 경우
• 데이터의 접근이 빈번한 경우

LinkedList

• 데이터의 삽입, 삭제가 빈번한 경우
• 데이터의 접근이 빈번하지 않은 경우
• 데이터 개수가 많지 않은 경우(삽입, 삭제도 일단 해당 위치로 접근해야 하기 때문에 데이터가 많은 경우 삽입, 삭제도 느려질 수 있음)

선택 정렬

 데이터가 무작위로 여러 개 있을 때, 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복하는 알고리즘을 선택 정렬이라 한다. 선택 정렬은 아이디어가 매우 간단하지만, 시간복잡도가 항상 O(N^2)로 다른 정렬 알고리즘과 비교했을 때 매우 비효율적이다.

Name	Best	Avg	Worst
선택 정렬	O(N^2)	O(N^2)	O(N^2)

Java

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
        // 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

		// 선택 정렬
        for(int i=0; i<N; i++){
            for(int j=i+1; j<N; j++){
                if(arr[i]>arr[j]){
                    int tem = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tem;
                }
            }
        }

		// 출력
        for(int i=0; i<N; i++){
            bw.write(String.valueOf(arr[i] + " "));
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

입력
6
13 5 11 7 23 15
출력
5 7 11 13 15 23

버블 정렬

 버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 선택 정렬과 마찬가지로 아이디어는 매우 간단하지만, 시간복잡도가 항상 O(N^2)로 다른 정렬 알고리즘과 비교했을 때 매우 비효율적이다.

Name	Best	Avg	Worst
선택 정렬	O(N^2)	O(N^2)	O(N^2)

Java

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
		// 버블 정렬
        for(int i=0; i<N-1; i++){
            for(int j=0; j<N-1-i; j++){
                if(arr[j]>arr[j+1]){
                    int tem = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tem;
                }
            }
        }
        
		// 출력
        for(int i=0; i<N; i++){
            bw.write(String.valueOf(arr[i] + " "));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

삽입 정렬

 삽입 정렬은 두 번째 값부터 시작해 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘이다. 삽입 정렬의 시간 복잡도는 O(N^2)이지만 데이터가 거의 정렬되어 있는 상황에서는 최선의 경우 O(N)으로 매우 강력한 정렬 알고리즘이다.

Name	Best	Avg	Worst
삽입 정렬	O(N)	O(N^2)	O(N^2)

Java

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
		// 삽입 정렬
        for(int i=1; i<N; i++){
            int tem = arr[i];
            int j;
            for(j=i-1; j>=0; j--){
                if(tem<arr[j]){
                    arr[j+1] = arr[j];
                }
                else
                    break;
            }
            arr[j+1] = tem;
        }
        
		// 출력
        for(int i=0; i<N; i++){
            bw.write(String.valueOf(arr[i] + " "));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}