Giới thiệu

Sự khác biệt chính giữa Array và Linked List liên quan đến cấu trúc của chúng. Array có cấu trúc dữ liệu dựa trên chỉ mục (index based), trong đó mỗi phần tử chỉ được ứng với một chỉ mục. Còn, Linked list phụ thuộc vào các tham chiếu (references) 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 Array 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 Linked list 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 Linked list, là trường dữ liệu (data field) và trường liên kết (link field). Trường dữ liệu chứa giá trị thực sẽ được lưu trữ và xử lý. 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 Array và Linked list là Array có kích thước cố định và được yêu cầu khai báo trước, còn Linked list không bị giới hạn về kích thước và có khả năng mở rộng trong quá trình thực thi.

Bảng so sánh Array và Linked List

Định nghĩa của Array

Một Array đượ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 ví dụ 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];

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ố 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 độ dài của nó được đưa ra theo phương trình sau: (upper bound-lower bound) + 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ụ: Để đọc một mảng với vòng lặp for

for ( i= 0; i <= 9; i++) { scanf ( “%d”, &a[ i ] ) ; }

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

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

Chương trình sau đây sẽ minh họa việc đọc và ghi của 1 mảng :

#include<stdio.h>
#include<conio.h>
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 Linked List

Linked List 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à POINTER trỏ đến phần tử tiếp theo và phần thứ 2 là một loại con trỏ.

Các loại danh sách được liên kết là Singly-linked list, Doubly linked list, Circular linked list, Circular double linked list.

Các bước hoạt động được thực hiện trên Linked List

1. Creation
2. Duyệt qua
3. Chèn
4. Xóa
5. Tìm kiếm
6. Liên kết
7. Hiển thị

Đoạn mã sau minh họa việc tạo Linked List:

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'));
 }

Kết luận

Array và Linked lists 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. Cả 2 có lợi thế và bất lợi đặc biệt so với việc thực hiện trong các trường hợp khác nhau. Do đó các bạn nên cân nhắc trước khi sử dụng giữa Array và Linked lists. Trên đây là nhưng điểm khác nhau giữa Array và Linked lists mà mình tìm hiểu được.

Cảm ơn các bạn đã đọc bài!

Tài liệu tham khảo:

https://www.learn-c.org/en/Linked_lists

https://www.tutorialspoint.com/cprogramming/c_arrays.htm

https://techdifferences.com/difference-between-array-and-linked-list.html