Computer science/Data Structure

[자바스크립트] 큐(Queue) 자료구조 예시를 통해 쉽게 이해하기

큐(Queue) 자료구조란? 큐(Queue)는 가장 먼저 들어온 데이터가 가장 먼저 나가는(선입선출, FIFO(First In First Out)) 자료구조입니다. 일상생활에서도 쉽게 접할 수 있는데요. 영화관에서 영화를 보러 들어가기 위해 대기하거나, 비행기를 탑승하기 위해 대기를 할 때 먼저 줄을 선 사람이 먼저 들어가는 경우가 바로 큐 자료구조와 같습니다. 코드 구현 예시 굉장히 단순하게 구현할 경우 자바스크립트 배열 자료구조를 활용해서 쉽게 구현할 수 있습니다. 배열 활용 예시 배열의 push, pop, unshift, shift 메서드를 사용할 때 시간복잡도는 O(1)이지만, 데이터를 할당/제거 후 배열을 재구성해야되기 때문에 O(N) 복사 비용이 발생합니다. 그렇기 때문에 배열을 통해 구현할 ..

Computer science/Data Structure

[자바스크립트] 연결리스트(Linked List) 예시를 통해 쉽게 이해하기 (1)

연결리스트(Linked List)란? 연결리스트는 모든 요소(a.k.a 노드)가 다음 요소에 연결된 자료구조입니다. 예를 들어 학교의 한 반에 있는 학생들을 데이터로 저장한다면, 1번 학생 데이터를 노드로 생성할 때 2번 학생 데이터가 어디에 있는지 노드의 위치를 표시하는 방식입니다. 자료가 연결되어있기 때문에 새로운 자료를 앞쪽에 추가/삭제할 때 굉장히 유용하게 사용할 수 있습니다. 하지만 특정한 자료를 불러올 때는 무조건 순회하며 찾아가는 과정이 필요하기 때문에 특정한 노드를 찾기 까다롭다는 단점이 있습니다. 위 예시에서 3번 학생 데이터를 확인하기 위해선 2번 학생 데이터를 무조건 거쳐야 3번 학생 데이터가 어디있는지 알 수 있습니다. 만약 1만명의 학생들이 엮여있다면, 특정 학생을 찾을 때마다 꽤..

Computer science/Data Structure

자바스크립트로 구현한 선택정렬

자바스크립트로 구현한 선택 정렬입니다.