Danh sách liên kết (Linked List) là gì ?

Một Danh sách liên kết (Linked List) là 1 dãy các cấu trúc dữ liệu được liên kết với nhau thông qua các links (link). Gọi một cách đơn giản thì Danh sách link là một cấu tạo dữ liệu bao gồm 1 nhóm những nút (node) chế tác thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó với tham chiếu đến nút tiếp nối trong chuỗi.

Bạn đang xem: Hiển thị danh sách liên kết theo chiều đảo ngược trong c

Danh sách liên kết là kết cấu dữ liệu được sử dụng thông dụng thứ nhì sau mảng. Dưới đây là các quan niệm cơ bạn dạng liên quan tới danh sách liên kết:

Link (liên kết): mỗi links của một danh sách liên kết hoàn toàn có thể lưu giữ một tài liệu được gọi là 1 phần tử.Next: Mỗi link của một Danh sách liên kết chứa một liên kết tới next link được gọi là Next.First: một danh sách liên kết bao hàm các link kết nối cho tới first links được điện thoại tư vấn là First.

Biểu diễn Danh sách liên kết (Linked List)

Danh sách liên kết rất có thể được biểu diễn như là một trong những chuỗi những nút (node). Từng nút đã trỏ tới nút kế tiếp.

*

Dưới đấy là một số vấn đề cần nhớ về list liên kết:

Danh sách links chứa một trong những phần tử liên kết thì được hotline là First.Mỗi link mang trong mình một trường tài liệu và một trường liên kết được hotline là Next.Mỗi liên kết được link với link kế tiếp bởi sử dụng link tiếp nối của nó.Link sau cuối mang một link là null để lưu lại điểm cuối của danh sách.

Các loại Danh sách link (Linked List)

Dưới đây là các một số loại Danh sách liên kết (Linked List) đa dạng:

Danh sách links đơn (Simple Linked List): chỉ trông nom các phần tử theo chiều về trước.Danh sách link đôi (Doubly Linked List): các phần tử có thể được chăm nom theo chiều về trước hoặc về sau.Danh sách link vòng (Circular Linked List): thành phần cuối thuộc chứa liên kết của bộ phận đầu tiên như thể next và bộ phận đầu tiên có links tới phần tử cuối cùng như thể prev.

Các hoạt động cơ phiên bản trên list liên kết

Dưới đây là một số hoạt động cơ bản có thể được triển khai bởi một danh sách liên kết:

Hoạt động chèn: thêm một trong những phần tử vào đầu danh sách liên kết.Hoạt rượu cồn xóa (phần tử đầu): xóa một trong những phần tử tại đầu danh sách liên kết.Hiển thị: hiển thị cục bộ danh sách.Hoạt rượu cồn tìm kiếm: tìm kiếm thành phần bởi áp dụng khóa (key) sẽ cung cấp.Hoạt đụng xóa (bởi thực hiện khóa): xóa một trong những phần tử bởi sử dụng khóa (key) đang cung cấp.

Hoạt động chèn trong list liên kết

Việc thêm một nút new vào trong danh sách liên kết không chỉ có là một chuyển động thêm dễ dàng và đơn giản như trong các cấu tạo dữ liệu khác (bởi vì bọn họ có tài liệu và tất cả link). Họ sẽ mày mò thông qua sơ đồ gia dụng dưới đây. Đầu tiên, tạo nên một nút bởi sử dụng cùng kết cấu và tìm vị trí nhằm chèn nút này.

*

Giả sử chúng ta cần chèn một nút B vào giữa nút A (nút trái) và C (nút phải). Do đó: B.next trỏ tới C.

NewNode.next −> RightNode;Hình minh họa như sau:

*

Bây giờ, next của nút phía bên trái sẽ trở cho tới nút mới.

LeftNode.next −> NewNode;

*

Quá trình trên sẽ đặt nút bắt đầu vào thân hai nút. Lúc đó danh sách mới sẽ trông như sau:

*

Các bước tương tự sẽ được tiến hành nếu chèn nút vào đầu danh sách liên kết. Trong khi đặt một nút vào địa điểm cuối của danh sách, thìnút sản phẩm hai tính trường đoản cú nút sau cuối của list sẽ trỏ tới nút new và nút mới sẽ trỏ cho tới NULL.

Hoạt cồn xóa trong danh sách liên kết

Hoạt đụng xóa vào Danh sách link cũng phức hợp hơn trong cấu tạo dữ liệu khác. Đầu tiên họ cần định vị nút phải xóa vị sử dụng các giải thuật search kiếm.

*

Bây giờ, nút phía trái (prev) của nút buộc phải xóa đề xuất trỏ cho tới nút tiếp nối (next) của nút nên xóa.

LeftNode.next −> TargetNode.next;

*

Quá trình này đang xóa link trỏ tới nút bắt buộc xóa. Bây giờ chúng ta sẽ xóa hồ hết gì mà nút cần xóa sẽ trỏ tới.

TargetNode.next −> NULL;

*

Nếu bạn cần sử dụng nút đã bị xóa này thì chúng ta cũng có thể giữ chúng trong bộ nhớ, ví như không bạn có thể xóa trọn vẹn hẳn nó khỏi bộ nhớ.

*

Hoạt động hòn đảo ngược danh sách liên kết

Với chuyển động này, bạn phải cẩn thận. Bọn họ cần làm cho nút đầu (head) trỏ tới nút ở đầu cuối và đảo ngược toàn bộ danh sách liên kết.

*

Đầu tiên, họ duyệt tới phần cuối của danh sách. Nút này đang trỏ cho tới NULL. Bây giờ điều phải làm là tạo nên nút cuối này trỏ cho tới nút phía trước của nó.

*

Chúng ta phải đảm bảo an toàn rằng nút sau cuối này sẽ không trở nên thất lạc, do đó họ sẽ sử dụng một số trong những nút nhất thời (temp node – giống như các trở thành tạm trung gian để giữ gìn giá trị). Tiếp theo, bọn họ sẽ tạo nên từng nút phía bên trái sẽ trỏ tới nút trái của chúng.

*

Sau đó, nút trước tiên sau nút head sẽ trỏ cho tới NULL.

*

Chúng ta sẽ làm cho nút head trỏ cho tới nút đầu tiên mới vày sử dụng các nút tạm.

*

Bây giờ danh sách liên kết đã bị đảo ngược.

Xem thêm: Bài Tập C Và C++ Có Lời Giải, Tuyển Tập 140 Bài Tập C Có Giải

Danh sách link (Linked List) trong C

Một Danh sách links (Linked List) là 1 dãy các kết cấu dữ liệu được liên kết với nhau trải qua các links (link). Hiểu một cách đơn giản và dễ dàng thì Danh sách links là một kết cấu dữ liệu gồm 1 nhóm các nút (node) tạo ra thành một chuỗi. Từng nút gồm tài liệu ở nút đó với tham chiếu đến nút tiếp nối trong chuỗi.

Chương trình minh họa Danh sách liên kết (Linked List) trong C

#include #include #include #include struct node int data; int key; struct node *next;;struct node *head = NULL;struct node *current = NULL;//hien thi danh sachvoid printList() struct node *ptr = head; printf(" < "); //bat dau tu phan dau danh sach while(ptr != NULL) printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; printf(" >");//chen link tai vi tri dau tienvoid insertFirst(int key, int data) //tao mot links struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //tro links nay toi first node cu link->next = head; //tro first toi first node moi head = link;//xoa phan tu dau tienstruct node* deleteFirst() //luu tham chieu toi first link struct node *tempLink = head; //danh dau next toi first link la first head = head->next; //tra ve liên kết bi xoa return tempLink;//kiem tra danh sách co trong tuyệt khongbool isEmpty() return head == NULL;int length() int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) length++; return length;//tim mot link voi key domain authority chostruct node* find(int key) //bat dau tim tu first liên kết struct node* current = head; //neu danh mục la trong if(head == NULL) return NULL; //duyet qua danh mục while(current->key != key) //neu day la last node if(current->next == NULL) return NULL; else //di chuyen toi next links current = current->next; //neu tim vậy du lieu, tra ve link hien tai return current;//xoa mot liên kết voi key domain authority chostruct node* deleteKey(int key) //bat dau tu first link struct node* current = head; struct node* previous = NULL; //neu menu la trong if(head == NULL) return NULL; //duyet qua menu while(current->key != key) //neu day la last node if(current->next == NULL) return NULL; else //luu tham chieu toi links hien tai previous = current; //di chuyen toi next links current = current->next; //cap nhat link if(current == head) //thay doi first de tro toi next liên kết head = head->next; else //bo qua links hien tai previous->next = current->next; return current;// đắm say sap xepvoid sort() int i, j, k, tempKey, tempData ; struct node *current; struct node *next; int kích cỡ = length(); k = size ; for ( i = 0 ; i next ; for ( j = 1 ; j data > next->data ) tempData = current->data ; current->data = next->data; next->data = tempData ; tempKey = current->key; current->key = next->key; next->key = tempKey; current = current->next; next = next->next; } }// say mê dao nguoc listvoid reverse(struct node** head_ref) struct node* prev = NULL; struct node* current = *head_ref; struct node* next; while (current != NULL) next = current->next; current->next = prev; prev = current; current = next; *head_ref = prev;main() insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("Danh sach ban dau: "); //in danh sach printList(); while(!isEmpty()) struct node *temp = deleteFirst(); printf(" Gia tri bi xoa:"); printf("(%d,%d) ",temp->key,temp->data); printf(" Danh sach sau thời điểm da xoa gia tri: "); printList(); insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(" Phuc hoi danh sach: "); printList(); printf(" "); struct node *foundLink = find(4); if(foundLink != NULL) printf("Tim vắt phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tim vậy phan tu."); deleteKey(4); printf("Danh sach, sau khoản thời gian xoa mot phan tu: "); printList(); printf(" "); foundLink = find(4); if(foundLink != NULL) printf("Tim thay phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tim vắt phan tu."); printf(" "); sort(); printf("Danh sach sau thời điểm duoc sap xep: "); printList(); reverse(&head); printf(" Danh sach sau thời điểm bi dao nguoc: "); printList();Kết quả