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

Một Danh sách link (Linked List) là một trong những hàng các cấu trúc dữ liệu được liên kết với nhau thông qua các link (link). Hiểu một giải pháp đơn giản và dễ dàng thì Danh sách liên kết là 1 trong kết cấu dữ liệu gồm một team những nút ít (node) chế tạo thành một chuỗi. Mỗi nút ít bao gồm dữ liệu nghỉ ngơi nút đó cùng tham mê chiếu đến nút ít tiếp đến trong chuỗi.

Bạn đang xem:

Danh sách links là cấu tạo tài liệu được sử dụng phổ cập trang bị nhị sau mảng. Dưới đấy là các có mang cơ bạn dạng liên quan cho tới Danh sách liên kết:

Link (liên kết): từng link của một Danh sách links rất có thể giữ lại một tài liệu được gọi là một trong những phần tử.Next: Mỗi link của một Danh sách links chứa một liên kết tới next links được hotline là Next.First: một Danh sách link bao hàm các liên kết kết nối tới first links được Call là First.

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

Danh sách liên kết hoàn toàn có thể được màn biểu diễn như là 1 chuỗi các nút ít (node). Mỗi nút ít vẫn trỏ cho tới nút ít sau đó.

*

Dưới đó là một số trong những điểm cần nhớ về Danh sách liên kết:

Danh sách link cất một trong những phần tử link thì được Điện thoại tư vấn là First.Mỗi link mang 1 trường dữ liệu cùng một ngôi trường liên kết được hotline là Next.Mỗi liên kết được liên kết với link tiếp nối vày thực hiện links tiếp nối của nó.Link cuối cùng mang một links là null để ghi lại điểm cuối của danh sách.

Các nhiều loại Danh sách links (Linked List)

Dưới đấy là các loại Danh sách liên kết (Linked List) nhiều dạng:

Danh sách link 1-1 (Simple Linked List): chỉ để ý những phần tử theo chiều về trước.Danh sách liên kết song (Doubly Linked List): các phần tử có thể được chú ý theo hướng về trước hoặc sau này.Danh sách links vòng (Circular Linked List): phần tử ở đầu cuối chứa liên kết của bộ phận đầu tiên như là next và thành phần thứ nhất tất cả link tới phần tử cuối cùng như thể prev.

Các vận động cơ bản bên trên Danh sách liên kết

Dưới đây là một vài chuyển động cơ phiên bản hoàn toàn có thể được thực hiện vị một list liên kết:

Hoạt cồn chèn: thêm một phần tử vào đầu list liên kết.Hoạt hễ xóa (phần tử đầu): xóa một phần tử trên đầu danh sách link.Hiển thị: hiển thị toàn bộ danh sách.Hoạt cồn tìm kiếm kiếm: kiếm tìm kiếm bộ phận vì áp dụng khóa (key) sẽ cung ứng.Hoạt cồn xóa (do sử dụng khóa): xóa 1 phần tử bởi thực hiện khóa (key) vẫn cung cấp.

Hoạt rượu cồn chèn vào Danh sách liên kết

Việc thêm 1 nút mới vào trong list liên kết không những là 1 trong vận động thêm dễ dàng và đơn giản nhỏng trong các cấu trúc dữ liệu không giống (cũng chính vì chúng ta bao gồm dữ liệu với tất cả link). Chúng ta sẽ tò mò trải qua sơ vật dụng dưới đây. Trước hết, sinh sản một nút vày thực hiện thuộc cấu trúc cùng kiếm tìm địa chỉ nhằm cnhát nút ít này.

*

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

NewNode.next −> RightNode;Hình minch họa nlỗi sau:

*

Bây giờ đồng hồ, next của nút phía bên trái đang trlàm việc tới nút ít mới.

LeftNode.next −> NewNode;

*

Quá trình trên đã đặt nút ít mới vào giữa hai nút ít. khi đó list new đang trông như sau:

*

Các bước tương tự như sẽ tiến hành triển khai nếu cnhát nút vào đầu list link. Trong khi đặt một nút vào địa chỉ cuối của list, thìnút ít thứ hai tính trường đoản cú nút ít sau cùng của danh sách đang trỏ cho tới nút ít mới cùng nút bắt đầu sẽ trỏ cho tới NULL.

Hoạt rượu cồn xóa vào Danh sách liên kết

Hoạt động xóa vào Danh sách link cũng tinh vi rộng vào cấu tạo tài liệu không giống. trước hết bọn họ phải xác định nút bắt buộc xóa bởi thực hiện các lời giải kiếm tìm tìm.

*

Bây tiếng, nút bên trái (prev) của nút đề nghị xóa bắt buộc trỏ cho tới nút ít kế tiếp (next) của nút ít bắt buộc xóa.

LeftNode.next −> TargetNode.next;

*

Quá trình này đã xóa links trỏ cho tới nút ít yêu cầu xóa. Bây giờ bọn họ sẽ xóa phần nhiều gì nhưng nút ít đề xuất xóa đang trỏ tới.

TargetNode.next −> NULL;

*

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

*

Hoạt cồn đảo ngược Danh sách liên kết

Với hoạt động này, bạn phải cẩn thận. Chúng ta cần khiến cho nút đầu (head) trỏ cho tới nút ít sau cùng và đảo ngược toàn thể danh sách liên kết.

*

Trước tiên, bọn họ xem xét cho tới phần cuối của list. Nút này sẽ trỏ cho tới NULL. Bây tiếng điều cần có tác dụng là khiến cho nút cuối này trỏ tới nút ít vùng phía đằng trước của nó.

*

Chúng ta yêu cầu bảo vệ rằng nút sau cùng này đã không xẩy ra thất lạc, vì vậy họ đã thực hiện một số nút ít tạm (temp node – giống như các vươn lên là tạm thời trung gian nhằm giữ lại giá chỉ trị). Tiếp theo, chúng ta đang làm cho từng nút phía bên trái sẽ trỏ cho tới nút trái của chúng.

*

Sau đó, nút đầu tiên sau nút head đang trỏ cho tới NULL.

*

Chúng ta đang tạo cho nút ít head trỏ cho tới nút ít trước tiên new vì chưng sử dụng các nút trợ thì.

*

Bây tiếng Danh sách links đã trở nên hòn đảo ngược.

Xem thêm: Cách Thay Đổi Hoặc Bỏ Quick Access Win 10 Tự Thêm Thư Mục Vào Quick Access

Danh sách links (Linked List) trong C

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

Cmùi hương trình minc họa Danh sách link (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 links tai vi tri dau tienvoid insertFirst(int key, int data) //tao mot liên kết struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //tro link ni toi first node cu link->next = head; //tro first toi first node moi head = link;//xoa phan tu dau tienstruct node* deleteFirst() //luu tđắm say chieu toi first liên kết struct node *tempLink = head; //danh dau next toi first links la first head = head->next; //tra ve link bi xoa return tempLink;//kiem tra danh sách teo trong xuất xắc khongbool isEmpty() return head == NULL;int length() int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) length++; return length;//tyên mot liên kết voi key domain authority chostruct node* find(int key) //bat dau tyên tu first link struct node* current = head; //neu các mục la vào if(head == NULL) return NULL; //duyet qua các 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 tyên ổn núm du lieu, tra ve sầu link hien tai return current;//xoa mot link voi key domain authority chostruct node* deleteKey(int key) //bat dau tu first link struct node* current = head; struct node* previous = NULL; //neu các mục la vào if(head == NULL) return NULL; //duyet qua list while(current->key != key) //neu day la last node if(current->next == NULL) return NULL; else //luu tmê man chieu toi link hien tai previous = current; //di chuyen toi next link current = current->next; //cap nhat links if(current == head) //chũm 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;// ham mê sap xepvoid sort() int i, j, k, tempKey, tempData ; struct node *current; struct node *next; int size = 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; } }// đắm đuối 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 domain authority 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("Tyên ổn cầm cố phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tyên cố kỉnh phan tu."); deleteKey(4); printf("Danh sach, sau khi xoa mot phan tu: "); printList(); printf(" "); foundLink = find(4); if(foundLink != NULL) printf("Tyên vắt phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tim thế phan tu."); printf(" "); sort(); printf("Danh sach sau khoản thời gian duoc sap xep: "); printList(); reverse(&head); printf(" Danh sach sau khoản thời gian bi dao nguoc: "); printList();Kết quả