Khái niệm danh sách liên kết đơn nhập vai trò quan trọng đặc biệt trong các thao tác làm việc lập trình. Ứng dụng nó đem về là cực kỳ lớn. Vì thế bạn hiểu nếu muốn tìm hiểu ngành này thì không thể bỏ qua những kiến thức về danh sách links đơn. Nội dung bài viết sau tự hutgiammo.com để giúp bạn đọc xem thêm thông tin về chủ đề này như định nghĩa, điểm lưu ý và cách setup danh sách links đơn.

Bạn đang xem:


Nội dung

3 Đặc điểm của danh sách liên kết đơn4 Cách setup danh sách link đơn4.3 Thêm thành phần vào danh sách liên kết đơn4.4 Xóa bộ phận khỏi danh sách links đơn

Tìm hiểu về list liên kết

Trước khi tìm hiểu về danh sách links đơn, ta sẽ bước đầu với danh sách liên kết trước. Để mang lại dễ hình dung, bạn cũng có thể hiểu danh sách links trong C có tác dụng khá tương tự với một mảng. Mặc dù vẫn có những điểm khác hoàn toàn nhất định. Cách phân biệt danh sách link và mảng như sau:

Nội dungMảngDanh sách liên kết
Kích thước

(Danh sách links chiếm ưu thế)

Kích thước được cố định mọi lúcTrong lúc khai báo buộc phải chỉ rõ kích thướcKích thước chuyển đổi liên tục trong quá trình thêm, sút phân tử.Kích thước tối đa chỉ dựa vào vào bộ nhớ
Cấp phát bộ nhớ

(Danh sách liên kết chiếm ưu thế)

Tĩnh: bộ nhớ lưu trữ được cung cấp theo cơ chế trong quy trình biên dịch.Động: bộ lưu trữ được cấp cho theo chính sách trong quy trình khởi chạy.
Thứ từ bỏ và giải pháp sắp xếp

(Danh sách links chiếm ưu thế)

Được bảo quản trên một dãy các ô nhớ ngay thức thì kềĐược cất giữ trên các ô ghi nhớ bất kỳ
Truy cập

(Mảng chiếm phần ưu thế)

Bằng cách thực hiện chỉ số mảng, được cho phép truy cập đến 1 phần tử ngẫu nhiên: O(1)Muốn truy vấn đến phần tử ngẫu nhiên rất cần phải trải qua quy trình duyệt từ trên đầu đến cuối bộ phận đó: O(n)
Tìm kiếm

(Mảng chiếm ưu thế)

Có thể search kiếm bằng 2 ngôn ngữ tuyến tính với nhị phânChỉ hoàn toàn có thể tìm kiếm bằng tuyến tính
Danh sách links đơn (Single linked list) là 1 trong những trong 3 phân một số loại của danh sách links C++.

Danh sách liên kết đơn là gì?

Danh sách link đơn nói một cách khác là Single Linked List. Nó được dùng làm chỉ một cấu tạo dữ liệu di động cầm tay hay còn rất có thể hình dung như một list mà trong những số ấy mỗi bộ phận đều liên kết với bộ phận đứng sau nó.


*

Mô hình danh sách liên kết đơn


Single Linked danh mục được dùng thịnh hành với ngôn ngữ lập trình C++. Trong Linked danh mục C++, mỗi thành phần được kết cấu nên từ nhì thành phần chính. Đó là thành phần tài liệu và nguyên tố liên kết. Yếu tắc dữ liệu chịu trách nhiệm lưu trữ thông tin về bản thân bộ phận đó. Còn nguyên tố liên kết để giúp lưu địa chỉ của thành phần đứng sau bộ phận chủ thể đó. Nếu thành phần được xét đã đứng cuối danh sách thì thành phần liên kết sẽ bằng NULL. Một phần tử hoàn hảo được cấu thành từ bỏ data (dữ liệu) với pointer (liên kết) sẽ được gọi là một node (hay còn gọi là nút).

Đặc điểm của danh sách links đơn

Tính cấp phát dữ liệu động

Trong khi chạy chương trình, Single liên kết list C++ đang được cấp phát bộ nhớ. Các thành phần được tàng trữ một cách bỗng nhiên trong RAM. Khi thêm hoặc sút phần tử, size của danh sách cũng sẽ thay đổi. Form size tối đa của Single linked menu trong c++ phụ thuộc vào bộ lưu trữ khả dụng của RAM.

Tính link của phần tử đầu và bộ phận đứng sau

Vì gồm sự links giữa nhị phần đứng trước lép vế nên chỉ việc nắm được thông tin của thành phần đầu tiên và bộ phận cuối thuộc là tín đồ dùng có thể dễ dàng quản lý được cả danh sách. Tuy nhiên nếu muốn truy cập đến một vị trí ngẫu nhiên thì phải tiến hành duyệt từ trên đầu đến bộ phận đó. Ko kể ra, trong danh sách links đơn C++ cũng chỉ được cho phép người dùng tìm kiếm đường tính độc nhất vô nhị 1 phân tử.

Cách thiết đặt danh sách links đơn

Tạo node

Một list được tạo lên từ khá nhiều node. Vì thế ta đã đi từ cách tạo node trước. Như sẽ nói ở trên, một node bao gồm 2 phần là thành phần link và yếu tố dữ liệu. Đối với yếu tắc dữ liệu, bạn có thể tự tạo ra lên dữ liệu theo ý thích (class) hoặc sử dụng tài liệu có sẵn (struct). Còn phần links thì dĩ nhiên sẽ là con trỏ. Con trỏ này trỏ trường đoản cú node trước đến node cạnh bên phía sau.

Với phần ví dụ chế tác node này, ta sẽ sử dụng int mang lại phần dữ liệu như sau:

struct Node

int data;

Node* next;

;

Để tạo thêm một node mới, ta sẽ thực hiện khởi tạo nên giá trị ban đầu và trả add về mang đến node được cấp cho phát.

Node* CreateNode(int init_data)

{

Node* node = new Node;

node->data = init_data;

node->next = NULL;

Node vừa mới được tạo chưa thêm vào list nên chưa links với thành phần nào cả. Cho nên vì thế nên phần links gán bằng NULL.

Code danh sách liên kết đơn C++


*

Thêm một node vào giữa danh sách link đơn


Khi đã tất cả sẵn các node rồi, ta sẽ triển khai tạo lập 1 danh mục trong C++. Vày đặc tính của node là link với nhau bắt buộc ta chỉ cần nắm được tin tức của node đầu (head) cùng nốt cuối (tail) là có thể cai quản được danh sách.

struct LinkedList

Node* head;

Node* tail;

;

Khi hàm tạo list mới được hình thành, bọn chúng vẫn không có bộ phận nào cả. Chính vì như vậy ta vẫn gắn phần đầu và cuối nhất thời vào NULL.

void CreateList(LinkedList& l)

l.head = NULL;

l.tail = NULL;

Thêm thành phần vào danh sách liên kết đơn

Thêm bộ phận đầu

Đầu tiên ta cần xác minh xem danh sách link đơn này còn có rỗng giỏi không. Nếu danh sách đó rỗng, ta gán luôn luôn head vào node cần thêm. Nếu list không rỗng, ta trỏ link từ head vào node mới. Kế tiếp mới gán lại head vào node này.

void AddHead(LinkedList& l, Node* node)

if (l.head == NULL)

l.head = node;

l.tail = node;

else

node->next = l.head;

l.head = node;

Thêm thành phần đuôi
*

Thêm một node vào đuôi danh sách


Tương tự như cách thêm phần tử đầu, ta cũng trở nên xác định coi danh sách này có rỗng tuyệt không. Ví như rỗng thì cho node mới làm tail luôn. Nếu không rỗng thì trỏ tail sẵn gồm đến node này rồi gán lại tail vào node new được trỏ.

void AddTail(LinkedList& l, Node* node)

if (l.head == NULL)

l.head = node;

l.tail = node;

else

l.tail->next = node;

l.tail = node;

Thêm vào điểm bất kỳ

Gọi p. Là node yêu cầu thêm, còn q là node đằng trước vị trí yêu cầu thêm. Đầu tiên, ta sẽ khám nghiệm xem node q có gán với NULL tuyệt không. Nếu bao gồm gán có nghĩa là danh sách rỗng. Lúc đó chỉ cần gán p lên đầu là được. Giả dụ không, người tiêu dùng sẽ tiến hành theo công việc sau: trỏ p->next = q->next, kế tiếp q->next = phường Khi hoàn thành, phải kiểm tra tiếp q có phải nốt cuối xuất xắc không. Nếu đề nghị thì cần thường xuyên gán phường vài tail.

void InsertAfterQ(LinkedList& l, Node* p, Node* q)

{

if (q != NULL)

{

p->next = q->next;

q->next = p;

Xóa phần tử khỏi danh sách liên kết đơn

Xóa làm việc đầu

Đầu tiên, ta triển khai kiểm tra xem danh sách đó có rỗng không. Nếu gồm thì trực tiếp xóa đi cùng để giá trị bằng 0 là được. Còn nếu list không rỗng thì tiến hành theo những bước sau. Đầu tiên là gán lại head vào vị trí đằng sau bộ phận cần xóa, nhớ yêu cầu lưu head lại. Sau đó mới triển khai xóa.

int RemoveHead(LinkedList& l, int& x)

if (l.head != NULL)

Node* node = l.head;

x = node->data; // Lưu quý giá của node head lại

l.head = node->next;

delete node; // hủy node head đi

if (l.head == NULL)

l.tail = NULL;

return 1;

return 0;

Xóa nghỉ ngơi điểm bất kỳ
*

Cách xóa một node


Nếu đề xuất xóa node p. Sau một node q bất kỳ, ta sẽ có được 3 ngôi trường hợp phải xét:

Nếu q là NULL suy ra list rỗng, không cần xóa mà chỉ cần chỉnh về 0Nếu next của q là NULL, minh chứng p là NULL, suy ra p. Không tồn tại để xóaNếu p. Có tồn tại, soát sổ xem p có cần tail không, nếu có thì chỉ việc gán tail lại vào q là được.

int RemoveAfterQ(LinkedList& l, Node* q, int& x)

if (q != NULL)

Node* phường = q->next;

if (p != NULL)

if (l.tail == p)

l.tail = q;

q->next = p->next;

x = p->data;

delete p;

return 1;

return 0;

return 0;

Duyệt danh sách link đơn với in

Để khám nghiệm xem danh sách đã hoàn hảo hay chưa, ta sẽ gán một node bằng head. Sau đó kiểm tra xem node kia NULL xuất xắc không. Nếu đã đạt tức là ta đã có tài liệu của node này. Tiếp tục thực hiện thao tác làm việc đó cho đến node NULL, đó bao gồm tail của danh sách.

Xem thêm: Các Phương Pháp Giải Phương Trình Vô Tỉ Lớp 9, Chuyên Đề: Phương Pháp Giải Phương Trình Vô Tỉ

Vậy trong nội dung bài viết vừa rồi, hutgiammo.com đã hỗ trợ bạn tham khảo thêm về các điểm lưu ý của danh sách link đơn cũng tương tự cách tạo một danh sách hoàn chỉnh. Hy vọng rằng những kiến thức và kỹ năng này để giúp đỡ ích cho quy trình học tập và thao tác của bạn.