CS - Data Structure

배열

연관된 데이터를 모아서 연속적으로 관리하기 위한 자료구조

 

- 배열은 메모리 상에 고정된 크기를 가지기 때문에 한 번 생성하면 크기 수정이 불가능

- 인덱스를 통해 배열에 접근할 때의 시간 복잡도는 O(1)

- 프로그램 작성 과정에서 데이터를 삽입/삭제 불가능, 변경만 가능

 

int main(){
	int a[5] = {0,};
	int a[] = {1, 2, 3, 4, 5};
}

 

위와 같이 미리 크기를 할당하고 사용해야 한다

LinkedList

포인터와 노드를 사용해 연속이 아닌 연결되어 있는 자료구조

 

각 노드는 데이터 필드와 주소 필드로 이루어져 있음

 

- 원하는 위치에 삽입/삭제가 가능함으로 동적으로 데이터를 관리할 수 있음

- 첫 번째 노드부터 순차적으로 요소에 접근해야함 임의로 액새스 불가능

 

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

int main() {
    char[] data = ['A', 'B', 'C', 'D', 'E'];
    int size = sizeof(data)/sizeof(data[0])
    
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    struct Node* current = head;
    
    head->data = data[0]
    head->next = null;
    
    for(int i = 1; i<size; i++){
    	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
        new_node->data = data[i];
        new_node->next = null;
        
        current->next = new_node;
        current = new_node;
    }
}

 

위와 같은 방식으로 생성 가능

 

연결리스트에서 데이터를 삽입하려면

void push(struct Node** prev_node, int new_data) {
    if(prev_node == NULL) return;
    
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node))
    
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

 

위와 같은 방식으로 코드를 짤 수 있다

 

같은 방식으로 연결리스트에 데이터를 삭제하려면

void delete(struct Node* prev_node) {
    if (prev_node == NULL || prev_node->next == NULL) return;

    struct Node* temp = prev_node->next; 
    prev_node->next = temp->next;       
    free(temp);                      
}

 

위와 같이 코드를 짤 수 있다

 

 

Array VS LinkedList VS ArrayList

- Array : 인덱스로 자료에 빠른 접근이 가능하나 크기를 미리 할당하고 사용해야함

- LinkedList : 자료의 삽입/삭제가 빠르나 데이터를 접근할 때 순차 검색이기 때문에 데이터 검색이 느림

- ArrayList : 데이터를 빠르게 찾을 수 있으나 삽입/삭제가 느림

 

STACK

후입선출 구조의 자료구조

 

top은 -1부터 시작

void push(int data){
    if(top == size) return;
	stack[++top] = data;
}

 

 

int pop(){
    if(top == -1) return -1;
    return stack[top--];
}

 

QUEUE

선입선출 구조의 자료구조

 

front는 0부터 시작

rear는 -1부터 시작

 

void add(int index) {
    if(rear == size) return;
    queue[++rear] = index;
}

 

int delete(){
    if(rear < front) return -1;
    return queue[front++];
}