Chi Tiết Bài Học Danh Sách Liên Kết Đơn

     

Khái niệm danh sách links đơn nhập vai trò đặc biệt trong các thao tác làm việc lập trình. Ứng dụng nó đem lại là vô cùng lớn. Chính vì như vậy bạn gọi nếu muốn tìm hiểu ngành này thì không thể bỏ qua các kiến thức về danh sách link đơn. Bài viết sau trường đoản cú giangdien.com.vn sẽ giúp bạn đọc tìm hiểu thêm thông tin về chủ thể này như định nghĩa, điểm lưu ý và cách setup danh sách links đơn.

Bạn đang xem: Chi tiết bài học danh sách liên kết đơn


Nội dung

3 Đặc điểm của danh sách liên kết đơn4 Cách thiết lập danh sách link đơn4.3 Thêm bộ phận vào danh sách liên kết đơn4.4 Xóa thành phần khỏi danh sách liên kết đơn5 học tập lập trình, công nghệ tại giangdien.com.vn – tin tức cần biết

Tìm hiểu về danh sách liên kết

Trước khi tò mò về danh sách links đơn, ta sẽ ban đầu với danh sách liên kết trước. Để mang đến dễ hình dung, bạn cũng có thể hiểu danh sách links trong C có công dụng khá tương tự với một mảng. Tuy nhiên vẫn bao gồm điểm khác biệt nhất định. Biện pháp phân biệt danh sách liên kết 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 khi khai báo đề xuất chỉ rõ kích thướcKích thước đổi khác liên tục trong quá trình thêm, bớt phân tử.Kích thước buổi tối đa chỉ nhờ vào vào cỗ 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 cấp cho theo chế độ trong quy trình biên dịch.Động: bộ lưu trữ được cấp cho theo cơ chế trong quy trình khởi chạy.
Thứ trường đoản cú và giải pháp sắp xếp

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

Được giữ gìn trên một dãy các ô nhớ tức thì kềĐược giữ lại 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, chất nhận được truy cập đến một trong những 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ừ đầu đến cuối phần tử đó: O(n)
Tìm kiếm

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

Có thể tìm kiếm kiếm bằng 2 ngôn ngữ tuyến tính và nhị phânChỉ rất có thể tìm kiếm bằng tuyến tính
Danh sách links đơn (Single linked list) là một trong 3 phân nhiều loại của danh sách liên kết C++.

Danh sách link đơn là gì?

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


*

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


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

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

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

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

Tính liên kết của thành phần đầu và bộ phận đứng sau

Vì bao gồm sự link giữa hai phần đứng trước đứng sau nên chỉ cần nắm được tin tức của phần tử đầu tiên và phần tử cuối cùng là tín đồ dùng rất có thể dễ dàng làm chủ được cả danh sách. Mặc dù 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 thành phần đó. Không tính ra, vào danh sách liên kết đơn C++ cũng chỉ có thể chấp nhận được người dùng tìm kiếm con đường tính tuyệt nhất 1 phân tử.

Cách thiết lập danh sách link đơn

Tạo node

Một list được chế tạo lên từ khá nhiều node. Vì vậy ta đang đi từ bước tạo node trước. Như vẫn nói sinh sống trên, một node bao gồm 2 phần là thành phần link và nhân tố dữ liệu. Đối với nguyên tố dữ liệu, chúng ta có thể tự tạo ra lên dữ 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ì tất nhiên sẽ là bé trỏ. Bé trỏ này trỏ từ node trước mang đến node ngay cạnh phía sau.

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

struct Node

int data;

Node* next;

;

Để tạo thêm 1 node mới, ta sẽ thực hiện khởi chế tác giá trị ban đầu và trả địa chỉ cửa hàng về mang đến node được cấp 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 phần tử nào cả. Cho nên nên phần link gán bằng NULL.

Code danh sách links đơn C++


*

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


Khi đã gồm sẵn đa số node rồi, ta sẽ thực hiện tạo lập 1 menu trong C++. Vì đặc tính của node là links với nhau phải ta chỉ việc nắm được thông tin của node đầu (head) và nốt cuối (tail) là gồm thể quản lý được danh sách.

Xem thêm: Thuật Toán Chia Để Trị - Giải Thuật Chia Để Trị (Divide And Conquer)

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ó phần tử nào cả. Chính vì như thế ta đang gắn phần đầu cùng cuối trợ thì vào NULL.

void CreateList(LinkedList& l)

l.head = NULL;

l.tail = NULL;

Thêm thành phần vào danh sách link đơn

Thêm bộ phận đầu

Đầu tiên ta cần xác minh xem danh sách links đơn này có rỗng tuyệt không. Nếu danh sách đó rỗng, ta gán luôn luôn head vào node phải thêm. Nếu list không rỗng, ta trỏ links từ head vào node mới. Tiếp nối 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 thành phần đầu, ta cũng biến thành xác định coi danh sách này có rỗng giỏi không. Nếu rỗng thì cho node new làm tail luôn. Nếu như 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 mới đượ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 phường là node đề xuất thêm, còn q là node đằng trước vị trí yêu cầu thêm. Đầu tiên, ta sẽ kiểm tra xem node q gồm gán với NULL tuyệt không. Nếu gồm gán tức là danh sách rỗng. Khi đó chỉ cần gán p lên đầu là được. Nếu như không, người dùng sẽ triển khai theo công việc sau: trỏ p->next = q->next, sau đó q->next = p. Khi trả thành, buộc phải kiểm tra tiếp q tất cả phải nốt cuối giỏi không. Nếu cần thì cần liên tục 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 thành phần khỏi danh sách link đơn

Xóa sinh sống đầu

Đầu tiên, ta tiến hành kiểm tra xem list đó gồm rỗng không. Nếu tất cả thì thẳng xóa đi với để giá trị bởi 0 là được. Còn nếu list không rỗng thì thực hiện 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ớ đề nghị lưu head lại. Tiếp đến 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 giá trị của node head lại

l.head = node->next;

delete node; // bỏ node head đi

if (l.head == NULL)

l.tail = NULL;

return 1;

return 0;

Xóa làm việc điểm bất kỳ
*

Cách xóa một node


Nếu nên xóa node p. Sau một node q bất kỳ, ta sẽ sở hữu 3 trường hợp đề nghị xét:

Nếu q là NULL suy ra danh sách rỗng, không nên xóa mà chỉ việc chỉnh về 0Nếu next của q là NULL, minh chứng p là NULL, suy ra phường không tồn tại nhằm xóaNếu phường có tồn tại, bình chọn xem p. Có yêu cầu tail không, nếu tất cả thì chỉ cần 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 liên kết đơn với in

Để kiểm tra xem list đã hoàn hảo hay chưa, ta vẫn gán một node bởi head. Tiếp đến kiểm tra coi node kia NULL tuyệt không. Nếu đang đạt có nghĩa là ta vẫn có tài liệu của node này. Thường xuyên thực hiện thao tác đó cho đến node NULL, đó bao gồm tail của danh sách.

Vậy trong nội dung bài viết vừa rồi, giangdien.com.vn đã giúp bạn bài viết liên quan về các đặc điểm của danh sách links đơn cũng như cách tạo ra một danh sách hoàn chỉnh. Hy vọng rằng những kiến thức này sẽ giúp ích cho quy trình học tập và thao tác của bạn.

Học lập trình, technology tại giangdien.com.vn – tin tức cần biết

giangdien.com.vn là học viện sáng chế công nghệ với chương trình huấn luyện STEAM (Science – công nghệ – Engineering – Art – Mathematics) theo chuẩn Mỹ đầu tiên tại Việt Nam dành cho trẻ em từ 4 đến 18 tuổi.

Được thành lập trong thời điểm tháng 6 năm 2016, giangdien.com.vn quyết tâm thực hiện sứ mệnh mang lại cho cụ hệ trẻ vn kiến thức trọn vẹn về STEAM, nhất là các tư duy công nghệ, khoa học laptop và kỹ năng thế kỷ 21 – 4Cs (Critical Thinking: bốn duy phản biện – Communication: giao tiếp – Creativity: trí tuệ sáng tạo – Collaboration: thao tác nhóm).

Xem thêm: Bài Tập Tương Lai Tiếp Diễn, Thì Tương Lai Tiếp Diễn (Future Continuous)


*

Trải nghiệm học tập lập trình miễn phí


Đây là chương trình không chỉ là trang bị kiến thức và kỹ năng lập trình hơn nữa rèn luyện nhóm kỹ năng 4Cs. Trẻ đã được:

Các bộ môn đào tạo và giảng dạy tại giangdien.com.vn gồm: lập trình và cải tiến và phát triển ứng dụng, thiết kế game, lập trình web với python  Lập trình Scratch Robotics Engineering, technology 3D với MultiMedia. Shop chúng tôi tin rằng trẻ em nước ta có cơ hội phát triển khỏe khoắn trong một nền kinh tế số và cần được trang bị sẵn sàng chuẩn bị để thay đổi những doanh nhân technology trong tương lai.

Liên hệ ngay học tập viện technology sáng tạo thành giangdien.com.vn nhằm được hỗ trợ tư vấn khóa học:

Cam kêt 7 tuổi hoàn toàn có thể lập trìnhTop 10 dự án công trình giáo dục tất cả tầm ảnh hưởng nhất Đông phái mạnh Á 2017 & 2018Top 3 dự án công trình xuất sắc đẹp nhất, NextGen – Thụy Sĩ Hotline Hà Nội: 024-7109-6668 | 0975-241-015 Hotline hồ Chí Minh: 028-7109 9948 | 097-900-8642