TechCodeview

정렬 그리고 연결리스트 메모리에서 데이터를 구성하는 두 가지 방법이 있습니다. 차이점을 이해하기 전에 정렬 그리고 연결리스트 , 먼저 살펴보겠습니다 배열에서 그리고 연결 리스트 .

쉐타 티와리

배열이란 무엇입니까?

동일한 유형의 요소를 포함하는 데이터 구조입니다. 데이터 구조는 데이터를 구성하는 방법입니다. 배열은 데이터를 순차적으로 구성하므로 데이터 구조입니다. 배열은 메모리가 작은 블록으로 나누어져 있고 각 블록은 특정 값을 저장할 수 있는 큰 메모리 덩어리입니다.

10개의 값으로 구성된 배열을 생성했다고 가정하면 각 블록은 정수 유형의 값을 저장합니다. 다른 유형의 배열에 값을 저장하려고 하면 올바른 배열이 아니며 컴파일 시간 오류가 발생합니다.

배열 선언

배열은 다음과 같이 선언할 수 있습니다.

 data_type name of the array[no of elements] 

배열을 선언하려면 먼저 배열 유형을 지정한 다음 배열 이름을 지정해야 합니다. 대괄호 안에 배열에 포함되어야 하는 요소 수를 지정해야 합니다.

예를 통해 이해해 봅시다.

 int a[5]; 

위의 경우 '로 5개 요소의 배열을 선언했습니다. ㅏ '의 이름 정수 데이터 형식.

연결리스트란 무엇인가요?

연결된 목록은 무작위로 저장된 노드의 모음입니다. 각 노드는 두 개의 필드로 구성됩니다. 데이터 그리고 링크 . 여기서 데이터는 특정 노드에 저장된 값이고 링크는 다음 노드의 주소를 보유하는 포인터입니다.

배열과 연결리스트의 차이점

우리는 어떤 데이터 구조가 더 나은지 말할 수 없습니다. 즉, 배열 또는 연결리스트 . 한 종류의 요구 사항에 대해 하나의 데이터 구조가 더 나은 반면, 다른 종류의 요구 사항에는 다른 데이터 구조가 더 나을 가능성이 있을 수 있습니다. 데이터 구조나 데이터 크기에 대해 자주 수행되는 작업이 무엇인지, 데이터 구조가 선택되는 기타 요소와 같은 다양한 요소가 있습니다. 이제 일부 매개 변수를 기반으로 배열과 연결 목록 간의 몇 가지 차이점을 살펴보겠습니다.

1. 요소에 액세스하는 비용

배열의 경우 배열의 크기에 관계없이 배열이 요소에 액세스하는 데 일정한 시간이 걸립니다. 배열에서는 요소가 연속적으로 저장되므로 요소의 기본 주소를 알면 배열에 있는 모든 요소의 주소를 쉽게 얻을 수 있습니다. 배열에 있는 요소의 주소를 얻으려면 간단한 계산을 수행해야 합니다. 따라서 배열의 요소에 액세스하는 것은 오(1) 시간복잡도 측면에서요.

연결된 목록에서는 요소가 연속적으로 저장되지 않습니다. 여러 개의 블록으로 구성되며, 각 블록은 노드로 표현됩니다. 각 노드에는 두 개의 필드가 있습니다. 즉, 하나는 데이터 필드용이고 다른 하나는 다음 노드의 주소를 저장합니다. 연결된 목록에서 노드를 찾으려면 먼저 헤드 노드로 알려진 첫 번째 노드를 결정해야 합니다. 목록에서 두 번째 노드를 찾아야 한다면 첫 번째 노드부터 순회해야 하며, 최악의 경우 마지막 노드를 찾으려면 모든 노드를 순회하게 됩니다. 요소에 액세스하는 평균 사례는 O(n)입니다.

우리는 배열의 요소에 액세스하는 비용이 연결 목록보다 적다는 결론을 내렸습니다. 따라서 요소에 액세스하기 위한 요구 사항이 있는 경우 배열이 더 나은 선택입니다.

jquery 클릭

2. 요소 삽입 비용

삽입에는 세 가지 시나리오가 있을 수 있습니다.

처음에 요소 삽입:처음에 새 요소를 삽입하려면 먼저 요소를 오른쪽으로 이동하여 첫 번째 위치에 공백을 만들어야 합니다. 따라서 시간 복잡도는 목록의 크기에 비례합니다. n이 배열의 크기라면 시간 복잡도는 O(n)이 됩니다.

연결리스트의 경우 연결리스트의 시작 부분에 요소를 삽입하기 위해 새 노드를 생성하고 첫 번째 노드의 주소가 새 노드에 추가됩니다. 이런 방식으로 새 노드가 첫 번째 노드가 됩니다. 따라서 시간복잡도는 목록의 크기에 비례하지 않습니다. 시간 복잡도는 일정합니다(예: O(1)).

끝에 요소 삽입

배열이 가득 차지 않으면 인덱스를 통해 새 요소를 직접 추가할 수 있습니다. 이 경우 시간 복잡도는 O(1)로 일정합니다. 배열이 꽉 차면 먼저 배열을 다른 배열에 복사하고 새 요소를 추가해야 합니다. 이 경우 시간 복잡도는 O(n)이 됩니다.

연결된 목록의 끝에 요소를 삽입하려면 전체 목록을 순회해야 합니다. 연결된 목록이 n개의 요소로 구성되면 시간 복잡도는 O(n)이 됩니다.

중간에 요소 삽입

i에 요소를 삽입하고 싶다고 가정합니다.^일배열의 위치; n/2개의 요소를 오른쪽으로 이동해야 합니다. 따라서 시간 복잡도는 요소 수에 비례합니다. 평균적인 경우 시간 복잡도는 O(n)입니다.

c에서 무작위

연결리스트의 경우 새 요소를 삽입해야 하는 위치로 이동해야 합니다. 하지만 어떤 종류의 이동도 수행할 필요는 없지만 n/2 위치로 이동해야 합니다. 걸리는 시간은 n개의 요소 수에 비례하며 평균 사례의 시간 복잡도는 O(n)입니다.

결과 연결 목록은 다음과 같습니다.

사용의 용이성

배열의 구현은 연결리스트에 비해 쉽습니다. 연결된 목록을 사용하여 프로그램을 만드는 동안 프로그램은 분할 오류나 메모리 누수와 같은 오류가 발생하기 쉽습니다. 따라서 연결리스트에 프로그램을 생성할 때에는 많은 주의가 필요하다.

동적 크기

연결된 목록은 크기가 동적이지만 배열은 정적입니다. 여기서 static은 런타임에 크기를 결정할 수 없다는 의미가 아니라 크기가 결정되면 변경할 수 없다는 의미입니다.

3. 메모리 요구 사항

배열의 요소가 하나의 연속된 메모리 블록에 저장되므로 배열의 크기는 고정되어 있습니다. 크기가 7인 배열이 있고 배열이 4개의 요소로 구성되어 있으며 나머지 공간은 사용되지 않는다고 가정합니다. 7개 요소가 차지하는 메모리:

메모리 공간 = 7*4 = 28바이트

여기서 7은 배열의 요소 수이고 4는 정수 유형의 바이트 수입니다.

연결리스트의 경우 사용되지 않는 메모리는 없지만 포인터 변수가 추가 메모리를 차지합니다. 데이터가 정수형인 경우 한 노드가 차지하는 총 메모리는 8바이트입니다. 즉, 데이터는 4바이트, 포인터 변수는 4바이트입니다. 연결된 목록이 4개의 요소로 구성된 경우 연결된 목록이 차지하는 메모리 공간은 다음과 같습니다.

웹드라이버

메모리 공간 = 8*4 = 32바이트

데이터 부분의 크기가 더 크다면 연결된 목록이 더 나은 선택이 될 것입니다. 데이터가 16바이트라고 가정합니다. 배열이 차지하는 메모리 공간은 16*7=112바이트이고 연결 목록은 20*4=80을 차지합니다. 여기서는 데이터 크기에 대해 16바이트에 포인터 변수에 대해 4바이트를 더해 20바이트를 지정했습니다. 더 큰 크기의 데이터를 선택하면 연결된 목록이 더 적은 메모리를 소비합니다. 그렇지 않으면 크기를 결정하기 위해 채택하는 요소에 따라 달라집니다.

배열과 연결리스트의 차이점을 표 형식으로 살펴보겠습니다.