데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체이다
자료구조 : 컴퓨터에 정보를 각기 다른 방법으로 저장할 수 있도록 도와준다
두 개의 값을 가진 구조체도 자료구조이다
배열 : 쉽게 인덱싱할 수 있다 (빠르다)
링크드 리스트(연결 리스트)
-메모리 덩어리 여러 개를 포함한 데이터 구조
-각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다
node 구조체
typedef가 하는 일 : node 구조체에서 node로의 별칭을 제공
중간에 코드를 추가한 경우 업데이트 한 코드를 기존에 존재하는 코드와 연결하고
앞에 위치하는 코드를 업데이트 코드를 가리키게 한다
컴퓨터는 하나의 연결리스트를 볼 수 있다
배열과 비교하여 연결리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다
구조가 정적인 배열과 달리 유동적인 구조를 가진 연결 리스트에서는 임의접근이 불가능하다
연결리스트 값에 추가하거나 검색하는 경우 해당하는 위치까지 연결리스트의 각node들을 따라 이동해야 한다
->연결리스트의 크기가 n일 때 그 시간은 O(n)이 된다
배열의 경우 임의접근이 가능하기 때문에 정렬되어 있는 경우 이진 검색을 이용하면 O(log n)이 걸린다
-> 데이터 구조는 각각의 장단점이 있기 때문에 효율적인 데이터 구조를 고민해서 사용해야한다
트리
연결리스트는 유동적이지만 임의접근이 불가능하다
해결법 : 두 개의 포인터를 가진 node를 생성
struct node *left;
struct node *right;
이진 탐색 트리 : 트리의 노드들이 최대 두 개의 자식을 가지는 것이다
-모든 노드에서 오른쪽 자식이 더 크다
-root(뿌리)라고 불리는 제일 처음의 단계부터 탐색한다
재귀에 가장 적합한 방식이다
-> 트리는 2차원적이고 재귀적이다
실행시간의 상한 O(log n) 노드 삽입 시간 O(log n)
해시 테이블
일정한 시간을 가지는 자료구조
배열과 연결리스트를 조합한 것 : 해시테이블
해시함수 : 입력값을 받아서 출력값을 내보낸다 //함수이자 알고리즘
해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담기게 되어 검색 시간은 O(1)이 될 것이다
하지만, 첫 글자가 같은 이름이 두 개인 경우 오류가 발생할 수 있다
-> 첫 두 글자를 보게 만들면 충돌이 덜 할 것이다 공간은(메모리) 많아지지만 충돌확률이 낮아짐
->그럼에도 충돌은 난다 == 이상적이지 않다
-> 첫 세글자를 보게 한다 ->실행시간은 O(n)이 된다 //느려진다
얼마나 많은 저장공간을 쓸 것인지 함수를 어떻게 짤것인지 고려해야한다
tries : 트라이
각각의 노드가 배열로 이루어진 트리이다
이 자료구조에서는 고정된 상한 O(1)이 있다
->검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값(예, 20자 이내)이기 때문에
O(1)이나 마찬가지라고 볼 수 있다.
해시테이블에 비해 실행시간이 빠르지만 메모리 차지를 많이한다
큐(queues) : FIFO 선입 선출의 특징을 가진 자료구조 enqueue->dequeue
stack(스택) : LIFO 마지막에 입력한 것이 가장 먼저 출력된다 (후입선출) push->pop
딕셔너리 : 일종의 해시테이블이라 볼 수 있다 ‘키’와 ‘값’이라는 요소로 이루어져 있다.
//자바 컬렉션 클래스의 맵과 유사하다고 생각된다