Tóm Tắt
Tìm hiểu về danh sách liên kết
Trước khi tìm hiểu và khám phá về danh sách liên kết đơn, ta sẽ khởi đầu với danh sách liên kết trước. Để cho dễ tưởng tượng, bạn hoàn toàn có thể hiểu danh sách liên kết trong C có công dụng khá giống với một mảng. Tuy nhiên vẫn có những điểm độc lạ nhất định. Cách phân biệt danh sách liên kết và mảng như sau :
| Nội dung | Mảng | Danh sách liên kết |
| Kích thước( Danh sách liên kết chiếm lợi thế ) |
|
|
| Cấp phát bộ nhớ
(Danh sách liên kết chiếm ưu thế) Bạn đang đọc: Danh sách liên kết đơn – Tất cả thông tin chi tiết nhất |
|
|
| Thứ tự và cách sắp xếp( Danh sách liên kết chiếm lợi thế ) |
|
|
| Truy cập( Mảng chiếm lợi thế ) |
|
|
| Tìm kiếm( Mảng chiếm lợi thế ) |
|
|
Danh sách liên kết đơn ( Single linked list ) là một trong 3 phân loại của danh sách liên kết C + + .
Danh sách liên kết đơn là gì ?
Danh sách liên kết đơn còn được gọi là Single Linked List. Nó được dùng để chỉ một cấu trúc tài liệu di động hay còn hoàn toàn có thể tưởng tượng như một danh sách mà trong đó mỗi thành phần đều liên kết với thành phần đứng sau nó .
Single Linked List được dùng thông dụng với ngôn từ lập trình C + +. Trong Linked List C + +, mỗi thành phần được cấu trúc nên từ hai thành phần chính. Đó là thành phần tài liệu và thành phần liên kết. Thành phần tài liệu chịu nghĩa vụ và trách nhiệm tàng trữ thông tin về bản thân thành phần đó. Còn thành phần liên kết sẽ giúp lưu địa chỉ của thành phần đứng sau thành phần chủ thể đó. Nếu thành phần được xét đang đứng cuối danh sách thì thành phần liên kết sẽ bằng NULL. Một thành phần hoàn hảo được cấu thành từ data ( tài liệu ) và pointer ( liên kết ) sẽ được gọi là một node ( hay còn được gọi là nút ) .
Đặc điểm của danh sách liên kết đơn
Tính cấp phép tài liệu động
Trong khi chạy chương trình, Single link list C + + sẽ được cấp phép bộ nhớ. Các thành phần được tàng trữ một cách ngẫu nhiên trong RAM. Khi thêm hoặc bớt thành phần, kích cỡ của danh sách cũng sẽ đổi khác. Kích thước tối đa của Single linked list trong c + + nhờ vào vào bộ nhớ khả dụng của RAM .
Tính liên kết của thành phần đầu và thành phần đứng sau
Vì có sự liên kết giữa hai phần đứng trước đứng sau nên chỉ cần nắm được thông tin của thành phần tiên phong và thành phần sau cuối là người dùng hoàn toàn có thể thuận tiện quản trị được cả danh sách. Tuy nhiên nếu muốn truy vấn đến một vị trí bất kể thì phải triển khai duyệt từ đầu đến thành phần đó. Ngoài ra, trong danh sách liên kết đơn C + + cũng chỉ được cho phép người dùng tìm kiếm tuyến tính duy nhất 1 phân tử .
Cách thiết lập danh sách liên kết đơn
Tạo node
Một danh sách được tạo lên từ nhiều node. Do vậy ta sẽ đi từ bước tạo node trước. Như đã nói ở trên, một node gồm có 2 phần là thành phần liên kết và thành phần tài liệu. Đối với thành phần tài liệu, bạn hoàn toàn có thể tự tạo lên tài liệu theo ý muốn ( class ) hoặc sử dụng tài liệu có sẵn ( struct ). Còn phần liên kết thì đương nhiên sẽ là con trỏ. Con trỏ này trỏ từ node trước đến node liền kề phía sau .Với phần ví dụ tạo node này, ta sẽ sử dụng int cho phần tài liệu như sau :struct Node{int data ;Node * next ;} ;Để tạo thêm 1 node mới, ta sẽ thực thi khởi tạo giá trị khởi đầu và trả địa chỉ về cho node được cấp phép .Node * CreateNode ( int init_data ){Node * node = new Node ;node -> data = init_data ;node -> next = NULL ;Node vừa được tạo chưa thêm vào danh sách nên chưa liên kết với thành phần nào cả. Do đó nên phần liên kết gán bằng NULL .
Code danh sách liên kết đơn C + +
Khi đã có sẵn những node rồi, ta sẽ thực thi tạo lập 1 list trong C + +. Do đặc tính của node là liên kết với nhau nên ta chỉ cần nắm được thông tin của node đầu ( head ) và nốt cuối ( tail ) là hoàn toàn có thể quản trị được danh sách .struct LinkedList{Node * head ;Node * tail ;} ;Khi hàm tạo danh sách mới được hình thành, chúng vẫn chưa có thành phần nào cả. Vì thế ta sẽ gắn phần đầu và cuối tạm vào NULL .void CreateList ( LinkedList và 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 thành phần đầu
Đầu tiên ta cần xác lập xem danh sách liên kết đơn này có rỗng hay không. Nếu danh sách đó rỗng, ta gán luôn head vào node cần thêm. Nếu danh sách không rỗng, ta trỏ liên kết từ head vào node mới. Sau đó mới gán lại head vào node này .void AddHead ( LinkedList và 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
Tương tự như cách thêm thành phần đầu, ta cũng sẽ xác lập xem danh sách này có rỗng hay không. Nếu rỗng thì cho node mới làm tail luôn. Nếu không rỗng thì trỏ tail sẵn có đến node này rồi gán lại tail vào node mới được trỏ .void AddTail ( LinkedList và 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 cần thêm, còn q là node đằng trước vị trí cần thêm. Đầu tiên, ta sẽ kiểm tra xem node q có gán với NULL hay không. Nếu có gán tức là danh sách rỗng. Khi đó chỉ cần gán p lên đầu là được. Nếu không, người dùng sẽ triển khai theo những bước sau : trỏ p -> next = q -> next, sau đó q -> next = p. Khi triển khai xong, phải kiểm tra tiếp q có phải nốt cuối hay không. Nếu phải thì cần liên tục gán p vài tail .void InsertAfterQ ( LinkedList và l, Node * p, Node * q ){if ( q ! = NULL ){p -> next = q -> next ;q -> next = p ;
Xóa thành phần khỏi danh sách liên kết đơn
Xóa ở đầu
Đầu tiên, ta thực thi kiểm tra xem danh sách đó có rỗng không. Nếu có thì trực tiếp xóa đi và để giá trị bằng 0 là được. Còn nếu danh sách không rỗng thì thực thi theo những bước sau. Đầu tiên là gán lại head vào vị trí đằng sau thành phần cần xóa, nhớ phải lưu head lại. Sau đó mới triển khai xóa .int RemoveHead ( LinkedList và l, int và x ){if ( l.head ! = NULL ){Node * node = l.head ;x = node -> data ; / / Lưu giá trị của node head lạil.head = node -> next ;delete node ; / / Hủy node head điif ( l.head = = NULL )l.tail = NULL ;return 1 ;}return 0 ;}
Xóa ở điểm bất kể
Nếu cần xóa node p sau một node q bất kể, ta sẽ có 3 trường hợp cần xét :
- Nếu q là NULL suy ra danh sách rỗng, không cần xóa mà chỉ cần chỉnh về 0
- Nếu next của q là NULL, chứng tỏ p là NULL, suy ra p không tồn tại để xóa
- Nếu p có tồn tại, kiểm tra xem p có phải tail không, nếu có thì chỉ cần gán tail lại vào q là được.
int RemoveAfterQ ( LinkedList và l, Node * q, int và x ){if ( q ! = NULL ){Node * p = 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 liên kết đơn và in
Để kiểm tra 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 đó NULL hay không. Nếu đã đạt tức là ta đã có tài liệu của node này. Tiếp tục triển khai thao tác đó cho đến node NULL, đó chính tail của danh sách .
Mời bạn đọc tìm hiểu thêm thêm : SQL là gì ?
Vậy trong bài viết vừa qua, Teky đã giúp bạn khám phá thêm về những đặc thù của danh sách liên kết đơn cũng như cách tạo một danh sách hoàn hảo. Mong rằng những kiến thức và kỹ năng này sẽ giúp ích cho quy trình học tập và thao tác của bạn .
Source: https://final-blade.com
Category: Kiến thức Internet
