비디오 + 연습과 함께 설명되는 10 가지 공통 데이터 구조

“불량한 프로그래머들은 코드에 대해 걱정합니다. 훌륭한 프로그래머는 데이터 구조와 관계에 대해 걱정합니다.”— Linus Torvalds, Linux 제작자
** 업데이트 ** 알고리즘에 관한 비디오 코스가 생겼습니다! Manning Publications에서 동작중인 알고리즘을 확인하십시오. 코드 '39carnes'를 사용하여 코스를 39 % 할인 받으세요! 또는 코드 'vlcarnes2'를 사용하여 딥 러닝 인 모션 코스를 50 % 할인받을 수 있습니다.

데이터 구조는 소프트웨어 개발의 중요한 부분이며 개발자 면접 질문에 가장 일반적인 주제 중 하나입니다.

좋은 소식은 기본적으로 데이터를 구성하고 저장하기위한 특수 형식 일뿐입니다.

이 짧은 기사에서 가장 일반적인 10 가지 데이터 구조를 알려 드리겠습니다.

이러한 각 데이터 구조를 위해 만든 비디오를 포함 시켰습니다. 또한 각각의 코드 예제와 연결하여 JavaScript로 구현하는 방법을 보여줍니다.

연습을하기 위해 freeCodeCamp 커리큘럼의 과제에 연결했습니다.

이러한 데이터 구조 중 일부는 Big O 표기법의 시간 복잡성을 포함합니다. 시간 복잡도는 때때로 구현 방법에 따라 달라 지므로 모든 항목에 포함되지는 않습니다. Big O Notation에 대해 더 자세히 알고 싶다면 Briana Marie의 기사 또는이 비디오에 대한 기사를 확인하십시오.

또한 JavaScript로 이러한 데이터 구조를 구현하는 방법을 보여 주지만 C와 같은 저수준 언어를 사용하지 않는 한 대부분의 경우 직접 구현할 필요가 없습니다.

JavaScript (대부분의 고급 언어와 마찬가지로)에는 이러한 많은 데이터 구조가 기본적으로 구현되어 있습니다.

그럼에도 불구하고 이러한 데이터 구조를 구현하는 방법을 알고 있으면 개발자 구직에 큰 도움이되며 고성능 코드를 작성하려고 할 때 유용 할 수 있습니다.

연결된 목록

연결리스트는 가장 기본적인 데이터 구조 중 하나입니다. 많은 다른 데이터 구조가 배열 또는 링크 된 목록으로 구현 될 수 있기 때문에 배열과 비교되는 경우가 많습니다. 그들은 각각 장단점이 있습니다.

연결된 목록 표현

연결된 목록은 시퀀스를 함께 나타내는 노드 그룹으로 구성됩니다. 각 노드에는 저장되는 실제 데이터 (기본적으로 모든 유형의 데이터 일 수 있음)와 시퀀스의 다음 노드에 대한 포인터 (또는 링크)가 있습니다. 각 노드에 목록의 다음 항목과 이전 항목에 대한 포인터가있는 이중 연결 목록도 있습니다.

연결된 목록에서 가장 기본적인 작업은 목록에 항목을 추가하고 목록에서 항목을 삭제 한 다음 목록에서 항목을 검색하는 것입니다.

JavaScript의 링크 된 목록에 대한 코드는 여기를 참조하십시오.

연결된 목록 시간 복잡성
╔ ============ ╦ ========= ╦ ============= ╗
║ 알고리즘 ║ 평균 ║ 최악의 경우 ║
╠ ============ ╬ ========= ╬ ============= ╣
║ 공간 ║ O (n) ║ O (n) ║
║ 검색 ║ O (n) ║ O (n) ║
║ 삽입 ║ O (1) ║ O (1) ║
║ 삭제 ║ O (1) ║ O (1) ║
╚ ============ ╩ ========= ╩ ============= ╝

freeCodeCamp 도전

  • 링크 된 목록에서 노드 작업
  • 연결 목록 클래스 만들기
  • 연결된 목록에서 요소 제거
  • 링크 된 목록 내에서 검색
  • 인덱스로 링크 된 목록에서 요소 제거
  • 링크 된 목록의 특정 색인에 요소 추가
  • 이중 연결 목록 만들기
  • 이중 연결 목록 반전

스택

스택은 스택의 맨 위에있는 항목 만 삽입하거나 삭제할 수있는 기본 데이터 구조입니다. 그것은 책의 스택과 비슷합니다. 스택 중간에있는 책을 보려면 먼저 그 위에있는 모든 책을 꺼내야합니다.

스택은 LIFO (Last In First Out)로 간주됩니다. 스택에 마지막으로 넣은 항목은 스택에서 가장 먼저 나오는 항목입니다.

스택 표현

스택에서 수행 할 수있는 세 가지 주요 작업이 있습니다 : 스택에 항목 삽입 ( '푸시'), 스택에서 항목 삭제 ( '팝') 및 스택의 내용 표시 (때로는 'pip') ').

JavaScript의 스택 코드는 여기를 참조하십시오.

스택 시간 복잡성
╔ ============ ╦ ========= ╦ ============= ╗
║ 알고리즘 ║ 평균 ║ 최악의 경우 ║
╠ ============ ╬ ========= ╬ ============= ╣
║ 공간 ║ O (n) ║ O (n) ║
║ 검색 ║ O (n) ║ O (n) ║
║ 삽입 ║ O (1) ║ O (1) ║
║ 삭제 ║ O (1) ║ O (1) ║
╚ ============ ╩ ========= ╩ ============= ╝

freeCodeCamp 도전

  • 스택 작동 방법 알아보기
  • 스택 클래스 생성

대기열

식료품 점에서 줄을 사람들의 줄로 생각할 수 있습니다. 줄의 첫 번째는 첫 번째로 제공되는 것입니다. 대기열처럼.

큐 표현

대기열은 데이터에 액세스하는 방식을 보여주기 위해 FIFO (선입 선출)로 간주됩니다. 즉, 새 요소가 추가되면 새 요소를 제거하기 전에 이전에 추가 된 모든 요소를 ​​제거해야합니다.

대기열에는 대기열 및 대기열 제거의 두 가지 주요 작업이 있습니다. 대기열에 넣기는 대기열 뒷면에 항목을 삽입하는 것을 의미하고 대기열에 들어가는 것은 앞쪽 항목을 제거하는 것을 의미합니다.

JavaScript의 대기열 코드는 여기를 참조하십시오.

대기열 시간 복잡성
╔ ============ ╦ ========= ╦ ============= ╗
║ 알고리즘 ║ 평균 ║ 최악의 경우 ║
╠ ============ ╬ ========= ╬ ============= ╣
║ 공간 ║ O (n) ║ O (n) ║
║ 검색 ║ O (n) ║ O (n) ║
║ 삽입 ║ O (1) ║ O (1) ║
║ 삭제 ║ O (1) ║ O (1) ║
╚ ============ ╩ ========= ╩ ============= ╝

freeCodeCamp 도전

  • 대기열 클래스 만들기
  • 우선 순위 대기열 클래스 만들기
  • 순환 대기열 만들기

세트

표현 설정

세트 데이터 구조는 특정 순서없이 반복 된 값없이 값을 저장합니다. 세트에 요소를 추가 및 제거 할 수있을뿐만 아니라 한 번에 두 세트로 작동하는 몇 가지 다른 중요한 세트 기능이 있습니다.

  • Union — 서로 다른 두 세트의 모든 항목을 결합하고이를 중복없이 새 세트로 반환합니다.
  • 교차 — 두 세트가 주어지면이 함수는 두 세트의 일부인 모든 항목이있는 다른 세트를 반환합니다.
  • 차이 — 한 세트에는 있지만 다른 세트에는없는 항목 목록을 반환합니다.
  • 하위 집합 — 한 집합의 모든 요소가 다른 집합에 포함되어 있는지 여부를 나타내는 부울 값을 반환합니다.

JavaScript로 세트를 구현하는 코드를 보려면 여기를 클릭하십시오.

freeCodeCamp 도전

  • 세트 클래스 만들기
  • 세트에서 제거
  • 세트의 크기
  • 두 세트에 대한 연합 수행
  • 두 데이터 세트에 대한 교차 수행
  • 두 세트의 데이터에 대한 차이 수행
  • 두 세트의 데이터에 대한 서브 세트 확인 수행
  • ES6에서 세트 생성 및 추가
  • ES6의 세트에서 아이템 제거
  • ES6 세트에서 .has 및 .size 사용
  • ES5 Set () 통합을위한 스프레드 및 노트 사용

지도

맵은 모든 키가 고유 한 키 / 값 쌍으로 데이터를 저장하는 데이터 구조입니다. 맵을 연관 배열 또는 사전이라고도합니다. 빠른 데이터 조회에 자주 사용됩니다. 지도는 다음을 허용합니다.

지도 표현
  • 컬렉션에 페어 추가
  • 컬렉션에서 페어 제거
  • 기존 쌍의 수정
  • 특정 키와 관련된 값 조회

JavaScript로지도를 구현하는 코드를 보려면 여기를 클릭하십시오.

freeCodeCamp 도전

  • 지도 데이터 구조 만들기
  • ES6 자바 스크립트 맵 생성

해시 테이블

해시 테이블 및 해시 함수 표현

해시 테이블은 키 / 값 쌍을 포함하는 맵 데이터 구조입니다. 해시 함수를 사용하여 원하는 값을 찾을 수있는 버킷 또는 슬롯 배열로 인덱스를 계산합니다.

해시 함수는 일반적으로 문자열을 입력으로 사용하고 숫자 값을 출력합니다. 해시 함수는 항상 동일한 입력에 대해 동일한 출력 번호를 제공해야합니다. 두 개의 입력이 동일한 숫자 출력으로 해시 될 때이를 충돌이라고합니다. 목표는 충돌이 거의없는 것입니다.

따라서 키 / 값 쌍을 해시 테이블에 입력하면 키가 해시 함수를 통해 실행되고 숫자로 바뀝니다. 그런 다음이 숫자 값은 값이 저장된 실제 키로 사용됩니다. 동일한 키에 다시 액세스하려고하면 해싱 함수가 키를 처리하고 동일한 숫자 결과를 반환합니다. 그런 다음 숫자는 관련 값을 찾는 데 사용됩니다. 이는 평균적으로 매우 효율적인 O (1) 조회 시간을 제공합니다.

여기에서 해시 테이블의 코드를보십시오.

해시 테이블 시간 복잡성
╔ ============ ╦ ========= ╦ ============= ╗
║ 알고리즘 ║ 평균 ║ 최악의 경우 ║
╠ ============ ╬ ========= ╬ ============= ╣
║ 공간 ║ O (n) ║ O (n) ║
║ 검색 ║ O (1) ║ O (n) ║
║ 삽입 ║ O (1) ║ O (n) ║
║ 삭제 ║ O (1) ║ O (n) ║
╚ ============ ╩ ========= ╩ ============= ╝

freeCodeCamp 도전

  • 해시 테이블 만들기

이진 검색 트리

이진 검색 트리

트리는 노드로 구성된 데이터 구조이며 다음과 같은 특징이 있습니다.

  1. 각 트리에는 루트 노드가 있습니다 (맨 위에).
  2. 루트 노드에는 0 개 이상의 자식 노드가 있습니다.
  3. 각 자식 노드에는 0 개 이상의 자식 노드 등이 있습니다.

이진 검색 트리는 다음 두 가지 특성을 추가합니다.

  1. 각 노드에는 최대 2 개의 자식이 있습니다.
  2. 각 노드의 왼쪽 하위 항목은 현재 노드보다 작으며 오른쪽 하위 항목보다 작습니다.

이진 검색 트리를 사용하면 항목을 빠르게 조회, 추가 및 제거 할 수 있습니다. 그것들이 설정되는 방식은 평균적으로 각 비교가 연산이 트리의 절반을 건너 뛸 수있게하여 각 조회, 삽입 또는 삭제가 트리에 저장된 항목 수의 로그에 비례하는 시간을 갖도록합니다.

JavaScript에서 이진 검색 트리의 코드를 보려면 여기를 클릭하십시오.

이진 검색 시간의 복잡성
╔ ============ ╦ =========== ╦ ============= ╗
║ 알고리즘 ║ 평균 ║ 최악의 경우 ║
╠ ============ ╬ =========== ╬ ============= ╣
║ 공간 ║ O (n) ║ O (n) ║
║ 검색 ║ O (log n) ║ O (n) ║
║ 삽입 ║ O (log n) ║ O (n) ║
║ 삭제 ║ O (log n) ║ O (n) ║
╚ ============ ╩ =========== ╩ ============= ╝

freeCodeCamp 도전

  • 이진 검색 트리에서 최소값과 최대 값 찾기
  • 이진 검색 트리에 새 요소 추가
  • 이진 검색 트리에 요소가 있는지 확인
  • 이진 검색 트리의 최소 및 최대 높이 찾기
  • 이진 검색 트리에서 깊이 우선 검색 사용
  • 이진 검색 트리에서 너비 우선 검색 사용
  • 이진 검색 트리에서 리프 노드 삭제
  • 이진 검색 트리에서 자식이 하나 인 노드 삭제
  • 이진 검색 트리에서 두 자녀가있는 노드 삭제
  • 이진 트리 반전

시도

트리 ( 'try'로 발음 됨) 또는 접두사 트리는 일종의 검색 트리입니다. 트라이는 각 단계가 트라이의 노드 인 단계로 데이터를 저장합니다. Tries는 단어 자동 완성 기능과 같은 빠른 검색을 위해 단어를 저장하는 데 종종 사용됩니다.

트리 표현

언어 트리의 각 노드에는 한 글자의 단어가 포함됩니다. 당신은 한 번에 한 글자 씩 단어의 철자를 찾기 위해 트리의 가지를 따릅니다. 문자 순서가 트리의 다른 단어와 다를 때 또는 단어가 끝날 때 단계가 시작됩니다. 각 노드에는 문자 (데이터)와 노드가 단어의 마지막 노드인지 여부를 나타내는 부울이 포함됩니다.

이미지를 보면 단어를 만들 수 있습니다. 항상 맨 위의 루트 노드에서 시작하여 작동을 중단하십시오. 여기에 표시된 trie에는 ball, bat, doll, do, dork, dorm, send, sense라는 단어가 포함됩니다.

JavaScript의 트라이 코드를 보려면 여기를 클릭하십시오.

freeCodeCamp 도전

  • Trie Search Tree 만들기

이진 힙

이진 힙은 다른 유형의 트리 데이터 구조입니다. 모든 노드에는 최대 두 명의 자식이 있습니다. 또한 완전한 나무입니다. 이것은 모든 레벨이 마지막 레벨까지 완전히 채워지고 마지막 레벨은 왼쪽에서 오른쪽으로 채워짐을 의미합니다.

최소 및 최대 힙 표현

이진 힙은 최소 힙 또는 최대 힙일 수 있습니다. 최대 힙에서 상위 노드의 키는 항상 하위의 키보다 크거나 같습니다. 최소 힙에서 상위 노드의 키는 하위의 키보다 작거나 같습니다.

레벨 간의 순서는 중요하지만 동일한 레벨의 노드 순서는 중요하지 않습니다. 이미지에서 최소 힙의 세 번째 레벨 값이 10, 6 및 12임을 알 수 있습니다.이 숫자는 순서가 다릅니다.

JavaScript에서 힙 코드를 보려면 여기를 클릭하십시오.

이진 힙 시간 복잡성
╔ ============ ╦ =========== ╦ ============= ╗
║ 알고리즘 ║ 평균 ║ 최악의 경우 ║
╠ ============ ╬ =========== ╬ ============= ╣
║ 공간 ║ O (n) ║ O (n) ║
║ 검색 ║ O (n) ║ O (n) ║
║ 삽입 ║ O (1) ║ O (log n) ║
║ 삭제 ║ O (log n) ║ O (log n) ║
║ 엿보기 ║ O (1) ║ O (1) ║
╚ ============ ╩ =========== ╩ ============= ╝

freeCodeCamp 도전

  • 최대 힙에 요소 삽입
  • 최대 힙에서 요소 제거
  • 최소 힙으로 힙 정렬 구현

그래프

그래프는 노드 (정점이라고도 함)와 노드 간 연결 (에지라고 함)의 모음입니다. 그래프는 네트워크라고도합니다.

그래프의 한 예는 소셜 네트워크입니다. 노드는 사람이고 가장자리는 우정입니다.

방향성 그래프와 비 방향성 그래프의 두 가지 주요 유형이 있습니다. 무 방향 그래프는 노드 간 가장자리에 방향이없는 그래프입니다. 반면에 방향 그래프는 가장자리에 방향이있는 그래프입니다.

그래프를 나타내는 두 가지 일반적인 방법은 인접 목록과 인접 행렬입니다.

인접 행렬 그래프

인접 목록은 왼쪽이 노드이고 오른쪽이 연결된 다른 모든 노드를 나열하는 목록으로 표시 될 수 있습니다.

인접 행렬은 숫자의 격자로, 각 행 또는 열은 그래프에서 다른 노드를 나타냅니다. 행과 열의 교차점에는 관계를 나타내는 숫자가 있습니다. 0은 에지 또는 관계가 없음을 의미합니다. 하나는 관계가 있음을 의미합니다. 1보다 큰 숫자는 다른 가중치를 표시하는 데 사용될 수 있습니다.

순회 알고리즘은 그래프에서 노드를 순회하거나 방문하는 알고리즘입니다. 순회 알고리즘의 주요 유형은 너비 우선 탐색 및 깊이 우선 탐색입니다. 용도 중 하나는 노드가 루트 노드에 얼마나 가까운 지 확인하는 것입니다. 아래 비디오에서 JavaScript로 폭 넓은 검색을 구현하는 방법을 참조하십시오.

JavaScript의 인접 행렬 그래프에서 너비 우선 검색 코드를 참조하십시오.

인접성 목록 (그래프) 시간 복잡성
╔ ================= ╦ ============= ╗
║ 알고리즘 ║ 시간 ║
╠ ================= ╬ ============= ╣
║ 보관 ║ O (| V | + | E |) ║
Ver 정점 추가 ║ O (1) ║
Edge 모서리 추가 ║ O (1) ║
Ver 정점 제거 ║ O (| V | + | E |) ║
Edge 모서리 제거 ║ O (| E |) ║
║ 쿼리 ║ O (| V |) ║
╚ ================= ╩ ============= ╝

freeCodeCamp 도전

  • 인접 목록
  • 인접 행렬
  • 발생률 매트릭스
  • 너비 우선 검색
  • 깊이 우선 검색

Grokking Algorithms 책은 데이터 구조 / 알고리즘에 익숙하지 않고 컴퓨터 과학 배경이없는 경우이 주제에 대한 최상의 책입니다. 이해하기 쉬운 설명과 재미있는 손으로 그린 ​​그림 (Etsy의 수석 개발자 인 저자)이이 기사에 소개 된 일부 데이터 구조를 설명합니다.

또는 Manning Publications의 Motion in Algorithms in the book라는 책을 기반으로 내 비디오 코스를 확인할 수 있습니다. 코드 '39carnes'를 사용하여 코스를 39 % 할인 받으세요!