배열 (Array)

1. 배열 초기화

// 스택에 할당
int arr[5];
int nums[5] = { 1, 2, 3, 4, 5 };

// 힙에 할당
int* agg = new int[5];
int* ngg = new int[5] {1, 2, 3, 4, 5};

2. 요소 접근

int getElement(int* data, int idx) {
    return *(data + idx);
}

3. 데이터 삽입

void insertElement(int* data, int len, int value, int pos) {
    for (int i = len - 1; i > pos; i--) {
        data[i] = data[i - 1];
    }
    data[pos] = value;
}

4. 배열 순회

for (int k = 0; k < 5; k++) {
    std::cout << *(ngg + k) << std::endl;
}

5. 특정 값 검색

int searchValue(int* data, int len, int target) {
    for (int i = 0; i < len; i++) {
        if (data[i] == target)
            return i;
    }
    return -1;
}

6. 배열 확장

int* expandArray(int* src, int oldSize, int addSize) {
    int* newArr = new int[oldSize + addSize];
    for (int i = 0; i < oldSize; i++) {
        *(newArr + i) = *(src + i);
    }
    delete[] src;
    return newArr;
}

7. 전체 예제

#include <iostream>

int getElement(int* data, int idx);
void insertElement(int* data, int len, int value, int pos);
int searchValue(int* data, int len, int target);
int* expandArray(int* src, int oldSize, int addSize);

int main() {
    // 스택 할당
    int arr[5];
    int nums[5] = { 1, 2, 3, 4, 5 };

    // 힙 할당
    int* agg = new int[5];
    int* ngg = new int[5] {1, 2, 3, 4, 5};

    int* result = expandArray(ngg, 5, 3);
    for (int i = 0; i < sizeof(result); i++) {
        std::cout << *(result + i) << std::endl;
    }
}

int getElement(int* data, int idx) {
    return *(data + idx);
}

void insertElement(int* data, int len, int value, int pos) {
    for (int i = len - 1; i > pos; i--) {
        data[i] = data[i - 1];
    }
    data[pos] = value;
}

int searchValue(int* data, int len, int target) {
    for (int i = 0; i < len; i++) {
        if (data[i] == target)
            return i;
    }
    return -1;
}

int* expandArray(int* src, int oldSize, int addSize) {
    int* newArr = new int[oldSize + addSize];
    for (int i = 0; i < oldSize; i++) {
        *(newArr + i) = *(src + i);
    }
    delete[] src;
    return newArr;
}

8. 배열 특징 요약

• 삽입과 삭제의 시간 복잡도는 O(n)이지만, 임의 접근은 O(1)
• 공간 효율성과 캐시 지역성: 배열 요소 접근 시 주변 데이터도 함께 캐시되어 성능 향상
• 길이가 고정되어 있으며 메모리 낭비 가능성이 있음

연결 리스트 (Linked List)

1. 연결 리스트 초기화

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

int main() {
    Node* node0 = new Node(1);
    Node* node1 = new Node(3);
    Node* node2 = new Node(2);
    Node* node3 = new Node(5);
    Node* node4 = new Node(4);

    node0->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
}

2. 노드 삽입 (시간 복잡도 O(1))

void insertNode(Node* prev, Node* newNode) {
    Node* temp = prev->next;
    newNode->next = temp;
    prev->next = newNode;
}

주의: 첫 번째 줄에서 원본 next 포인터를 저장해야 합니다. 생략하면 안 됩니다.

3. 노드 삭제

void removeNode(Node* prev) {
    Node* target = prev->next;
    Node* nextNode = target->next;
    prev->next = nextNode;
    delete target;
}

4. 요소 접근 (순차 탐색 필요)

Node* accessNode(Node* head, int idx) {
    for (int i = 0; i < idx; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

5. 값으로 인덱스 찾기

int findIndex(Node* head, int target) {
    int idx = 0;
    while (head != nullptr) {
        if (head->val == target)
            return idx;
        head = head->next;
        idx++;
    }
    return -1;
}

6. 이중 연결 리스트

브라우저 히스토리 등에 활용됩니다.

struct DNode {
    int val;
    DNode* next;
    DNode* prev;
    DNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};

배열과 연결 리스트 비교

배열은 빠른 임의 접근과 캐시 효율성을 제공하지만 크기가 고정되어 있습니다. 연결 리스트는 동적 크기 조정과 효율적인 삽입/삭제가 가능하지만, 순차 접근만 가능하고 추가 메모리가 필요합니다.