[자료구조] 배열(Array), 정적 배열(Static Array) vs 동적 배열(Dynamic Array)

1. 배열(Array)의 개념 

• 배열이란 가장 일반적인 선형 자료구조의 일종입니다.
• 복수의 데이터들을 연결시켜 관리하는 자료구조입니다.
• 메모리 관리 방법의 차이로 정적 배열(Static Array)과 동적 배열(Dynamic Array)로 나뉩니다.

2. 정적 배열(Static Array)

2 - 1. 개념

• 정적 배열(Static Array) 라고도 하고 Array List 라고도 합니다.
  대부분 후자로 부르나 저는 이번 글에서 메모리의 차이를 집중적으로 다루고자 Static Array라고 부르겠습니다.
• 아래 이미지와 같이 같은 타입의 데이터를 연속적 메모리 공간에 저장하고 인덱스로 접근하는 자료구조입니다.

Static Array

• 같은 타입 
  • 하나의 같은 자료형으로만 선언이 가능하고 하나의 배열 내에 int, char등의 여러 자료형이 나올 수 없다.
• 연속적 메모리 공간
  • 메모리 공간에 연속적으로 저장됩니다. 때문에 프로그래밍 과정에서 정해진 크기에서 변동되는것이 불가 하기에 정적(Static)이라고 합니다.
• 인덱스
  • 정적 배열은 시작 메모리 주소만을 저장하고 그 외의 주소는 따로 저장 하지 않으며 그것들에 접근 하기 위해 Offset이라는 개념을 사용하여 그것들에 접근합니다. Offset이라 함은 첫번째 원소로 부터 얼마나 떨어진지를 말하며 때문에 index가 0부터 시작 합니다.
  • array[n]의 주소 = base address + n

2 - 2. 사용

public class Main {
    public static void main(String[] args) {
        // 배열 선언 및 초기화
        int[] array = new int[5];

        // 배열에 값 할당
        array[0] = 3;
        array[1] = 7;
        array[2] = 9;

        // 배열의 요소 출력
        System.out.println("Array:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

2 - 3. 장점

• 빠른 접근 : 인덱스를 통해 원하는 위치의 데이터에 빠르게 접근할 수 있습니다.
• CPU Cache: 연속된 메모리 공간에 데이터를 저장하기 때문에, CPU Cache를 통해서 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있습니다.

2 - 4. 단점 

• 고정된 크기: 배열의 크기가 고정되어 있어 프로그래밍 과정에서 크기를 지정해야 하며, 이는 불필요한 메모리 사용이나 부족한 공간으로 인한 문제를 일으킬 수 있습니다.
• 삽입과 삭제의 어려움: 배열의 중간에 데이터를 삽입하거나 삭제하기 어려우며, 이로 인해 데이터 이동이 필요할 수 있습니다.

 

 

 

3. 동적 배열(Dynamic Array)

3 - 1. 개념

• 동적 배열(Dynamic Array) 라고도 하고 Linked List 라고도 합니다.
• 크기가 변할 수 있는 배열로, 데이터를 더하거나, 빼는 것이 가능한 자료구조 입니다.
• resizable array, arraylist, liked list, dynamic array 모두 이것을 의미 합니다.
• C++에서는 vector, Java에서는 LinkedList로 구현되어있습니다.

3 - 2. 데이터의 삽입 삭제

데이터 삽입

n번째 노드로 데이터를 삽입 한다면 다음과 같은 과정을 거치게 됩니다.

1. 새로운 노드를 생성하고 그 노드에 삽입하고자 하는 데이터를 넣는다.
2. n-1번째 노드에 접근하여 그것이 들고 있는 다음 노드의 주소 값을 생성한 노드의 다음 노드 참조로 한다.
3. n-1번째 노드의 다음 노드 참조를 생성한 노드의 주소로 한다.

데이터 삭제

n번째 노드로 데이터를 삭제 한다면 다음과 같은 과정을 거치게 됩니다.

1. n-1번째 노드의 다음 노드 참조를 n번째 노드의 다음 노드 참조로 변경한다.
2. n번째 노드의 메모리를 릴리즈 한다.

3 - 3. 구현 & 사용

구현

public class LinkedList {

    // 노드 클래스 정의
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 연결 리스트의 첫번째 노드를 가리키는 변수
    private Node head;

    // 생성자: 빈 연결 리스트 생성
    public LinkedList() {
        this.head = null;
    }

    // 새로운 데이터를 연결 리스트의 맨 앞에 추가하는 메서드
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 연결 리스트의 요소를 출력하는 메서드
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

사용(java.util.LinkedList)

LinkedList: 내부적으로는 더블 링크드 리스트(Double Linked List)로 구현됩니다. 각 노드는 데이터와 다음 노드, 이전 노드에 대한 참조를 가지고 있어서 삽입 및 삭제가 빠르지만 인덱스를 통한 접근은 선형 시간이 소요됩니다.

ArrayList: 내부적으로 배열을 사용하여 요소를 저장합니다. 배열은 요소의 연속된 메모리 공간에 저장되므로 인덱스를 통한 빠른 접근이 가능합니다. 때문에 주로 ArrayList를 사용 합니다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> linkedList = new LinkedList<>();

        // 맨 앞에 요소 추가
        linkedList.addFirst(3);
        linkedList.addFirst(7);
        linkedList.addFirst(9);

        // 연결 리스트의 요소 출력
        System.out.println("Linked List:");
        for (Integer element : linkedList) {
            System.out.print(element + " ");
        }
        System.out.println();
    }
}

3 - 4. 장점

 

• 유동적인 크기: 배열의 크기가 고정되어 있지 않아 프로그램의 구동중에도 늘어나거나 줄어들수 있습니다.
• 삽입과 삭제가 가능: 배열의 중간에 데이터를 삽입하거나 삭제하는 것이 가능하여 메모리를 효율적으로 관리 할 수 있습니다.

 

 

3 - 5. 단점 

• 느린 접근 : n번째 노드를 접근하기 위해서는 head, 0 ~ n-1까지의 모든 노드들을 접근 해야 접든할수 있기에 느립니다.
• 비효율적 메모리 : 각각의 노드들이 다음 혹은, 이전, 다음 노드의 주소를 가지고 있어야 하기에 비효율적입니다.