1. 배열
1) 고정된 크기를 가진다.
2) JS같은 스크립트언어는 자동으로 증감
3) JS는 인덱스를 문자나 논리값이 가능하나 문자열로 변환된 키값이 되고 이는 length에 영향을 미치지 않으므로 사용권장 X
4) 번호를 알고 있다면 O(1)로 원소를 찾는다.
5) 원소를 삭제하면 빈자리가 생긴다.
중간을 삭제,추가 후 순서를 맞추려면 O(n) 소요
추가 , 삭제가 반복되는 로직은 배열 사용을 권장하지 않는다.
=> 즉, 배열은 탐색에 유리한 자료구조이다.
2. 연결리스트
연결리스트 핵심로직
1) 요소 찾기 O(n)
2) 요소 추가 O(1) => 추가할 위치의 인덱스를 알 때 O(1)
3) 요소 삭제 O(1) => 삭제할 위치의 인덱스를 알 때 O(1)
연결리스트 종류
1) singly
2) Doubly
3) Circular
| 배열 | 연결리스트 |
|---|---|
| 연속된 메모리 사용 | 비연속적 메모리사용 |
| 중간요소 추가나 삭제 위해 O(n) 소모 | 추가 삭제를 위해 O(1) 소모 |
3. 문자열 순회
1) for of
2) for in
let a = 'abcde'
for(const val of a ){
console.log(val); //각줄마다 a, b, c, d,e 출력
}
for(const val in a ){
console.log(val,a[val]) //각 줄마다 0 a , 1 b , 2 c , 3 d , 4 e 순서로 출력
}4. 스택과 큐
1) 스택
1) Array
2) 연결리스트
2) 큐
- 선형 큐 (linear)
1) Array
2) 연결리스트- 환영 큐 (circular)
1) Array
2) 연결리스트
- 주의 : shift메소드는 queue에서 요구사항을 처리하지 못한다.
왜냐면 shift메소드는 O(n) 시간이 걸리고 queue는 O(1)시간을 원하기 때문이다.
5. 해쉬테이블
키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형자료구조
해쉬충돌 해결방법
1) 선형탐사법 : 충돌 발생시 한칸 옆 이동
2) 제곱탐사법
3) 이중해싱 : 해쉬함수 2번째꺼를 계속 진행
4) 분리연결법 : 해쉬테이블에 하나의 대상에 리스트로 추가
(한 리스트에 많이 쌓여 좋은 방법 X)
해쉬테이블 사용법
1) 배열
2) 객체
3) Map
4) Set
해쉬테이블 ex)
const table = {};
table["key"] = 100;
table["key2"] = "hello";
console.log(table["key"]); //100
table["key"] = 300;
console.log(table["key"]); //300
delete table["key2"];
console.log(table["key2"]); //undefined6.그래프
정점은 여러 간선을 가진다.
가중치를 가진다.
사이클 발생
방향성에 따라
1) 무방향그래프
2) 방향그래프
연결 상태에 따라
1) 연결그래프 : 모든 정점이 서로 이동가능
2) 비연결그래프 : 간선이 존재하지않는 그래프
3) 완전그래프 : 모든 정점끼리 연결
사이클이란?
- 정점과 간선 부분집합에서 순환이 되는 부분
그래프 구현방법
1) 인접 행렬
2) 인접리스트
