단순 구조

• 정수, 실수, 문자열, 논리

선형 구조

한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조

• 배열: 추가와 삭제가 반복되는 로직이면 권장하지 않음, 탐색이 많은 경우에 유리한 자료구조
• 연결 리스트: 추가와 삭제가 반복되는 로직에 권장됨
• 스택: LIFO(Last In First Out)
• 큐: FIFO(First In First Out)

큐(Queue)

• JS에서 shift 함수로 큐를 구현하지 말자! ⇒ shift는 선형 시간이 걸리기 때문에 효율이 좋지 않다!
• JS에서의 큐 구현

  class Queue {
    constructor() {
      this.queue = [];
      this.front = 0;
      this.rear = 0;
    }
  
    enqueue(inputValue) {
      this.queue[this.rear++] = inputValue;
    }
  
    dequeue() {
      const returnValue = this.queue[this.front];
      delete this.queue[this.front++];
      return returnValue;
    }
  
    peek() {
      return this.queue[this.front];
    }
  
    size() {
      return this.rear - this.front
    }
  }

해시 테이블(Hash Table)

• 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
• 삽입, 삭제, 탐색의 시간복잡도가 모두 O(1)
• Bucket: 각 테이블에 해당 하는 index를 말함
• 사용자 정보 관리 등에 유용함

해시 함수

• 입력 받은 값을 특정 범위 내 수로 변경하는 함수
• 해시 함수 결과가 동일한 경우 ⇒ 해시 충돌(Hash Collision) 발생

해시 충돌 해결 방법

1. 선형 탐사법: 충돌이 발생하면 한 칸 옆으로 이동
   • 단점: 특정 영역에 데이터가 몰릴 수 있음, 최악의 경우 탐색에 선형 시간이 걸릴 가능성이 있음
2. 제곱 탐사법: 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
3. 이중 해싱: 충돌이 발생하면 다른 해시 함수를 이용, 충돌이 발생하지 않을 때 까지 두번째 해시로 index를 계속 생성
4. 분리 연결법: 충돌이 발생한 버킷(인덱스)에 버킷의 값을 연결 리스트로 사용하여 값을 추가
   • 단점: 하나의 버킷에 값들이 무한정 늘어날 수 있는 가능성

JS에서 해시 테이블 구현

• Object로 구현

// Object를 이용
const hashTable = {};
hashTable['key'] = 10;
hashTable['key2'] = 'hi';
console.log(hashTable['key']); // 10
delete hashTable['key'];
console.log(hashTable['key']); // undefined

• Map으로 구현

// Map을 사용, Object도 Key로 사용 가능
const hashTable = new Map();
hashTable.set('key', 10);

//object를 key로 사용
const obj = { a: 2 };
hashTable.set(obj, 'aa');
console.log(hashTable.get(obj)); // a

hashTable.delete(obj);

console.log(hashTable.keys()); // { 'key' }
console.log(hashTable.values()); // { 10 }
hashTable.clear();
console.log(hashTable.keys()); // { }
console.log(hashTable.values()); // { }

• Set으로 구현

// key와 Value가 동일함
const hashTable = new Set();
hashTable.add('key');
hashTable.add('key2');
console.log(hashTable.has('key')); // true
hashTable.delete('key2');
console.log(hashTable.has('key2')); // false

비선형 구조

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적합

• 트리
• 그래프

그래프

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
• 정점(Node) 집합과 간선(Edge) 집합으로 표현할 수 있음
• 특징
  • 정점은 여래 개의 간선을 가질 수 있음
  • 크게 방향 그래프와 무방향 그래프로 나눌 수 있음
    • 무방향 그래프: 정점이 간선으로 이어진 경우 양방향으로 이동 가능( A→B와 B→A는 같은 간선으로 취급)
    • 방향 그래프: 간선에 바향성이 존재하는 그래프
  • 간선은 가중치를 가질 수 있음
  • 사이클이 발생할 수 있음 ⇒ 탐색 시 무한루프에 빠지지 않도록 사이클을 찾아야함
    • 사이클: 그래프의 정점과 간선이 부분 집합에서 순환되는 부분을 말함
• 연결 그래프: 모든 정점이 서로 이동 가능한 상태인 그래프
• 비연결 그래프: 정점에 연결된 간선이 0개인 정점이 존재하는 그래프
• 완전 그래프: 모든 정점끼리 연결된 상태인 그래프

JS 인접 행렬로 구현

• 행렬의 열 부분 ⇒ 시작 정점
• 행렬의 행 부분 ⇒ 도착 정점
• true로 간선이 연결된 것으로 설정
• 무방향 그래프의 경우 모든 값을 대칭으로 대입

const graph = Array.from(Array(5), () => Array.fill(false));
graph[0][1] = true; // 0에서 1로 가는 간선이 존재하는 경우

JS 인접 리스트로 구현

• 정점의 수 만큼 배열을 만든 후 연결할 정점을 배열에 추가

const graph = Array.from(Array(5), () => []);
graph[0].push(1) // 0에서 1로 가는 간선이 존재하는 경우

some()

• array 타입에서 사용 가능한 함수로 주어진 판별 함수를 실행하여 배열 안의 요소들 중 참이 되는 결과가 있는지 테스트한다.
• 판별 함수가 true를 반환하면 some은 true를 반환한다.
• 예시

  arr = [1, 2, 3, 4, 5, 6];
  
  console.log(arr.some((num) => num > 5)); // true
  console.log(arr.some((num) => num > 7)); // false