알아야 할 Java의 상위 데이터 구조 및 알고리즘

소프트웨어 개발에서 가장 중요한 하나의 주제를 선택해야한다면 데이터 구조와 알고리즘이 될 것입니다. 모든 컴퓨터 프로그래머가 사용할 수있는 기본 도구로 생각할 수 있습니다. 프로그래밍하는 동안 우리는 데이터 구조 데이터 저장 및 구성 알고리즘 해당 구조의 데이터를 조작합니다. 이 기사에는 모든 일반적인 데이터 구조 및 알고리즘에 대한 자세한 검토가 포함되어 있습니다. 독자가 잘 갖추게 할 수 있습니다.

이 기사에서 논의되는 주제는 다음과 같습니다.

• 자바의 데이터 구조
  • 선형 데이터 구조
  • 계층 적 데이터 구조
• 자바의 알고리즘
  • 알고리즘 정렬
  • 알고리즘 검색

자바의 데이터 구조

데이터 구조는 데이터를 효율적으로 사용할 수 있도록 컴퓨터에 데이터를 저장하고 구성하는 방법입니다. 대량의 데이터를 효율적으로 관리 할 수있는 수단을 제공합니다. 효율적인 데이터 구조는 효율적인 알고리즘 설계의 핵심입니다.

에이 '자바의 데이터 구조 및 알고리즘'기사에서는 다음과 같은 기본 데이터 구조를 다룰 것입니다.

• 선형 데이터 구조
  • 연결된 목록
  • 스택
  • 대기열

• 계층 적 데이터 구조
  • 이진 트리
  • 힙
  • 해시 테이블

각각을 확인해 보겠습니다.

자바의 선형 데이터 구조

선형 데이터 구조 요소가 순차적이고 순서대로 정렬 된 요소입니다. 첫 번째 요소 그리고 하나만 있습니다 다음 요소 , 하나만 있습니다 마지막 요소 그리고 하나만 있습니다 이전 요소 , 다른 모든 요소에는 다음 그리고 이전 요소.

배열

안 정렬 선형 데이터 구조입니다.색인으로 액세스되는 유사한 요소 그룹을 나타냅니다. 데이터를 저장하기 전에 배열의 크기를 제공해야합니다. 다음은 배열의 속성입니다.

• 배열의 각 요소는 데이터 유형이 동일하고 크기가 동일합니다.
• 배열의 요소는 첫 번째 요소가 가장 작은 메모리 위치에서 시작하는 연속 메모리 위치에 저장됩니다.
• 배열의 요소는 무작위로 액세스 할 수 있습니다.
• 배열 데이터 구조는 완전히 동적이 아닙니다.

예를 들면 , 비디오 게임에서 해당 게임의 상위 10 개 점수를 추적 할 수 있습니다. 열 가지를 사용하는 것보다 변수 이 작업에서는 전체 그룹에 대해 단일 이름을 사용하고 인덱스 번호를 사용하여 해당 그룹의 최고 점수를 참조 할 수 있습니다.

연결된 목록

에 다중 노드 모음이있는 선형 데이터 구조입니다. 여기서 e각 요소는 자체 데이터와 다음 요소의 위치에 대한 포인터를 저장합니다. 연결된 목록의 마지막 링크는 null을 가리키며 체인의 끝을 나타냅니다. 연결 목록의 요소를 마디 . 첫 번째 노드는 머리 .마지막 노드가 호출됩니다.그만큼 꼬리 .

연결된 목록의 유형

단일 연결 목록 (단방향)

이중 연결 목록 (양방향)

순환 연결 목록

다음은 간단한 예입니다. 서로 연결된 클립 체인과 같은 연결된 목록을 상상해보십시오. 상단 또는 하단에 다른 클립을 쉽게 추가 할 수 있습니다. 중간에 삽입하는 것도 빠릅니다. 중간에있는 체인을 분리하고 새 클립을 추가 한 다음 나머지 절반을 다시 연결하기 만하면됩니다. 연결 목록도 비슷합니다.

스택

스택, 추상적 인 데이터 구조는 사물 에 따라 삽입 및 제거되는 후입 선출 (LIFO) 원리. 객체는 언제든지 스택에 삽입 할 수 있지만 가장 최근에 삽입 된 (즉, '마지막') 객체 만 언제든지 제거 할 수 있습니다.다음은 스택의 속성입니다.

• 정렬 된 목록입니다.삽입 및 삭제는라는 한쪽 끝에서만 수행 할 수 있습니다. 상단
• 상위 요소에 대한 포인터가있는 재귀 데이터 구조
• 다음을 따릅니다 후입 선출 (LIFO) 원리
• 가장 기본적인 두 가지 방법 지원
  • push (e) : 요소 e를 스택 맨 위에 삽입합니다.
  • pop () : 스택의 최상위 요소를 제거하고 반환합니다.

스택의 실제 예에는 단어를 뒤집을 때가 포함됩니다.,정확성을 확인하기 위해 괄호순서,브라우저 등에서 기능을 다시 구현합니다.

대기열

또 다른 유형의 추상 데이터 구조입니다. 스택과는 달리 대기열은 다음에 따라 삽입 및 제거되는 개체의 모음입니다. 선입 선출 (FIFO) 원리. 즉, 요소는 언제든지 삽입 할 수 있지만 대기열에 가장 오래 있었던 요소 만 언제든지 제거 할 수 있습니다.다음은 대기열의 속성입니다.

• 종종 선입 선출 명부
• 가장 기본적인 두 가지 방법 지원
  • enqueue (e) : 요소 e를 후방 대기열의
  • dequeue () : 제거하고 앞 대기열의

대기열은두 프로세스 간의 비동기 데이터 전송, CPU 스케줄링, 디스크 스케줄링 및 여러 사용자가 자원을 공유하고 선착순 서버 기반으로 서비스를 제공하는 기타 상황. 다음으로이 '자바의 데이터 구조 및 알고리즘'기사에는 계층 적 데이터 구조가 있습니다.

Java의 계층 적 데이터 구조

이진 트리

이진 트리는계층 적 트리 데이터 구조 각 노드에는 최대 2 개의 자식이 있습니다. , 이는 왼쪽 아이 그리고 오른쪽 아이 . 각 바이너리 트리에는 다음과 같은 노드 그룹이 있습니다.

• 루트 노드 : 최상위 노드이며 주 노드라고도합니다.다른 모든 노드는 루트에서 도달 할 수 있기 때문에
• 이진 트리이기도 한 왼쪽 하위 트리
• 이진 트리이기도 한 오른쪽 하위 트리

이진 트리의 속성은 다음과 같습니다.

• 이진 트리는 두 가지 방법으로 순회 할 수 있습니다.
  • Depth First Traversal : In-order (Left-Root-Right), Preorder (Root-Left-Right), Postorder (Left-Right-Root)
  • 폭 우선 순회 : 레벨 순서 순회
• 트리 탐색의 시간 복잡성 : O (n)
• 레벨‘l’의 최대 노드 수 = 2^l-1.

이진 트리의 응용 프로그램은 다음과 같습니다.

• 데이터가 지속적으로 들어오고 나가는 많은 검색 애플리케이션에서 사용됩니다.
• 시각 효과를 위해 디지털 이미지를 합성하는 워크 플로
• 라우터 테이블을 저장하기 위해 거의 모든 고 대역폭 라우터에서 사용됩니다.
• 무선 네트워킹 및 메모리 할당에도 사용됩니다.
• 압축 알고리즘 등에 사용됨

바이너리 힙

바이너리 힙은 완전한이진 트리, 힙 속성에 대한 응답입니다. 간단히 말해서다음 속성을 가진 이진 트리의 변형입니다.

• 힙은 완전한 이진 트리입니다. 가장 깊은 수준을 제외하고 모든 수준이 완료되면 트리는 완료되었다고합니다. 티그의 Binary Heap 속성은 .
• 힙 속성을 따릅니다. 바이너리 힙은 최소 힙 또는 최대 힙 .
  • 최소 바이너리 힙 : F또는 힙의 모든 노드에서 노드의 값은 보다 작거나 같음 아이들의 가치
  • 최대 바이너리 힙 : F또는 힙의 모든 노드에서 노드의 값은 보다 크거나 같음 아이들의 가치

바이너리 힙의 인기있는 응용 프로그램은 다음과 같습니다.효율적인 우선 순위 대기열을 구현하고 배열에서 가장 작은 (또는 가장 큰) 요소 k 개 등을 효율적으로 찾습니다.

해시 테이블

당신이 가지고 있다고 상상해보십시오 목적 매우 쉽게 검색 할 수 있도록 키를 할당하려고합니다. 해당 키 / 값 쌍을 저장하려면 키 (정수)를 데이터 값을 저장하는 인덱스로 직접 사용할 수있는 데이터 구조와 같은 간단한 배열을 사용할 수 있습니다. 그러나 키가 너무 커서 인덱스로 직접 사용할 수없는 경우에는 해싱이라는 기술이 사용됩니다.

해싱에서 큰 키는 다음을 사용하여 작은 키로 변환됩니다. 해시 함수 . 그런 다음 값은 다음과 같은 데이터 구조에 저장됩니다....에 해시 테이블. 해시 테이블은 고유 키를 값에 매핑 할 수있는 구조 인 사전 ADT를 구현하는 데이터 구조입니다.

일반적으로 해시 테이블에는 두 가지 주요 구성 요소가 있습니다.

1. 버킷 어레이 : 해시 테이블의 버킷 배열은 크기 N의 배열 A입니다. 여기서 A의 각 셀은 '버킷', 즉 키-값 쌍의 모음으로 간주됩니다. 정수 N은 어레이의 용량을 정의합니다.
2. 해시 기능 : 맵의 각 키 k를 [0, N & minus 1] 범위의 정수로 매핑하는 함수입니다. 여기서 N은이 테이블에 대한 버킷 배열의 용량입니다.

객체를 해시 테이블에 넣을 때 다른 객체가 동일한 해시 코드를 가질 수 있습니다. 이것은 충돌 . 충돌을 처리하기 위해 연결 및 개방 주소 지정과 같은 기술이 있습니다.

Power bi의 dax는 무엇입니까

따라서 이들은 Java에서 기본적이고 가장 자주 사용되는 데이터 구조입니다. 이제 이러한 각 항목을 알고 있으므로 . 이것으로 '자바의 데이터 구조 및 알고리즘'기사의 첫 번째 부분을 완료했습니다. 다음 부분에서 우리는기본 알고리즘 및 정렬 및 검색, 분할 및 정복, 탐욕스러운 알고리즘, 동적 프로그래밍과 같은 실제 응용 프로그램에서 사용하는 방법.

자바의 알고리즘

역사적으로 복잡한 수학적 계산을 해결하기위한 도구로 사용 된 알고리즘은 컴퓨터 과학, 특히 데이터 구조와 깊이 관련되어 있습니다. 알고리즘은 한정된 시간 내에 특정 문제를 해결하는 방법을 설명하는 일련의 지침. 두 가지 방법으로 표시됩니다.

• 순서도 - 이것은알고리즘의 제어 흐름을 시각적으로 표현
• 의사 코드 – 그것최종 소스 코드에 가까운 알고리즘의 텍스트 표현입니다.

노트 : 알고리즘의 성능은 시간 복잡성과 공간 복잡성을 기반으로 측정됩니다. 대부분의 알고리즘의 복잡성은 문제와 알고리즘 자체에 따라 다릅니다.

Java에서 두 가지 주요 알고리즘 범주를 살펴 보겠습니다.

• 자바의 정렬 알고리즘
• 자바에서 알고리즘 검색

자바의 정렬 알고리즘

정렬 알고리즘은 목록의 요소를 특정 순서로 배치하는 알고리즘입니다. 가장 일반적으로 사용되는 순서는 숫자 순서와 사전 순서입니다. 이 '데이터 구조 및 알고리즘'기사에서 몇 가지 정렬 알고리즘을 살펴볼 수 있습니다.

자바의 버블 정렬

싱킹 정렬이라고도하는 버블 정렬은 가장 간단한 정렬 알고리즘입니다. 정렬 할 목록을 반복적으로 살펴보고 인접한 요소의 각 쌍을 비교하고 순서가 잘못된 경우 서로 바꿉니다.거품 정렬은 물 위에 떠있는 거품과 같이 배열의 맨 위에있는 요소를 필터링하기 때문에 그 이름이 붙습니다.

여기에버블 정렬 알고리즘 (오름차순 정렬 컨텍스트)을 나타내는 의사 코드.

a []는 크기 N의 배열입니다. 시작 BubbleSort (a []) 정수 i 선언, i = 0 ~ N-1이면 j = 0 ~ N-i-1 if a [j]> a [j + 1 ] 그런 다음 a [j], a [j + 1] end if end if end for return a end BubbleSort를 바꿉니다.

이 코드는 N 데이터 항목의 1 차원 배열을 오름차순으로 정렬합니다. 외부 루프는 N-1이 어레이를 통과하도록합니다. 각 패스는 내부 루프를 사용하여 데이터 항목을 교환하여 다음으로 가장 작은 데이터 항목이 어레이의 시작 부분을 향해 '버블 링'되도록합니다. 그러나 문제는 알고리즘이 목록이 정렬되었음을 알기 위해 스왑없이 하나의 전체 패스가 필요하다는 것입니다.

최악의 평균 케이스 시간 복잡성 : O (n * n). 최악의 경우는 배열이 역 정렬 될 때 발생합니다.

최상의 시간 복잡성 : 의 위에). 배열이 이미 정렬 된 경우 최상의 경우가 발생합니다.

자바에서 선택 정렬

선택 정렬은 검색과 정렬의 조합입니다. 알고리즘은 정렬되지 않은 부분에서 최소 요소 (오름차순 고려)를 반복적으로 찾아 배열의 적절한 위치에 배치하여 배열을 정렬합니다.

다음은 선택 정렬 알고리즘 (오름차순 정렬 컨텍스트)을 나타내는 의사 코드입니다.

a []는 크기 N의 배열입니다. i = 0 ~ n-1에 대해 SelectionSort (a []) 시작 / * 현재 요소를 최소값으로 설정 * / min = i / * 최소 요소를 찾습니다. * / for j = i + 1 목록 [j] 인 경우 n
코드에서 알 수 있듯이 정렬이 배열을 통과하는 횟수는 배열의 항목 수보다 하나 적습니다. 내부 루프는 다음으로 가장 작은 값을 찾고 외부 루프는 해당 값을 적절한 위치에 배치합니다. 선택 정렬은 O (n) 스왑 이상을 만들지 않으며 메모리 쓰기에 비용이 많이 드는 작업 일 때 유용 할 수 있습니다.
 시간 복잡성 : 의 위에2) 두 개의 중첩 루프가 있기 때문입니다.
 보조 공간 : 또는 (1).
 자바에서 삽입 정렬 
삽입 정렬은 한 번에 하나의 입력 요소를 사용하여 목록을 반복하고 최종 정렬 된 배열을 작성하는 간단한 정렬 알고리즘입니다. 더 작은 데이터 세트에서 매우 간단하고 효과적입니다. 안정적이고 내부 분류 기술입니다.
다음은 삽입 정렬 알고리즘 (오름차순 정렬 컨텍스트)을 나타내는 의사 코드입니다.
a []는 크기 N의 배열입니다 .InsertionSort (a []) for i = 1 to N key = a [i] j = i-1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j-1 끝인 동안 a [j + 1] = 끝을위한 키 끝 InsertionSort
코드에서 알 수 있듯이 삽입 정렬 알고리즘은입력 데이터에서 하나의 요소를 제거하고 정렬 된 목록 내에서 해당 요소가 속한 위치를 찾아 여기에 삽입합니다. 정렬되지 않은 입력 요소가 없을 때까지 반복됩니다.
 최상의 사례 : 가장 좋은 경우는 입력이 이미 정렬 된 배열 인 경우입니다. 이 경우 삽입 정렬에는 선형 실행 시간이 있습니다 (예 : & Theta (n)).
 최악의 경우:  가장 간단한 최악의 경우 입력은 역순으로 정렬 된 배열입니다.
 Java의 QuickSort 
Quicksort 알고리즘은 분할 및 정복 원칙에 따라 작동하는 빠르고 재귀 적이며 불안정한 정렬 알고리즘입니다. 요소를 피벗으로 선택하고 선택한 피벗 주위에 지정된 배열을 분할합니다.
 빠른 정렬을 구현하는 단계 :  
 
적절한 '피벗 포인트'를 선택합니다.
목록을 두 목록으로 나누기이 피벗 요소를 기반으로합니다. 피벗 요소보다 작은 모든 요소는 왼쪽 목록에 배치되고 더 큰 모든 요소는 오른쪽 목록에 배치됩니다. 요소가 피벗 요소와 같으면 모든 목록에 들어갈 수 있습니다. 이를 파티션 작업이라고합니다.
각각의 작은 목록을 재귀 적으로 정렬합니다. 
다음은 Quicksort 알고리즘을 나타내는 의사 코드입니다.
QuickSort (A as array, low as int, high as int) {if (low
위의 의사 코드에서 분할() 함수는 파티션 작업을 수행하고 Quicksort () 함수는 생성 된 각 작은 목록에 대해 파티션 함수를 반복적으로 호출합니다. 평균적인 경우 퀵 정렬의 복잡성은 & Theta (n log (n))이고 최악의 경우 & Theta (n2)입니다.
 Java에서 정렬 병합 
Mergesort는 분할 및 정복 원칙에 따라 작동하는 빠르고 재귀 적이며 안정적인 정렬 알고리즘입니다. 빠른 정렬과 유사하게 병합 정렬은 요소 목록을 두 개의 목록으로 나눕니다. 이러한 목록은 독립적으로 정렬 된 다음 결합됩니다. 목록을 조합하는 동안 요소는 목록의 올바른 위치에 삽입 (또는 병합)됩니다.
다음은 병합 정렬 알고리즘을 나타내는 의사 코드입니다.
procedure MergeSort (a as array) if (n == 1) var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end procedure procedure merge (a as array, b as array) var c as array while (a and b have elements) if ( a [0]> b [0]) c 끝에 b [0] 추가 b에서 b [0] 제거 그렇지 않으면 c 끝에 a [0] 추가 c 끝에 a [0] 제거 (a에는 요소가 있습니다.) c 끝에 a [0]을 추가하고 끝에서 a [0]을 제거하는 동안 (b에는 요소가 있습니다.) c 끝에 b [0]을 추가하고 b 끝에서 b [0]을 제거합니다. c 종료 절차
 mergesort () 함수는 목록을 두 개로 나눕니다. mergesort () 이 목록에 개별적으로 추가 한 다음 merge () 함수에 매개 변수로 전송하여 결합합니다.알고리즘은 O (n log (n))의 복잡성을 가지고 있으며 다양한 응용 프로그램을 가지고 있습니다.
 자바의 힙 정렬 
Heapsort는 비교 기반 정렬 알고리즘입니다.바이너리 힙 데이터 구조. 개선 된 버전 f 선택 정렬이라고 생각할 수 있습니다.입력을 정렬 된 영역과 정렬되지 않은 영역으로 나누고 가장 큰 요소를 추출하고 정렬 된 영역으로 이동하여 정렬되지 않은 영역을 반복적으로 축소합니다.
 Quicksort 구현 단계 (오름차순) : 
정렬 배열로 최대 힙 빌드
이 지점에서t, 가장 큰 항목이 힙의 루트에 저장됩니다. 힙의 마지막 항목으로 바꾸고 힙의 크기를 1만큼 줄입니다. 마지막으로 트리의 루트를 힙화하십시오.
힙 크기가 1보다 클 때까지 위 단계를 반복하십시오.
다음은 힙 정렬 알고리즘을 나타내는 의사 코드입니다.
Heapsort (a as array) for (i = n / 2-1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) large = i // Initialize large as root int l eft = 2 * i + 1 // left = 2 * i + 1 int right = 2 * i + 2 // 오른쪽 = 2 * i + 2 if (왼쪽 a [최대]) 최대 = 왼쪽 if (오른쪽 a [최대]) 최대 = 오른쪽 if (최대! = i) swap ( a [i], A [가장 큰]) 힙화 (a, n, 최대) 끝 힙화
이 외에도 Introsort, Counting Sort 등과 같이 잘 알려지지 않은 다른 정렬 알고리즘이 있습니다.이 '데이터 구조 및 알고리즘'기사에서 다음 알고리즘 세트로 이동하여 검색 알고리즘을 살펴 보겠습니다.
 자바에서 알고리즘 검색 
검색은 일반 비즈니스 응용 프로그램에서 가장 일반적이고 자주 수행되는 작업 중 하나입니다. 검색 알고리즘은 항목 모음 중에서 지정된 속성을 가진 항목을 찾기위한 알고리즘입니다. 가장 일반적으로 사용되는 두 가지 검색 알고리즘을 살펴 보겠습니다.
 자바의 선형 검색 알고리즘 
선형 검색 또는 순차 검색은 가장 간단한 검색 알고리즘입니다. 요소를 찾거나 구조의 끝에 도달 할 때까지 주어진 데이터 구조에서 요소를 순차적으로 검색합니다. 요소가 발견되면 항목의 위치가 반환되고 그렇지 않으면 알고리즘이 NULL을 반환합니다.
다음은 자바에서 선형 검색을 나타내는 의사 코드입니다.
절차 linear_search (a [], value) for i = 0 to n-1 if a [i] = value then print 'Found'return i end if print 'Not found'end for end linear_search
이것은무차별 대입 알고리즘.확실히 가장 단순하지만 비 효율성 때문에 가장 일반적이지 않습니다. 선형 검색의 시간 복잡성은 의 위에) .
 자바의 바이너리 검색 알고리즘 
로그 검색이라고도하는 이진 검색은 이미 정렬 된 배열 내에서 대상 값의 위치를 ​​찾는 검색 알고리즘입니다. 입력 컬렉션을 동일한 절반으로 나누고 항목을 목록의 중간 요소와 비교합니다. 요소가 발견되면 검색이 종료됩니다. 그렇지 않으면 대상 요소가 중간 요소보다 작거나 큰지 여부에 따라 배열의 적절한 파티션을 나누고 선택하여 요소를 계속 찾습니다.
다음은 Java에서 이진 검색을 나타내는 의사 코드입니다.
절차 binary_search 정렬 된 배열 검색 할 배열 x 값의 n 크기 lowerBound = 1 upperBound = n while x not found if upperBound
검색은 upperBound (포인터)가 lowerBound (마지막 요소)를 지나갈 때 종료됩니다. 이는 전체 배열을 검색했고 요소가 존재하지 않음을 의미합니다.주로 빠른 검색 시간으로 인해 가장 일반적으로 사용되는 검색 알고리즘입니다. 이진 검색의 시간 복잡성은 다음과 같습니다. 의 위에) 그것은 현저한 개선입니다 의 위에) 선형 검색의 시간 복잡성.
이것으로이 '자바의 데이터 구조 및 알고리즘'기사를 마치겠습니다. Java의 가장 기본적이고 중요한 주제 중 하나를 다루었습니다.이 기사에서 여러분과 공유 한 모든 내용이 명확하기를 바랍니다.
  가능한 한 많이 연습하고 경험을 되 돌리십시오.   
 확인    전 세계에 250,000 명 이상의 만족 한 학습자 네트워크를 보유한 신뢰할 수있는 온라인 학습 회사 인 Edureka에서 작성했습니다. 우리는 당신의 여정의 모든 단계에서 당신을 돕기 위해 여기에 있습니다.이 자바 인터뷰 질문 외에 우리는 자바 개발자가 되고자하는 학생과 전문가를 위해 고안된 커리큘럼을 제안합니다. 
 질문이 있으십니까? 이 '자바의 데이터 구조 및 알고리즘'의 주석 섹션에 언급하십시오.  기사와 우리는 가능한 한 빨리 당신에게 돌아갈 것입니다.