생각하면서 접근하면 된다.

• ...

배열로 연결리스트 구현1_표 편집 유사.

#include <iostream>
#include <vector>

using namespace std;

class Table {
public:
    vector<int> data;
    vector<int> pre;
    vector<int> next;
    int head;
    int capacity; // 배열의 전체 크기

    // 1. init: 처음부터 n개의 데이터를 채우고 연결함
    Table(int n, int max_capacity) {
        capacity = max_capacity;
        data.resize(capacity, 0);
        pre.resize(capacity, -2);  // -2는 사용되지 않은 칸임을 표시 (임의)
        next.resize(capacity, -2);

        for (int i = 0; i < n; i++) {
            data[i] = (i + 1) * 10; // 10, 20, 30... 초기 데이터
            pre[i] = i - 1;
            next[i] = i + 1;
        }
        next[n - 1] = -1;
        head = 0;
    }

    /**
     * 2. Insert: 특정 인덱스(k)에 값(val)을 써서 target_pre 뒤에 연결
     * @param k : 데이터를 저장할 배열의 물리적 인덱스
     * @param val : 저장할 값
     * @param target_pre : 논리적으로 누구 뒤에 붙일 것인가 (-1이면 맨 앞)
     */
    void insertAt(int k, int val, int target_pre) {
        if (k < 0 || k >= capacity) {
            cout << "범위를 벗어난 인덱스입니다." << endl;
            return;
        }

        data[k] = val; // 값 기록

        if (target_pre == -1) {
            // 맨 앞에 삽입
            next[k] = head;
            pre[k] = -1;
            if (head != -1) pre[head] = k;
            head = k;
        } else {
            // target_pre 뒤에 삽입
            int target_next = next[target_pre];

            next[k] = target_next;
            pre[k] = target_pre;
            
            next[target_pre] = k;
            if (target_next != -1) pre[target_next] = k;
        }
        cout << ">> [삽입] 인덱스 " << k << "번에 값 " << val << "을 " << target_pre << "번 뒤에 연결" << endl;
    }

    // 3. Delete: 연결만 끊기
    void deleteAt(int k) {
    // 이미 삭제되었거나 범위를 벗어난 경우 방어
    if (k < 0 || k >= dataV.size()) return;

    int preIdx = preV[k];
    int nextIdx = nextV[k];

    // [체크] 앞사람이 있는가?
    if (preIdx != -1) {
        nextV[preIdx] = nextIdx;
    } else {
        // 앞사람이 없다면 내가 head였다는 뜻! 시작점을 다음 사람으로 옮김
        head = nextIdx;
    }

    // [체크] 뒷사람이 있는가?
    if (nextIdx != -1) {
        preV[nextIdx] = preIdx;
    }

    // (옵션) 삭제된 노드라는 표시를 남김
    preV[k] = -2;
    nextV[k] = -2;
}

    void display() {
        int curr = head;
        cout << "현재 표 상태: ";
        while (curr != -1) {
            cout << "[" << curr << "번:" << data[curr] << "]";
            curr = next[curr];
            if (curr != -1) cout << " <-> ";
        }
        cout << endl;
    }
};

int main() {
    // 1. 초기 상태: 0~2번 인덱스까지 데이터 10, 20, 30이 들어있음 (최대 10칸)
    Table myTable(3, 10);
    myTable.display(); // [0번:10] <-> [1번:20] <-> [2번:30]

    // 2. 삭제 테스트
    myTable.deleteAt(1); // 20 삭제
    myTable.display(); // [0번:10] <-> [2번:30]

    // 3. 사용자 지정 인덱스 삽입 테스트
    // 5번 인덱스에 값 99를 0번(값 10) 뒤에 삽입
    myTable.insertAt(5, 99, 0);
    myTable.display(); // [0번:10] <-> [5번:99] <-> [2번:30]

    // 4. 맨 앞에 삽입 테스트
    // 7번 인덱스에 값 77을 맨 앞에 삽입
    myTable.insertAt(7, 77, -1);
    myTable.display(); // [7번:77] <-> [0번:10] <-> [5번:99] <-> [2번:30]

    return 0;
}

node 를 기반으로

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 1. 노드 구조체 정의 (포인터 대신 인덱스 사용)
struct Node {
    int data;
    int prev; // 이전 노드의 배열 인덱스
    int next; // 다음 노드의 배열 인덱스
};

class Table {
public:
    Node nodes[1000001]; // 최대 개수만큼 미리 할당 (정적 배열 방식)
    int head;

    Table(int n) {
        for (int i = 0; i < n; i++) {
            nodes[i].data = (i + 1) * 10;
            nodes[i].prev = i - 1; // 0번 노드의 prev는 -1
            nodes[i].next = i + 1; // n-1번 노드의 next는 n (나중에 -1로 처리)
        }
        nodes[n - 1].next = -1;
        head = 0;
    }

    /**
     * @param k : 사용할 배열의 인덱스
     * @param val : 저장할 값
     * @param target_pre : 논리적으로 누구 뒤에 붙일 것인가 (인덱스)
     */
    void insertAt(int k, int val, int target_pre) {
        nodes[k].data = val;

        if (target_pre == -1) { // 맨 앞에 삽입
            nodes[k].next = head;
            nodes[k].prev = -1;
            if (head != -1) nodes[head].prev = k;
            head = k;
        } else {
            int target_next = nodes[target_pre].next;

            nodes[k].prev = target_pre;
            nodes[k].next = target_next;

            nodes[target_pre].next = k;
            if (target_next != -1) nodes[target_next].prev = k;
        }
    }

    void deleteAt(int k) {
        if (k == -1) return;

        int pr = nodes[k].prev;
        int nx = nodes[k].next;

        if (pr != -1) nodes[pr].next = nx;
        else head = nx;

        if (nx != -1) nodes[nx].prev = pr;

        // nodes[k]의 정보는 유지 (나중에 복구할 때 사용하기 위함)
    }

    void display() {
        int curr = head;
        cout << "현재 리스트: ";
        while (curr != -1) {
            cout << "[" << curr << "번:" << nodes[curr].data << "]";
            curr = nodes[curr].next;
            if (curr != -1) cout << " <-> ";
        }
        cout << endl;
    }
};

int main() {
    Table myTable(5); // 0~4번까지 10, 20, 30, 40, 50 연결
    myTable.display();

    myTable.deleteAt(2); // 2번(30) 삭제
    myTable.display();   // 0-1-3-4 연결

    // 9번 인덱스에 999라는 값을 0번 뒤에 삽입
    myTable.insertAt(9, 999, 0);
    myTable.display();   // 0-9-1-3-4 연결

    return 0;
}