개념 : 물리적으로 떨어져 있는 노드들이 다음 노드의 주소값을 가지고 있어서 연결되는 형태
vs 배열 : 물리적으로 한공간에 배열의 크기만큼의 메모리 공간이 할당 되어 있음.
단점 : 노드의 주소값을 따라 접근해야 하기 때문에 접근속도가 느릴 수 있음
장점 : 노드를 추가하거나 삭제할때 한부분만 가진 주소값을 변경해주면 되기 때문에 비교적 간단
vs 배열 : 원소를 추가하거나 삭제하기 위해서는 배열 전체의 공간을 다시 할당 해야하기 떄문에 복잡
=> 크기가 정해지지 않은 데이터들, 추가 삭제가 잦은 데이터를 다룰때 용이하다.

단방향/양방향 Linked List

단방향 : 각 노드에 다음 노드에 대한 정보만 있어서 이전 노드로 이동할 수 없고 한쪽 방향으로만 이동할 수 있는 Linked List

⇒ 검색 시에 가장 앞의 노드부터 한개의 노드 씩 이동하면서 검색을 수행함.

양방향 : 각 노드의 전후 노드의 주소를 모두 가지고 있는 Linked List

⇒ 가장 끝에 노드를 삽일 할 때 제일 앞의 노드부터 찾아가야 하는 번거로움을 줄일 수 있음.

단방향 Linked List는 첫 노드의 주소만을 저장하고 양방향 Linked List는 처음과 끝 노드의 주소를 저장한다.

공간의 효율성을 고려해서 필요한 형태를 이용하는것이 좋다.

Big O (빅오)

알고리즘의 성능을 수학적으로 표기한 것

특징

• Big-O표기법을 이용하면 알고리즘의 시간·공간 복잡도를 표현할 수 있다.
• Big-O 표기법은 실제 알고리즘이 수행되는 Running Time을 표기하기 위한 것이 아니라 데이터의 증가에 따른 알고리즘의 성능을 예측하는 것이기 때문에 상수는 무시된다.

표기 종류

1) O(1)

: 입력 데이터 크기에 관계 없이 일정한 시간이 소요됨.

ex)

Example (int[] n) {
    return (n[0] == 0)? true:false;
}

2) O(n)

: 입력 데이터 크기에 비례해서 처리 시간이 증가하는 알고리즘

ex) 단일 for문

Example (int[] n) {
    for(int i = 0; i < n.length; i++){
        System.out.print(i);
    }
}

3) O(n²)

: 입력 데이터 크기의 제곱에 비례해서 처리 시간이 증가하는 알고리즘

ex) 이중 for문

Example (int[] n) {
    for(int i = 0; i < n.length; i++){
            for(int j = 0; j < n.length; j++){
                System.out.print(i+j);
            }
    }
}

3-1) O(nm)

: 입력되는 데이터가 다르다면, 각 데이터의 크기에 영향을 받기 때문에 따로 표기해줘야 함.

Example (int[] n, int[] m) {
    for(int i = 0; i < n.length; i++){
            for(int j = 0; j < m.length; j++){
                System.out.print(i+j);
            }
    }
}

4) O(n³)

: 입력 데이터 크기의 세제곱에 비례해서 처리 시간이 증가하는 알고리즘

ex) 삼중 for문

Example (int[] n) {
    for(int i = 0; i < n.length; i++){
            for(int j = 0; j < n.length; j++){
                for(int k = 0; k < n.length; k++){
                    System.out.print(i + j + k);
                }
            }
    }
}

5) O(2ⁿ) 또는 O(mⁿ)

: 데이터의 증가에 따라 처리 시간이 현저하게 증가하는 알고리즘

ex) Fibonacci Numbers (피보나치 수열)

Example (int n, int[] r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    return r[n] = Example(n-1, r) + Example(n-2, r);
}

5) O(log n)

: 연산을 거듭할 때 마다 연산의 대상이 되는 데이터의 양이 줄어드는 알고리즘. 데이터 양의 증가에 비해 소요 시간의 증가 폭이 크지 않음.

ex) binary search (이진 탐색)

Example(int key, int[] arr, start, end){
    if(start > end) return -1;
    int m = (start + end) / 2l
    if (arr[m] == k) return m;
        else if(arr[m] > key) return Example(key, arr, start, m-1);
        else return Example(key, arr, m+1, end);
}

6) O(sqrt(n))

: n²개의 데이터 중 n개의 데이터에 대해서 만 연산하는 알고리즘

Big O 그래프 비교