LINKED LIST LÀ GÌ

Danh sách links (Linked List) là gì ?

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

Bạn đang xem: Linked list là gì

Danh sách liên kết là cấu trúc tài liệu được thực hiện phổ cập thiết bị nhị sau mảng. Dưới đó là những định nghĩa cơ bạn dạng tương quan tới Danh sách liên kết:

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

Biểu diễn Danh sách links (Linked List)

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

*

Dưới đây là một trong những vấn đề cần lưu giữ về Danh sách liên kết:

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

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

Dưới đó là những các loại Danh sách links (Linked List) nhiều dạng:

Danh sách liên kết đơn (Simple Linked List): chỉ chuẩn y các thành phần theo hướng về trước.Danh sách liên kết đôi (Doubly Linked List): các thành phần rất có thể được lưu ý theo chiều về trước hoặc về sau.Danh sách link vòng (Circular Linked List): bộ phận sau cùng chứa liên kết của thành phần đầu tiên như là next với phần tử thứ nhất bao gồm liên kết cho tới phần tử ở đầu cuối như thể prev.

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

Dưới đây là một số chuyển động cơ phiên bản có thể được tiến hành vì chưng một danh sách liên kết:

Hoạt đụng chèn: thêm 1 phần tử vào đầu list liên kết.Hoạt động xóa (bộ phận đầu): xóa 1 phần tử trên đầu danh sách liên kết.Hiển thị: hiển thị toàn thể list.Hoạt động tìm kiếm kiếm: tìm kiếm kiếm phần tử bởi áp dụng khóa (key) đã hỗ trợ.Hoạt hễ xóa (bởi vì áp dụng khóa): xóa một trong những phần tử vì chưng sử dụng khóa (key) sẽ hỗ trợ.

Hoạt động chèn trong Danh sách liên kết

Việc thêm 1 nút ít bắt đầu vào trong danh sách links không chỉ là là 1 trong chuyển động thêm dễ dàng và đơn giản nhỏng trong những kết cấu tài liệu không giống (chính vì chúng ta gồm dữ liệu và gồm link). Chúng ta đang mày mò trải qua sơ đồ dưới đây. Thứ nhất, sản xuất một nút vày sử dụng thuộc cấu tạo và tra cứu địa chỉ để chèn nút ít này.

Xem thêm: Làm Thế Nào Để Dịu Dàng Hơn, Học Cách Trở Thành Một Cô Gái Dịu Dàng

*

Giả sử bọn họ yêu cầu chèn một nút ít B vào giữa nút A (nút trái) và C (nút phải). Do đó: B.next trỏ cho tới C.

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

*

Bây tiếng, next của nút bên trái đã trsinh sống tới nút bắt đầu.

LeftNode.next −> NewNode;

*

Quá trình trên đang đặt nút ít new vào giữa nhì nút. lúc kia danh sách mới vẫn trông như sau:

*

Các bước tương tự như sẽ được tiến hành trường hợp ckém nút ít vào đầu list link. Trong lúc để một nút vào địa chỉ cuối của list, thìnút máy nhì tính từ nút sau cùng của list đã trỏ cho tới nút new và nút mới vẫn trỏ cho tới NULL.

Hoạt động xóa vào Danh sách liên kết

Hoạt động xóa vào Danh sách links cũng tinh vi rộng vào cấu trúc dữ liệu khác. Trước hết họ nên định vị nút buộc phải xóa vì sử dụng các giải thuật kiếm tìm tìm.

*

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

LeftNode.next −> TargetNode.next;

*

Quá trình này đã xóa links trỏ cho tới nút ít bắt buộc xóa. Bây giờ đồng hồ bọn họ đang xóa hồ hết gì mà lại nút ít yêu cầu xóa đang trỏ cho tới.

TargetNode.next −> NULL;

*

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

*

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

Với hoạt động này, bạn phải cẩn trọng. Chúng ta yêu cầu tạo nên nút ít đầu (head) trỏ tới nút ít sau cuối và hòn đảo ngược toàn bộ danh sách link.

*

Thứ nhất, bọn họ chú tâm tới phần cuối của list. Nút này vẫn trỏ cho tới NULL. Bây giờ vấn đề cần làm cho là làm cho nút ít cuối này trỏ cho tới nút ít vùng trước của nó.

*

Chúng ta yêu cầu đảm bảo rằng nút cuối cùng này vẫn không biến thành thất lạc, cho nên họ đã thực hiện một trong những nút ít trợ thời (temp node – giống như những đổi thay nhất thời trung gian nhằm giữ giàng giá trị). Tiếp theo, chúng ta đang tạo nên từng nút phía bên trái đang trỏ cho tới nút trái của bọn chúng.

*

Sau kia, nút thứ nhất sau nút ít head vẫn trỏ cho tới NULL.

*

Chúng ta vẫn làm cho nút ít head trỏ cho tới nút đầu tiên mới do thực hiện các nút ít tạm bợ.

*

Bây giờ đồng hồ Danh sách links đã biết thành đảo ngược.

Danh sách link (Linked List) trong C

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

Cmùi hương trình minch họa Danh sách link (Linked List) vào 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 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 tmê mệt chieu toi first link struct node *tempLink = head; //danh dau next toi first liên kết la first head = head->next; //tra ve sầu links bi xoa return tempLink;//kiem tra list 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;//tim mot links voi key da chostruct node* find(int key) //bat dau tim tu first links 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 link current = current->next; //neu tlặng cố du lieu, tra ve sầu liên kết 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 các mục la vào 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 mê chieu toi links hien tai previous = current; //di chuyen toi next links current = current->next; //cap nhat link if(current == head) //nuốm doi first de tro toi next links 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 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; } }// ham 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 khoản thời gian 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 nắm phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf(" "); else printf("Khong tim nỗ lực phan tu."); deleteKey(4); printf("Danh sach, sau thời điểm 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 cố gắng phan tu."); printf(" "); sort(); printf("Danh sach sau thời điểm duoc sap xep: "); printList(); reverse(&head); printf(" Danh sach sau khi bi dao nguoc: "); printList();Kết quả