데이터 구조-소개

 

DS Introduction - javatpoint

소개

데이터 구조는 데이터를 효율적으로 사용할 수 있도록 컴퓨터에 데이터를 저장하고 구성하는 효율적인 방법을 제공하는 데이터 요소들의 그룹으로 정의할 수 있습니다. 
데이터 구조의 몇 몇 예는 배열, Linked List, 스택, 큐 등이 있습니다. 
데이터 구조는 운영 체제, 컴파일러 설계, 인공 지능, 그래픽 등 컴퓨터 과학의 거의 모든 분야에서 널리 사용됩니다.
데이터 구조는 프로그래머가 효율적인 방식으로 데이터를 처리할 수 있도록 해 주는 여러 분야의 컴퓨터 과학 알고리즘의 주요 부분입니다.
소프트웨어의 주요 기능은 사용자의 데이터를 가능한 한 빨리 저장하고 검색하는 것이기 때문에 소프트웨어 또는 프로그램의 성능을 향상시키는 데 중요한 역할을 합니다.

기본 용어

데이터 구조는 어떤 프로그램 또는 소프트웨어의 빌딩 블록입니다. 
프로그램에 적합한 데이터 구조를 선택하는 것은 프로그래머에게 가장 어려운 작업입니다.
다음은 데이터 구조에서 사용되는 관심을 가져야 할 용어입니다.

데이터:

데이터는 기본 값 또는 값의 모음으로 정의할 수 있습니다. 예를 들어 학생에 대한 데이터는 학생의 이름과 ID가 됩니다.

그룹 항목:

하위 데이터 항목이 있는 데이터 항목을 그룹 항목이라고 합니다. 예를 들어 학생의 이름은 이름과 성을 가질 수 있습니다.

레코드:

레코드은 다양한 데이터 항목의 모음으로 정의할 수 있습니다. 예를 들어 학생 엔터티라는 것은 이름, 주소, 과정 및 점수를 함께 그룹화한 학생에 대한 레코드로 만들어 질 수 있습니다.

파일:

파일은 한 유형의 엔터티에 대한 다양한 레코드 모음입니다. 예를 들어 클래스에 60명의 직원이 있다면, 각 레코드는 해당 직원에 대한 데이터가 포함된 관련 파일이 있고 이 파일은 20개의 레코드가 쓰여질 것입니다.

속성 및 엔터티:

엔터티는 특정 객체들의 클래스를 나타냅니다. 여기에는 다양한 속성이 포함되어 있습니다. 각 속성은 해당 엔터티의 특정 속성을 나타냅니다.

필드:

필드는 엔터티의 속성을 나타내는 단일 기본 정보 단위입니다.

데이터 구조의 필요성

응용 프로그램이 복잡해지고 데이터 양이 날로 증가함에 따라 다음과 같은 문제가 발생할 수 있습니다:

 

프로세서 속도:

매우 많은 양의 데이터를 처리하기 위해서는 고속 처리가 필요하지만 날마다 데이터가 엔터티당 수십억 개의 파일로 증가하게 되면 프로세서가 그 많은 양의 데이터를 처리하지 못할 수 있습니다.

 

데이터 검색:

106개 항목의 재고 개수를 가진 상점을 생각해 봅시다. 만약 응용 프로그램이 특정 항목을 검색해야 해야 한다면, 매번 106개 항목을 탐색해야 하므로 검색 프로세스가 느려집니다.

 

다중 요청:

수천 명의 사용자가 웹 서버에서 동시에 데이터를 검색하는 경우 대용량 서버도 해당 프로세싱 중에 실패할 가능성이 있습니다.

위의 문제를 해결하기 위해 데이터 구조를 사용합니다. 모든 항목을 검색할 필요 없이 필요한 데이터를 바로 검색할 수 있도록 데이터 구조를 구성 할 수 있을 것입니다.

데이터 구조의 장점

효율성:

프로그램의 효율성은 데이터 구조의 선택에 따라 달라집니다. 
예를 들어, 우리는 어떤 데이터를 가지고 있고 특정 레코드에 대한 검색을 수행해야 한다고 가정합시다. 
이 경우 데이터를 배열로 구성하면 요소별로 순차적으로 검색해야 알 것입니다. 
따라서 이 경우 배열을 사용하는 것은 그다지 효율적이지 않을 수 있습니다. 
검색 프로세스를 효율적으로 만들 수 있는 더 나은 데이터 구조인 정렬된 배열, 이진 검색 트리 또는 해시 테이블 등이 존재합니다.

 

재사용성:

데이터 구조는 재사용 가능합니다. 
즉, 특정 데이터 구조를 구현해 놓으면 다른 곳에서 사용할 수 있습니다. 다른 클라이언트에서 사용할 수 있도록 이 데이터 구조 구현물은 라이브러리로 컴파일될 수 있습니다.

추상화:

데이터 구조는 추상화 수준을 제공하는 ADT에 의해 지정됩니다. 클라이언트 프로그램은 구현 세부 사항에 들어가지 않고 인터페이스를 통해서만 데이터 구조를 사용합니다.

데이터 구조 분류

선형 데이터 구조:

데이터 구조의 모든 요소가 선형 순서로 배열된 경우 데이터 구조를 선형이라고 합니다. 
선형 데이터 구조에서 요소는 첫 번째 요소와 마지막 요소를 제외하고 각 요소가 후속 요소와 선행 요소를 갖는 비계층적 방식으로 저장됩니다.

선형 데이터 구조의 유형은 다음과 같습니다.

배열:

배열은 비슷한 유형의 데이터 항목 모음이며 각 데이터 항목을 배열의 요소라고 합니다. 
요소의 데이터 유형은 char, int, float 또는 double과 같은 유효한 데이터 유형일 수 있습니다.
배열의 요소는 동일한 변수 이름을 공유하지만 각 요소는 첨자로 알려진 서로 다른 인덱스 번호를 가지고 다닙니다. 배열은 1차원, 2차원 또는 다차원일 수 있습니다.

배열 연령의 개별 요소는 다음과 같습니다.
age[0], age[1], age[2], age[3],......... age[98], age[99].

Linked List:

Linked List는 메모리에 목록을 유지하는 데 사용되는 선형 데이터 구조입니다. 
이 구조는 비연속 메모리 위치에 저장된 노드 모음으로 볼 수 있습니다.

목록의 각 노드에는 인접 노드에 대한 포인터가 포함됩니다.

 

스택:

스택은 한쪽 끝, 즉 top에서만 삽입 및 삭제가 허용되는 선형 목록입니다.
스택은 추상 데이터 유형(ADT)이며 대부분의 프로그래밍 언어로 구현할 수 있습니다. 
실 세계의 스택처럼 동작하기 때문에 이름도 스택으로 지었습니다.

예를 들어: - 플레이트 더미 또는 카드 데크 등

큐(Queue):

큐는 요소가 한쪽 끝 즉, rear에서만 삽입할수 있고, front 다른 쪽 끝에서만 요소가 삭제될 수 있는 선형 목록입니다.
스택과 유사한 추상 데이터 구조입니다. 큐는 양쪽 끝에서 열려 있으며 데이터 항목을 저장하기 위해 FIFO(First-In-First-Out) 방법론을 따릅니다.

 

비선형 데이터 구조:

이 데이터 구조는 시퀀스를 형성하지 않습니다. 즉, 각 항목 또는 요소는 비선형 배열로 둘 이상의 다른 항목과 연결됩니다. 데이터 요소는 순차적 구조로 정렬되지 않습니다.
비선형 데이터 구조의 유형은 다음과 같습니다:

트리: 트리는 노드로 알려진 요소 간에 계층적 관계가 있는 다단계 데이터 구조입니다. 
계층 구조에서 가장 아래에 있는 노드를 리프 노드라고 하고 가장 위에 있는 노드를 루트 노드라고 합니다. 
각 노드에는 인접한 노드를 가리키는 포인터가 포함되어 있습니다.
트리 데이터 구조는 노드 간의 부모-자식 관계를 기반으로 합니다. 
트리의 각 노드는 리프 노드를 제외하고 둘 이상의 자식을 가질 수 있지만 각 노드는 루트 노드를 제외하고 최대 하나의 부모를 가질 수 있습니다. 
트리는 이 자습서의 뒷부분에서 설명할 여러 범주로 분류 될 수 있습니다.

그래프:

그래프는 edge로 알려진 링크로 연결된 요소 집합(정점으로 표시됨)을 그림으로 표현한 것으로 정의할 수 있습니다. 
그래프는 주기를 가질 수 있지만 트리는 주기(cycle)를 가질 수 없다는 점에서 그래프는 트리와 다릅니다.

데이터 구조의 조작

1) 탐색:

모든 데이터 구조에는 데이터 요소 집합이 포함됩니다. 
데이터 구조 탐색은 검색이나 정렬과 같은 특정 작업을 수행하기 위해 데이터 구조의 각 요소를 방문하는 것을 의미합니다.

예: 학생이 6개의 다른 과목에서 얻은 점수의 평균을 계산해야 하는 경우 전체 점수 배열을 탐색하고 총 합계를 계산한 다음 해당 합계를 과목 수, 즉 평균을 계산하기 위해 6으로 나눕니다.

2) 삽입:

삽입은 데이터 구조의 어느 위치에나 요소를 추가하는 과정으로 정의할 수 있습니다.

데이터 구조의 크기가 n이면 n-1개의 데이터 요소만 삽입할 수 있습니다.

3) 삭제:

데이터 구조에서 요소를 제거하는 과정을 삭제라고 합니다. 임의의 위치에서 데이터 구조의 요소를 삭제할 수 있습니다.

빈 데이터 구조에서 요소를 삭제하려고 하면 언더플로가 발생합니다.

4) 검색:

데이터 구조 내에서 요소의 위치를 ​​찾는 과정을 검색이라고 합니다. 
검색을 수행하는 알고리즘에는 선형 검색과 이진 검색의 두 가지가 있습니다. 
이 자습서의 뒷부분에서 각각에 대해 설명합니다.

5) 정렬:

데이터 구조를 특정 순서로 정렬하는 프로세스를 정렬이라고 합니다. 

삽입 정렬, 선택 정렬, 버블 정렬 등 정렬을 수행하는 데 사용할 수 있는 많은 알고리즘들이 존재 합니다.

6) 병합:

크기가 M과 N인 두 개의 리스트 A와 리스트 B가 유사한 유형의 요소를 포함하거나 결합되어 크기가 (M+N)인 세 번째 리스트인 리스트 C를 생성할 때 이 프로세스를 병합이라고 합니다.