Danh sách liên kết DSA trong bộ nhớ
Bộ nhớ máy tính
Để giải thích danh sách liên kết là gì và danh sách liên kết khác với mảng như thế nào, chúng ta cần hiểu một số điều cơ bản về cách hoạt động của bộ nhớ máy tính.
Bộ nhớ máy tính là bộ nhớ mà chương trình của bạn sử dụng khi chạy. Đây là nơi lưu trữ các biến, mảng và danh sách liên kết của bạn.
Các biến trong bộ nhớ
Hãy tưởng tượng rằng chúng ta muốn lưu trữ số nguyên "17" trong một biến myNumber . Để đơn giản, giả sử số nguyên được lưu dưới dạng hai byte (16 bit) và địa chỉ trong bộ nhớ của myNumber là 0x7F30 .
0x7F30 thực sự là địa chỉ đầu tiên trong số hai byte bộ nhớ nơi lưu trữ giá trị số nguyên myNumber . Khi máy tính chuyển sang 0x7F30 để đọc một giá trị số nguyên, nó biết rằng nó phải đọc cả byte đầu tiên và byte thứ hai, vì số nguyên là hai byte trên máy tính cụ thể này.
Hình ảnh bên dưới cho thấy biến myNumber = 17 được lưu trữ trong bộ nhớ như thế nào.
Ví dụ trên cho thấy cách lưu trữ một giá trị số nguyên trên bộ vi điều khiển Arduino Uno đơn giản nhưng phổ biến. Bộ vi điều khiển này có kiến trúc 8 bit với bus địa chỉ 16 bit và sử dụng hai byte cho số nguyên và hai byte cho địa chỉ bộ nhớ. Để so sánh, máy tính cá nhân và điện thoại thông minh sử dụng 32 hoặc 64 bit cho số nguyên và địa chỉ, nhưng về cơ bản bộ nhớ hoạt động theo cùng một cách.
Mảng trong bộ nhớ
Để hiểu danh sách liên kết, trước hết cần biết mảng được lưu trữ trong bộ nhớ như thế nào.
Các phần tử trong mảng được lưu trữ liên tục trong bộ nhớ. Điều đó có nghĩa là mỗi phần tử được lưu trữ ngay sau phần tử trước đó.
Hình ảnh bên dưới cho thấy cách lưu trữ một mảng số nguyên myArray = [3,5,13,2] trong bộ nhớ. Ở đây chúng tôi sử dụng một loại bộ nhớ đơn giản với hai byte cho mỗi số nguyên, giống như trong ví dụ trước, chỉ để hiểu ý tưởng.
Máy tính chỉ có địa chỉ của byte đầu tiên của myArray , vì vậy để truy cập phần tử thứ 3 bằng mã myArray[2] máy tính bắt đầu ở 0x7F28 và nhảy qua hai số nguyên đầu tiên. Máy tính biết rằng một số nguyên được lưu trữ trong hai byte, do đó, nó nhảy 2x2 byte về phía trước từ 0x7F28 và đọc giá trị 13 bắt đầu từ địa chỉ 0x7F32 .
Khi xóa hoặc chèn các phần tử vào một mảng, mọi phần tử theo sau phải được dịch chuyển lên để nhường chỗ cho phần tử mới hoặc dịch chuyển xuống để thế chỗ cho phần tử đã bị xóa. Các hoạt động dịch chuyển như vậy tốn nhiều thời gian và có thể gây ra sự cố trong các hệ thống thời gian thực.
Hình ảnh bên dưới cho thấy các phần tử được dịch chuyển như thế nào khi một phần tử mảng bị xóa.
Thao tác với mảng cũng là điều bạn phải nghĩ tới nếu đang lập trình bằng C, nơi bạn phải di chuyển rõ ràng các phần tử khác khi chèn hoặc xóa một phần tử. Trong C điều này không xảy ra ở chế độ nền.
Trong C, bạn cũng cần đảm bảo rằng bạn đã phân bổ đủ không gian cho mảng bắt đầu để bạn có thể thêm nhiều phần tử hơn sau này.
Bạn có thể đọc thêm về mảng trên trang hướng dẫn DSA trước đây .
Danh sách liên kết trong bộ nhớ
Thay vì lưu trữ tập hợp dữ liệu dưới dạng mảng, chúng ta có thể tạo danh sách liên kết.
Danh sách liên kết được sử dụng trong nhiều trường hợp, như lưu trữ dữ liệu động, triển khai ngăn xếp và hàng đợi hoặc biểu diễn biểu đồ, để đề cập đến một số trường hợp trong số đó.
Danh sách liên kết bao gồm các nút có một số loại dữ liệu và ít nhất một con trỏ hoặc liên kết tới các nút khác.
Lợi ích lớn của việc sử dụng danh sách liên kết là các nút được lưu trữ ở bất kỳ nơi nào có dung lượng trống trong bộ nhớ, các nút không cần phải được lưu trữ liền kề nhau giống như các phần tử được lưu trữ trong mảng. Một điều thú vị khác với danh sách liên kết là khi thêm hoặc xóa các nút, các nút còn lại trong danh sách không cần phải dịch chuyển.
Hình ảnh bên dưới cho thấy cách lưu trữ danh sách liên kết trong bộ nhớ. Danh sách liên kết có bốn nút có giá trị 3, 5, 13 và 2 và mỗi nút có một con trỏ tới nút tiếp theo trong danh sách.
Mỗi nút chiếm bốn byte. Hai byte được sử dụng để lưu trữ một giá trị nguyên và hai byte được sử dụng để lưu địa chỉ cho nút tiếp theo trong danh sách. Như đã đề cập trước đó, cần bao nhiêu byte để lưu trữ số nguyên và địa chỉ tùy thuộc vào kiến trúc của máy tính. Ví dụ này, giống như ví dụ về mảng trước, phù hợp với kiến trúc vi điều khiển 8 bit đơn giản.
Để dễ dàng xem các nút liên quan với nhau như thế nào, chúng ta sẽ hiển thị các nút trong danh sách liên kết một cách đơn giản hơn, ít liên quan đến vị trí bộ nhớ của chúng, như trong hình bên dưới:
Nếu chúng ta đặt bốn nút giống nhau từ ví dụ trước lại với nhau bằng cách sử dụng hình ảnh trực quan mới này, nó sẽ trông như thế này:
Như bạn có thể thấy, nút đầu tiên trong danh sách liên kết được gọi là "Đầu" và nút cuối cùng được gọi là "Đuôi".
Không giống như mảng, các nút trong danh sách liên kết không được đặt ngay sau nhau trong bộ nhớ. Điều này có nghĩa là khi chèn hoặc xóa một nút, việc dịch chuyển các nút khác là không cần thiết, vì vậy đó là một điều tốt.
Một điều không tốt với danh sách liên kết là chúng ta không thể truy cập trực tiếp vào một nút như với một mảng chỉ bằng cách viết myArray[5] chẳng hạn. Để đến nút số 5 trong danh sách liên kết, chúng ta phải bắt đầu với nút đầu tiên được gọi là "head", sử dụng con trỏ của nút đó để đến nút tiếp theo và làm như vậy trong khi theo dõi số lượng nút chúng ta đã truy cập cho đến khi chúng ta đạt đến nút số 5.
Tìm hiểu về danh sách liên kết giúp chúng ta hiểu rõ hơn các khái niệm như cấp phát bộ nhớ và con trỏ.
Danh sách liên kết cũng rất quan trọng để hiểu trước khi tìm hiểu về các cấu trúc dữ liệu phức tạp hơn như cây và đồ thị, có thể được triển khai bằng danh sách liên kết.
Bộ nhớ trong máy tính hiện đại
Cho đến nay trên trang này, chúng tôi đã sử dụng bộ nhớ trong bộ vi điều khiển 8 bit làm ví dụ để giữ cho nó đơn giản và dễ hiểu hơn.
Bộ nhớ trong máy tính hiện đại hoạt động về nguyên tắc giống như bộ nhớ trong bộ vi điều khiển 8 bit, nhưng nhiều bộ nhớ hơn được sử dụng để lưu trữ số nguyên và nhiều bộ nhớ hơn được sử dụng để lưu trữ địa chỉ bộ nhớ.
Mã bên dưới cung cấp cho chúng tôi kích thước của một số nguyên và kích thước của địa chỉ bộ nhớ trên máy chủ mà chúng tôi đang chạy các ví dụ này.
Ví dụ
Mã viết bằng C:
#include <stdio.h>
int main() {
int myVal = 13;
printf("Value of integer 'myVal': %d\n", myVal);
printf("Size of integer 'myVal': %lu bytes\n", sizeof(myVal)); // 4 bytes
printf("Address to 'myVal': %p\n", &myVal);
printf("Size of the address to 'myVal': %lu bytes\n", sizeof(&myVal)); // 8 bytes
return 0;
} Chạy ví dụ »Ví dụ mã ở trên chỉ chạy trong C vì Java và Python chạy ở mức trừu tượng trên mức phân bổ bộ nhớ cụ thể/trực tiếp.
Triển khai danh sách liên kết trong C
Hãy triển khai danh sách liên kết này từ trước đó:
Hãy triển khai danh sách liên kết này trong C để xem ví dụ cụ thể về cách danh sách liên kết được lưu trữ trong bộ nhớ.
Trong mã bên dưới, sau khi bao gồm các thư viện, chúng tôi tạo một cấu trúc nút giống như một lớp đại diện cho nút là gì: nút chứa dữ liệu và một con trỏ tới nút tiếp theo.
Hàm createNode() phân bổ bộ nhớ cho một nút mới, điền vào phần dữ liệu của nút bằng một số nguyên được cung cấp làm đối số cho hàm và trả về con trỏ (địa chỉ bộ nhớ) cho nút mới.
Hàm printList() chỉ dùng để xem qua danh sách được liên kết và in giá trị của từng nút.
Bên trong hàm main() , bốn nút được tạo, liên kết với nhau, in và sau đó bộ nhớ được giải phóng. Cách tốt nhất là giải phóng bộ nhớ sau khi sử dụng xong để tránh rò rỉ bộ nhớ. Rò rỉ bộ nhớ là khi bộ nhớ không được giải phóng sau khi sử dụng, dần dần chiếm ngày càng nhiều bộ nhớ.
Ví dụ
Danh sách liên kết cơ bản trong C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void printList(Node* node) {
while (node) {
printf("%d -> ", node->data);
node = node->next;
}
printf("null\n");
}
int main() {
Node* node1 = createNode(3);
Node* node2 = createNode(5);
Node* node3 = createNode(13);
Node* node4 = createNode(2);
node1->next = node2;
node2->next = node3;
node3->next = node4;
printList(node1);
// Free the memory
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
} Chạy ví dụ » Để in danh sách liên kết trong đoạn mã trên, hàm printList() đi từ nút này sang nút tiếp theo bằng cách sử dụng con trỏ "tiếp theo" và chức năng này được gọi là "traversing" hoặc "traversal" của danh sách liên kết. Bạn sẽ tìm hiểu thêm về duyệt danh sách liên kết và các thao tác danh sách liên kết khác trên trang Hoạt động của danh sách liên kết .
Triển khai danh sách liên kết bằng Python và Java
Bây giờ chúng ta sẽ triển khai danh sách liên kết tương tự này bằng cách sử dụng Python và Java.
Trong mã Python bên dưới, lớp Node thể hiện nút là gì: nút chứa dữ liệu và liên kết đến nút tiếp theo.
Lớp Node được sử dụng để tạo bốn nút, sau đó các nút được liên kết với nhau và in ở cuối.
Như bạn có thể thấy, mã Python ngắn hơn rất nhiều so với mã C và có lẽ tốt hơn nếu bạn chỉ muốn hiểu khái niệm về danh sách liên kết chứ không phải cách danh sách liên kết được lưu trữ trong bộ nhớ.
Mã Java rất giống với mã Python. Nhấp vào nút "Chạy ví dụ" bên dưới và chọn tab "Java" để xem mã Java.
Ví dụ
Danh sách liên kết cơ bản trong Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null") Chạy ví dụ »