자료구조 Part1

Array(배열)

1. 메모리 상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조 입니다.
 
2. 크기는 고정되어 있으며, 변경될 수 없습니다.
데이터의 삽입/삭제는 불가능합니다.
 
하기 표는 Int 형태의 배열을 표로 나타내본것 입니다.
Int 는 4바이트 이기 때문에 4개의 byte 단위로 주소값을 가지고 있습니다.
Boolean 의 경우에는 1개의 byte 단위로 주소값을 가지고 있습니다.

0x6d5ab550	a[]
0x6d5ab550	10
0x6d5ab551
0x6d5ab552
0x6d5ab553
0x6d5ab554	20
0x6d5ab555
0x6d5ab556
0x6d5ab557
0x6d5ab558	30
0x6d5ab559
0x6d5ab560
0x6d5ab561
0x6d5ab562	40
0x6d5ab563
0x6d5ab564
0x6d5ab565

3. 시간 복잡도
i번째 데이터에 접근/변경 O(1)
-> 위치 별로 주소값을 통하여 바로 접근이 가능하기 때문에 시간복잡도는 O(1) 입니다.
 
특정 값이 있는지 탐색하는 경우 O(N)
-> 특정 값이 있는지 확인하기위해서는 배열에 저장된 값들을 순회하면서 확인해야 하므로 O(N) 입니다.
 

Dynamic Array (List, ArrayList,  Vector)

1. Dynamic Array는 메모리 상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조 입니다.
 
2. 크기는 동적으로 변경될 수 있지만, 근복적으로는 배열 기반으로 구현되어 있습니다.
 
3. 여유 공간이 없을 경우 사이즈를 (2배 혹은 50%) 씩 늘립니다.
-> 사이즈를 늘리는 로직 특성 상 메모리 낭비가 발생할 수 있습니다.
 
4. 시간 복잡도 
i번째 데이터에 접근/변경 O(1)
 
특정 데이터가 있는지 탐색하는 경우 O(N)
 
리스트의 끝에 데이터 삽입/삭제 *Amortized O(1)
(리스트의 끝을 제외한 데이터의  삽입/삭제 O(N)
 
5. 리사이징 예시
init size = 4, size 50% 증가
리사이징이 발생할 때마다 새로운 메모리 영역을 할당하고, 데이터 복사가 발생합니다.
-> 복사할 때의 시간 복잡도는 O(N) 입니다.
리사이징은 자주 발생하지 않으므로, 평균적(Amortize)으로 O(1)에 삽입 및 삭제가 가능합니다. -> 리스트의 끝에서만
 

 
6. 데이터 삽입 /  삭제 예시
 
리스트의 가장 끝에서는 리사이징이 발생하지 않고 데이터를 삽입하는 경우 O(1)의 시간 복잡도를 가진다.

 
리스트의 가장 끝 데이터를 삭제하는 경우 또한 O(1)의 시간 복잡도를 가집니다.

 
리스트의 중간에 데이터를 삽입하는 경우에는 O(N)의 시간 복잡도를 가집니다.
이유는 14를 한 칸 뒤로 이동하고, 12를 한 칸 이동하고..... 이런 방식을 반복 후 원하는 위치에 원하는 데이터를 넣기 때문에 시간 복잡도는 O(N) 이 됩니다.

 
중간에 있는 데이터를 삭제하는 경우 또한 마찬가지로 O(N)의 시간 복잡도를 가집니다.

 
 

Linked List

1. Linked List 는 메모리 상에서는 데이터가 불연속적으로 저장되어 있으나, 논리적으로 연속성을 구현한 선형 자료구조이다.
 
2. 값(value)과 다음 값의 위치(메모리 주소)를 노드(Node)라는 이름의 쌍으로 저장합니다.
 
3. i 번째 데이터에 접근하는 것은 O(N)의 시간 복잡도를 가지며, 데이터의 삽입/삭제는 어느 위치에서나 O(1)의 시간 복잡도를 가집니다.
 
4. 시간 복잡도
i 번째 데이터에 접근 /  변경 O(N)
특정 데이터가 있는지 탐색 O(N)
 
-> 특정 데이터를 접근하기 위해서는 앞에서부터 시작하여 원하는 조건이 만족할 때 까지 순회를 해야하기 때문에
O(N)의 시간 복잡도를 가지게 된다.
 

 
데이터의 삽입 / 삭제 O(1)  -> 해당 노드에 접근하는 시간은 제외

 

Doubly Linked List

Linked List 에 직전 Node의 주소 값도 추가로 저장하여, 양방향 탐색이 가능하도록 구현되어 있으며,
Java 에서 Linked List 는 Double Linked List 로 구현되어 있습니다.
또한 값의 접근을 할 때 앞에서 접근하는게 빠른지 뒤에서 접근하는 것이 빠른지 확인하여 접근 방식이 달라집니다.
가장 오래걸리는 값은 중간에 있는 값을 조회할 때 가장 많은 시간이 걸립니다.

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

 

Array, Dynamic Array, Linked List  비교

 

Queue(큐)

1. 데이터가 연속적(논리적)으로 저장되어 있는 선형 자료구조이다.
2. FIFI (First In First Out) 자료 구조 입니다.
 
3. 용어
Queue 에 데이터를 넣는 것 : Enqueue (Add)
Queue 에서 데이터를 꺼냄 : Dequeue (Poll)
 
4. 시간 복잡도
i 번째 데이터에 접근 : O(N)
맨 앞 데이터에 접근 / 삭제 : O(1)
맨 뒤 데이터에 접근 / 삭제 : O(1)
맨 뒤에 데이터 추가  : O(1)
특정 데이터가 있는지 탐색 : O(N)

 

Deque (Double Ended Queue)

1. 한 방향으로만 데이터를 넣거나 꺼내는게 아니라 양쪽 끝에서 데이터를 추가하거나 꺼낼 수 있는 자료구조
 
2. 시간 복잡도 
 
i 번째 데이터에 접근 : O(N)
맨 앞/뒤 데이터에 접근 / 추가 / 삭제 : O(1)
특정 데이터가 있는지 탐색 : O(N)
 

 

Stack

1. 데이터가 연속적(논리적)으로 연결되어 있는 선형 자료구조 이다.
 
2. LIFO (Last In First Out : 마지막에 들어온 데이터가 먼저 나감) 자료구조 이다.
 
3. 용어 
Stack 에 데이터를 넣음 Push
Stack 에서 데이터를 꺼냄 Pop
 
4. 시간 복잡도
i 번째 데이터에 접근 : O(N)
맨 위(뒤) 데이터에 접근 / 삭제 : O(1)
특정 데이터가 있는지 탐색 : O(N)
 
5. Stack 메모리를 초과하면 Stack Overflow Error가 발생하며, 비어있는 Stack 에서 Pop 을 하면
Empty Stack Error 가 발생한다.

6. 대표적으로 프로세스 메모리 영역에 사용되며, 해당 영역을 Stack 영역이라 부른다.
 
7. 함수의 복귀 주소, 지역 변수 저장 등의 용도로 사용된다.
 

 

fun main(){
    fun1(20)
}

fun fun1(num: Int){
    var a = 10
    fun2(30)
    println(num)
}

fun fun2(num: Int){
    var b = 40
    println(num)
}

상기 코드가 프로세스 메모리 영역에 저장되는 순서는 하기와 같다

따라서 출력 결과를 보면 하기와 같이 나오는 것을 확인 할 수 있다.

 
 
 
자료 출처 :
https://reliable-cloak-1e8.notion.site/fb0fb4eee0fc429abd36ca0806510cb6?v=e101408a85fd4f9a8a6eb1cceda9b2b0 

CS  강의/스터디 (공유용)

 
https://www.youtube.com/watch?v=sPUvJOgODmI