이때, 데이터 크기를 설정하는 메모리 주소를 같은 값으로 설정하면 나중에 넣는 값으로 덮히게 된다.
메모리 주소를 복사하는 것은 주의가 필요하다.
2) 배열의 크기 조정하기
realloc 함수를 사용해 배열의 크기를 조정할 수 있다.
3) 연결리스트 : 도입
데이터 구조는 컴퓨터 메모리를 효율적으로 관리하기 위해 새로 정의하는 구조체로, 일종의 메모리 레이아웃, 지도이다.
연결 리스트
ㄴ 각 인덱스의 값이 메모리상에서 연이어 저장되어 있는 배열과 달리 각 값이 메모리상의 여러 군데 나뉘어져 있지만 바로 다음 값의 메모리 주소를 기억하고 있어 값은 연이어 읽어들일 수 있다.
마지막 값은 NULL을 저장한다.
장점 - 연속적인 메모리 공간이 필요하지 않아 효율적이고, 데이터 수정이 용이하다.
단점 - 배열에 비해 접근성이 부족하고, 메모리 주소 값도 저장하기에 상대적으로 메모리 공간 사용량이 증가한다.
4) 연결리스트 : 코딩
list가 끊어지지 않게 코딩하는것이 중요하다. 끊어진 메모리는 다시 찾을 수 없기에
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
//node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
int number;
//다음 node의 주소를 가리키는 포인터를 *next로 지정합니다.
struct node *next;
}
node;
int main(void)
{
// list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다.
// 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
node *list = NULL;
// 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미입니다.
// 즉, n이 가리키는 node의 number 필드를 의미하는 것입니다.
// 간단하게 화살표 표시 ‘->’로 쓸 수 있습니다. n의 number의 값을 1로 저장합니다.
n->number = 1;
// n 다음에 정의된 node가 없으므로 NULL로 초기화합니다.
n->next = NULL;
// 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
list = n;
// 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number와 next의 값을 각각 저장합니다.
n->number = 2;
n->next = NULL;
// list가 가리키는 것은 첫 번째 node입니다.
//이 node의 다음 node를 n 포인터로 지정합니다.
list->next = n;
// 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
// 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있습니다.
// 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의
// 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정합니다.
list->next->next = n;
// 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다.
// 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}
5) 연결리스트 : 시연
연결 리스트는 새로운 값을 추가할 때 메모리를 다시 할당하지 않아도 되지만, 임의 접근이 불가능하다. 이처럼 데이터 구조에는 장점과 단점이 존재하기에 각 데이터 구조별 특징을 알고 사용해야 한다.
6) 연결리스트 : 트리
트리는 연결리스트를 기반으로 한 데이터 구조이다.
연결리스트의 각 노드의 1차원적인 연결을 2차원으로 구성하면 트리가 된다.
각 노드는 일정한 층에 속하고, 다음 층의 노드를 가리키는 포인터를 갖는다.
가장 상단에 트리가 시작되는 노드를 ‘루트’라고 한다. 루트 노드는 다음 층의 노드를 가리키고 이를 ‘자식 노드’라고 한다.
위 그림의 트리는 이진 검색 트리로 규칙에 의해 구성되어 있다.
균형이 이루어져 있다면 이진 검색과 삽입이 O(log n)으로 가능해 효율적이다.
하지만 메모리 크기가 크다는 단점이 있고, 트리의 균형이 맞지 않으면 똑같기에 균형을 맞추는 알고리즘이 추가로 필요하다.
7) 해시 테이블
해시 테이블은 연결 리스트의 배열이다.
각 값들은 해시 함수라는 맞춤형 함수를 통해 새롭게 정의되는 연결 리스트로 이어진다.
결국 연결 리스트가 여러개 있는 연결 리스트의 배열이 된다.
이상적인 해시 함수가 있다면 O(1)
그렇지 않다면 O(n)
8) 트라이
트라이는 각 노드가 배열로 이루어진 트리 형태의 자료 구조이다.
속도는 빠르지만 메모리를 많이 사용한다.
9) 스택, 큐, 딕셔너리
스택은 값이 위로 쌓이는 구조이다.
후입선출, LIFO 방식을 따르며, 가장 나중에 온 값이 가장 먼저 나가는 뷔페 접시와 같다.
