배열의 크기 조정하기
- 일정한 크기의 배열이 주어졌을 때 크 크기를 키우려면 새로운 공간에 큰 크기의 메모리를 할당하고 기존 배열의 값들을 하나씩 옮겨줘야한다.
- 이 작업을 realloc(원본 배열, 메모리크기)로 한번에 할 수 있다.
연결 리스트
- 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.
- 각 값이 메모리상의여러군데 나뉘어져 있더라도 다음 값의 메모리 주소만 기억하고 있으면 값을 연이어서 읽을 수있다. 이를 연결 리스트라고 한다.
- 연결리스트는 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.
- 연결리스트는 구조체로 정의할 수 있다.
typedef struct node
{
int number;
struct node *next;
}
node;- typedef struct 대신에 typedef struct node 라고 ‘node’를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함이다.
- 연결리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다.
- 연결리스트에 값을 추가하거나 검색하는 경우 해당하는 위치까지 연결 리스트의 각 node를 따라 이동해야한다. 그 실행시간은 O(n)이다.
- 배열은 임의 접근이 가능하기 때문에 정렬이 되어 있다면 O(log n)의 실행시간이 소요된다.
연결 리스트 : 트리
- 트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다.
- 가장 높은 층의 노드를 루트라고 하고 다음 층의 노드들을 자식 노드라고 한다.
- 사진은 이진 검색 트리이며, 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 크다.
- 검색 실행 시간과 노드 삽입 시간은 O(log n)이다.
해시 테이블
- 해시 테이블이란 연결리스트의 배열을 의미한다.
- 해시 함수란 해시 테이블에 값을 저장하는 방식을 의미한다.
- 위의 사진의 경우 해시 함수는 이름의 가장 첫 글자이다.
- 해시 함수가 이상적이라면 각 바구니에는 단 하나의 값만 담기기 때문에 검색 시간은 O(1)이다.
- 최악의 경우 한 바구니에 모든 값들이 담겨서 O(n)이 될수도 있다.
- 일반적으로는 O(1)에 가깝게 설계한다.
트라이
- 기본적으로 트리 형태의 자료구조이다.
- 각 노드가 배열로 이루어져있다는 점이 특징이다
- Hermione, Harry, Hagrid의 문자열을 트라이에 저장하기위해 첫번째 A~Z의 각 요소에 두번째 A~Z의 배열, 두번째 배열의 각 요소에 세번째 A~Z가 반복된다.
- 위의 트라이에서는 값을 검색하는데 걸리는 시간은 문자열의 길이에 한정된다. 단순히 문자열의 각 문자를 보며 트리를 탐색하면 되기 때문이다.
- 영어 이름의 길이가 n이라면 검색시간은 O(n)이지만, 대부분의 이름은 아무리 길더라도 상수값으로 취급할 수 있기 때문에 O(1)이라고 볼 수 있다.
- 검색 시간은 단축시킨 대신 상당한 메모리를 사용한다.
스택, 큐, 딕셔너리
큐
- 메모리 구조에서 아래로 쌓이는 구조이다.
- FIFO(선입 선출) 구조이며, 가장 먼저 들어온 값이 가장 먼저 나간다는 의미이다.
- 배열이나 연결 리스트를 통해 구현 가능하다.
스택
- 메모리 구조에서 위로 쌓이는 구조이다.
- LIFO(후입 선출) 구조이며, 가장 나중에 들어온 값이 가장 먼저 나간다.
- 역시 배열이나 연결 리스트로 구현 가능하다.
딕셔너리
- '키'와 '값'이라는 요소로 이루어져 있다.
- '키'에 해당하는 '값'을 저장하고 읽어온다. 해시 테이블과 동일한 개념이라고 볼 수 있다.
do for me