자료 구조(Data Structures) - 1

/** 자료구조는 따로 다시 정리할 예정**/

 

연속(Contiguous) 대 연결 자료구조(Linked Data Structures)

자료구조는 배열에 따라 구현 vs 포인터에 따라 구현

- 연속적 자료구조는 메모리의 연속된 한 구역으로 구성

배열, 행렬, 힙, 해시 테이블 등

 

- 연결된 자료구조는 포인터에 의해 뚜렷이 구분되는 메모리의 구역들로 구성

리스트, 트리, 그래프 등

 

배열(Array)

연속적으로 자료가 할당되는 가장 핵심적인 자료구조

각 원소들을 인덱스 혹은 주소로 그 위치를 찾을 수 있는 고정 크기(fixed-size) 구조

 

연속적으로 할당된 배열의 장법

- 주어진 인덱스로 상수 시간 접근 : 배열의 인덱스만 알면 데이터 요소 즉시 접근 가능

- 공간 효율성

- 메모리 지역성 : 배열은 매우 훌륭한 지역성을 갖고 있어 반복적 연산에 적합, 캐시 메모리 개발에 도움

 

배열의 단점

- 프로그램 수행 중에 그 크기를 조정할 수 없다는 것

 

포인터와 연결 구조

포인터는 연결 구조들의 흩어진 부분들을 잇는 연결(Connection)

아래 연결 리스트 코드에서 나타낼 수 있다

typedef struct list {
    item_type item;
    struct list *next;
} list;

리스트는 단순한 연결구조로 세 가지 기본 연산은 탐색(search), 삽입(insert), 삭제(delete)이다.

이중 연결 리스트(doubly-linked list)는 선행자와 후속자 노드를 가리키고 있어야 한다.

 

리스트 탐색

재귀적인 방법으로 리스트 탐색

list *search_list(list *l, item_type x) {
    if (l->next == NULL) return NULL;
    if (l->item == x) return l;
    else {
    	search_list(l->next, x);
    }
}

 

리스트 삽입

void insert_list(list **l, item_type x) {
    list *p;
    
    p = malloc(sizeof(list));
    p->item = x;
    p->next = *l;
    *l = p;
}

1. malloc 은 x를 저장할 새로운 노드 크기 만큼 메모리 할당

2. **l은 l이 리스트 노드에 대한 포인터에 대한 포인터임을 나타낸다.

 

* 위 코드는 특정 순서를 유지하지 않기 때문에 조건이 없는 코드다.

 

리스트 삭제

delete_list(list **l, item_type x) {
    list *p;
    list *pred
    list *search_list(), *predecessor_list();
    
    p = search_list(*l, x);
    if (p != NULL) {
    	pred = predecessor_list(*l, x);
        if (pred == NULL)
        	*l = p->next;
        else
        	pred->next = p->next;

        free(p);
    }
    
}

 

배열과 연결 리스트 비교

연결 리스트의 장점 than 배열

- 오버플로(overflow)는 발생하지 않는다.

- 배열보다 삽입과 삭제가 더 단순하다.

- 레코드를 옮기는 것보다 포인터를 옮기는 것이 더 쉽고 빠르다.

 

배열의 장점 than 연결리스트

- 연결 구조는 포인터 필드를 저장하기 위한 추가적인 공간을 필요

- 연결 리스트는 항목에 대한 랜덤 접근 불가능

- 배열은 보다 나은 메모리 지역성과 캐시 성능을 가진다

 

스택과 큐(Stack & Queue)

 

스택

LIFO 검색이 이루어지는 자료구조, 스택은 간단히 구현할 수 있고 매우 효율적인 자료구조

- Push(x, s) : 원소 x를 스택 s의 top에 삽입

- Pop(s) : 스택 s의 top의 원소를 되돌려 준 후 삭제

 

큐

FIFO 검색되는 자료구조

- enqueue(x, q) : 원소 x를 큐 q의 맨 뒤에 삽입

- dequeue(q) : q의 처음의 원소를 되돌려 준 후 삭제