Danh sách được liên kết sử dụng phân bổ bộ nhớ động và là tập hợp các nút.
Các nút có hai phần là dữ liệu và liên kết.
Các loại danh sách được liên kết
Các loại danh sách liên kết trong ngôn ngữ lập trình C như sau -
- Danh sách được liên kết đơn / lẻ
- Danh sách được liên kết đôi / liên kết đôi
- Danh sách liên kết đơn hình tròn
- Danh sách liên kết kép hình tròn
Danh sách liên kết đơn
Sơ đồ dưới đây mô tả sự thể hiện của danh sách liên kết đơn.
Ví dụ
Sau đây là chương trình C để hiển thị các số theo thứ tự ngược lại bằng cách sử dụng danh sách liên kết duy nhất -
#include <stdio.h> #include <stdlib.h> struct node { int num; struct node *nextptr; }*stnode; void createNodeList(int n); void reverseDispList(); void displayList(); int main(){ int n; printf("\n\n single Linked List : print it in reverse order :\n"); printf("------------------------------------------------------------------------------\n"); printf(" Input the number of nodes : "); scanf("%d", &n); createNodeList(n); printf("\n Data entered in the list are : \n"); displayList(); reverseDispList(); printf("\n The list in reverse are : \n"); displayList(); return 0; } void createNodeList(int n){ struct node *fnNode, *tmp; int num, i; stnode = (struct node *)malloc(sizeof(struct node)); if(stnode == NULL) { printf(" Memory can not be allocated."); } else{ // reads data for the node through keyboard printf(" Input data for node 1 : "); scanf("%d", &num); stnode-> num = num; stnode-> nextptr = NULL; tmp = stnode; //Creates n nodes and adds to linked list for(i=2; i<=n; i++){ fnNode = (struct node *)malloc(sizeof(struct node)); if(fnNode == NULL) { printf(" Memory can not be allocated."); break; } else{ printf(" Input data for node %d : ", i); scanf(" %d", &num); fnNode->num = num; fnNode->nextptr = NULL; tmp->nextptr = fnNode; tmp = tmp->nextptr; } } } } void reverseDispList(){ struct node *prevNode, *curNode; if(stnode != NULL){ prevNode = stnode; curNode = stnode->nextptr; stnode = stnode->nextptr; prevNode->nextptr = NULL; //convert the first node as last while(stnode != NULL){ stnode = stnode->nextptr; curNode->nextptr = prevNode; prevNode = curNode; curNode = stnode; } stnode = prevNode; //convert the last node as head } } void displayList(){ struct node *tmp; if(stnode == NULL){ printf(" No data found in the list."); } else{ tmp = stnode; while(tmp != NULL){ printf(" Data = %d\n", tmp->num); tmp = tmp->nextptr; } } }
Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
Single Linked List : print it in reverse order : ------------------------------------------------------------------------------ Input the number of nodes : 5 Input data for node 1 : 12 Input data for node 2 : 45 Input data for node 3 : 11 Input data for node 4 : 9 Input data for node 5 : 10 Data entered in the list are : Data = 12 Data = 45 Data = 11 Data = 9 Data = 10 The list in reverse are : Data = 10 Data = 9 Data = 11 Data = 45 Data = 12