Ưu điểm của danh sách liên kết so với danh sách đặc là gì?

Sự khác biệt chính giữa Array và danh sách Liên kết liên quan đến cấu trúc của chúng. Mảng là cấu trúc dữ liệu dựa trên chỉ mục trong đó mỗi phần tử được liên kết với một chỉ mục. Mặt khác, danh sách Liên kết phụ thuộc vào các tham chiếu trong đó mỗi nút bao gồm dữ liệu và các tham chiếu đến phần tử trước và phần tiếp theo.

Về cơ bản, một mảng là một tập hợp các đối tượng dữ liệu tương tự được lưu trữ trong các vị trí bộ nhớ tuần tự dưới một tiêu đề chung hoặc một tên biến.

Trong khi danh sách được liên kết là một cấu trúc dữ liệu chứa một chuỗi các phần tử trong đó mỗi phần tử được liên kết với phần tử tiếp theo của nó. Có hai trường trong một yếu tố của danh sách liên kết. Một là trường Dữ liệu và trường khác là trường liên kết, Trường dữ liệu chứa giá trị thực sẽ được lưu trữ và xử lý. Hơn nữa, trường liên kết giữ địa chỉ của mục dữ liệu tiếp theo trong danh sách được liên kết. Địa chỉ được sử dụng để truy cập vào một nút cụ thể được gọi là một con trỏ.

Một sự khác biệt đáng kể khác giữa một mảng và danh sách được liên kết là Array có kích thước cố định và được yêu cầu khai báo trước, nhưng Danh sách liên kết không bị giới hạn về kích thước và mở rộng và hợp đồng trong quá trình thực thi.

Biểu đồ so sánh

Định nghĩa của mảng

Một mảng được định nghĩa là một tập hợp một số lượng nhất định các phần tử đồng nhất hoặc các mục dữ liệu. Nó có nghĩa là một mảng chỉ có thể chứa một loại dữ liệu, tất cả các số nguyên, tất cả các số dấu phẩy động hoặc tất cả các ký tự. Khai báo một mảng như sau: int a [10];

Trong đó int chỉ định kiểu dữ liệu hoặc kiểu phần tử lưu trữ mảng. Số một tên là tên của một mảng và số được chỉ định trong dấu ngoặc vuông là số phần tử mà một mảng có thể lưu trữ, đây còn được gọi là kích thước hoặc độ dài của mảng.

Chúng ta hãy xem xét một số khái niệm cần nhớ về mảng:

• Các phần tử riêng lẻ của một mảng có thể được truy cập bằng cách mô tả tên của mảng, theo sau là chỉ mục hoặc chỉ mục (xác định vị trí của phần tử trong mảng) bên trong dấu ngoặc vuông. Ví dụ, để lấy phần tử thứ 5 của mảng, chúng ta cần viết một câu lệnh a [4].
• Trong mọi trường hợp, các phần tử của một mảng sẽ được lưu trữ trong một vị trí bộ nhớ liên tiếp.
• Phần tử đầu tiên của mảng có chỉ số zero [0]. Nó có nghĩa là phần tử đầu tiên và cuối cùng sẽ được chỉ định là [0] và [9] tương ứng.
• Số lượng phần tử có thể được lưu trữ trong một mảng, nghĩa là kích thước của một mảng hoặc chiều dài của nó được đưa ra theo phương trình sau: (giới hạn trên-giới hạn dưới) + 1

  Đối với mảng trên, nó sẽ là (9-0) + 1 = 10. Trong đó 0 là giới hạn dưới của mảng và 9 là giới hạn trên của mảng.

• Mảng có thể được đọc hoặc viết thông qua các vòng lặp. Nếu chúng ta đọc mảng một chiều, nó yêu cầu một vòng lặp để đọc và một vòng khác để viết (in) mảng, ví dụ: a. Để đọc một mảng cho (i = 0; i <= 9; i ++) {scanf (M %% dv, & a [i]); } b. Để viết một mảng cho (i = 0; i <= 9; i ++)

  {printf (phiên bản% dv, a [i]); }

• Trong trường hợp mảng 2 chiều, nó sẽ yêu cầu hai vòng và mảng n chiều tương tự sẽ cần n vòng.

Các hoạt động được thực hiện trên mảng là:

1. Tạo mảng
2. Đi qua một mảng
3. Chèn các yếu tố mới
4. Xóa các yếu tố cần thiết.
5. Sửa đổi một yếu tố.
6. Sáp nhập mảng

Thí dụ

Chương trình sau đây minh họa việc đọc và viết của mảng.

#include
#include
void main ()
{
int a[10], i;
printf("Enter the array");
for ( i= 0; i <= 9; i++)
{
scanf ( "%d", &a[ i ] ) ;
}
printf( "Enter the array" );
for (i = 0 ; i <= 9 ; i++)
{
printf ( "%d\n", a[ i ] ) ;
}
getch ();
}

Định nghĩa của danh sách liên kết

Danh sách liên kết là một danh sách cụ thể của một số yếu tố dữ liệu được liên kết với nhau. Trong phần này, mọi phần tử đều trỏ đến phần tử tiếp theo thể hiện thứ tự logic. Mỗi phần tử được gọi là một nút, có hai phần.

Phần INFO lưu trữ thông tin và ĐIỂM chỉ đến phần tử tiếp theo. Như bạn đã biết để lưu trữ địa chỉ, chúng tôi có một cấu trúc dữ liệu duy nhất trong C được gọi là con trỏ. Do đó trường thứ hai của danh sách phải là một loại con trỏ.

Các loại danh sách được liên kết là danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết tròn, danh sách liên kết đôi.

Các hoạt động được thực hiện trên Danh sách liên kết là:

1. Sự sáng tạo
2. Đi qua
3. Chèn
4. Xóa
5. Đang tìm kiếm
6. Ghép
7. Trưng bày

Thí dụ

Đoạn mã sau minh họa việc tạo danh sách được liên kết:

struct node
{
int num;
stuct node *next;
}
start = NULL;
void create()
{
typedef struct node NODE;
NODE *p, *q;
char choice;
first = NULL;
do
{
p = (NODE *) malloc (sizeof (NODE));
printf ("Enter the data item\n");
scanf ("%d", & p -> num);
if (p == NULL)
{
q = start;
while (q -> next ! = NULL)
{ q = q -> next
}
p -> next = q -> next;
q -> = p;
}
else
{
p -> next = start;
start = p;
}
printf ("Do you want to continue (type y or n) ? \n");
scanf ("%c", &choice) ;
}
while ((choice == 'y') || (choice == 'Y'));
}

1. Một mảng là cấu trúc dữ liệu chứa một tập hợp các phần tử dữ liệu loại tương tự trong khi danh sách Liên kết được coi là cấu trúc dữ liệu không nguyên thủy chứa một tập hợp các phần tử được liên kết không có thứ tự được gọi là các nút.
2. Trong mảng, các phần tử thuộc về chỉ mục, nghĩa là, nếu bạn muốn vào phần tử thứ tư, bạn phải viết tên biến với chỉ mục hoặc vị trí của nó trong dấu ngoặc vuông.
   Tuy nhiên, trong một danh sách được liên kết, bạn phải bắt đầu từ đầu và thực hiện theo cách của mình cho đến khi bạn đến phần tử thứ tư.
3. Mặc dù việc truy cập vào một mảng phần tử là nhanh trong khi danh sách Liên kết mất thời gian tuyến tính, do đó, nó chậm hơn một chút.
4. Các hoạt động như chèn và xóa trong mảng tiêu tốn rất nhiều thời gian. Mặt khác, hiệu suất của các hoạt động này trong danh sách Liên kết là nhanh.
5. Mảng có kích thước cố định. Ngược lại, danh sách Liên kết là động và linh hoạt và có thể mở rộng và hợp đồng kích thước của nó.
6. Trong một mảng, bộ nhớ được gán trong thời gian biên dịch trong khi trong danh sách Liên kết, nó được cấp phát trong khi thực thi hoặc thời gian chạy.
7. Các phần tử được lưu trữ liên tiếp trong các mảng trong khi nó được lưu trữ ngẫu nhiên trong danh sách Liên kết.
8. Yêu cầu của bộ nhớ ít hơn do dữ liệu thực tế được lưu trữ trong chỉ mục trong mảng. Ngoài ra, cần có thêm bộ nhớ trong Danh sách được liên kết do lưu trữ các yếu tố tham chiếu tiếp theo và trước đó.
9. Ngoài ra việc sử dụng bộ nhớ là không hiệu quả trong mảng. Ngược lại, sử dụng bộ nhớ là hiệu quả trong mảng.

Danh sách mảng và liên kết là các loại cấu trúc dữ liệu khác nhau về cấu trúc, phương thức truy cập và thao tác, yêu cầu bộ nhớ và sử dụng. Và có lợi thế và bất lợi đặc biệt so với việc thực hiện nó. Do đó, một trong hai có thể được sử dụng theo nhu cầu.