[Algorithm] 연결 리스트

연결 리스트

1. 동작 할당을 하는 오버헤드가 없어짐

2. 사용이 끝날 때마다 (ex. 여러개의 test case가 있는 경우) 메모리를 해제할 필요가 없음

3. 모든 노드가 메모리 상에서 뭉쳐 있기 때문에 캐시 효율 높아짐

관련 코드

constexpr size_t MAX_NODE = 100000;

struct Node {
    int data;
    Node* next;
};

int nodeCount = 0;
Node linkedList[MAX_NODE];

 // 더미 노드 head를 사용하면 연결 리스트에 원소가 최소 1개는 있기 때문에 삽입/삭제 과정에서 리스트가 비어 있을 경우를 생각하지 않아도 됨
Node head; 


Node* new_node(int data) {
    linkedList[nodeCount].data = data;
    linkedList[nodeCount].next = nullptr;

    return &linkedList[nodeCount++];
}

void init() {
    head.next = nullptr;
}

// 삽입 O(1). 리스트 맨 앞에 data 추가
void insert(int x) {
    Node *node = new_node(x);

    node->next = head.next;
    head.next = node;
}

// 삭제 O(N). 리스트에서 data를 찾아서 삭제
void remove(int x) {
    Node* prev_ptr = &head;

    while(prev_ptr->next != nullptr && prev_ptr->next->data != x) {
        prev_ptr = prev_ptr->next;
    }

    if (prev_ptr->next != nullptr) { // 삭제할 노드가 NULL이 아닌 경우
        prev_ptr->next = prev_ptr->next->next; // 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 함
    }
}

// 탐색 O(N). 리스트에 data 값이 있는지 반환하는 코드
bool find(int x) {
    Node* ptr = head.next;
    while(ptr != nullptr && ptr->data != x) {
        ptr = ptr->next;
    }
    return ptr != nullptr;
}