Danh Sách Liên Kết đơn - Tất Cả Thông Tin Chi Tiết Nhất - Teky

4.7/5 - (10 bình chọn)

Khái niệm danh sách liên kết đơn đóng vai trò quan trọng trong các thao tác lập trình. Ứng dụng nó mang lại là vô cùng lớn. Vì thế bạn đọc 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 liên kết đơn. Bài viết sau từ Teky sẽ giúp bạn đọc tìm hiểu thêm thông tin về chủ đề này như định nghĩa, đặc điểm và cách cài đặt danh sách liên kết đơn.

Nội dung

Toggle

• Tìm hiểu về danh sách liên kết
• Danh sách liên kết đơn là gì?
• Đặc điểm của danh sách liên kết đơn
  • Tính cấp phát dữ liệu động
  • Tính liên kết của phần tử đầu và phần tử đứng sau
• Cách cài đặt danh sách liên kết đơn
  • Tạo node
  • Code danh sách liên kết đơn C++
  • Thêm phần tử vào danh sách liên kết đơn
    • Thêm phần tử đầu
    • Thêm phần tử đuôi
    • Thêm vào điểm bất kỳ
  • Xóa phần tử khỏi danh sách liên kết đơn
    • Xóa ở đầu
    • Xóa ở điểm bất kỳ
  • Duyệt danh sách liên kết đơn và in
• Học lập trình, công nghệ tại Teky – thông tin cần biết
  • • Đây là chương trình không chỉ trang bị kiến thức lập trình mà còn rèn luyện nhóm kỹ năng 4Cs. Trẻ sẽ được:
  • Liên hệ ngay học viện công nghệ sáng tạo TEKY để được tư vấn khóa học:

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

Trước khi tìm hiểu về danh sách liên kết đơn, ta sẽ bắt đầu với danh sách liên kết trước. Để cho dễ hình dung, bạn có thể hiểu danh sách liên kết trong C có chức năng khá giống với một mảng. Tuy nhiên vẫn có những điểm khác biệt 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 ưu thế)	Kích thước được cố định mọi lúc Trong khi khai báo cần chỉ rõ kích thước	Kích thước thay đổi liên tục trong quá trình thêm, bớt phân tử. Kích thước tối đa chỉ phụ thuộc 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ớ được cấp theo chế độ trong quá trình biên dịch.	Động: Bộ nhớ được cấp theo chế độ trong quá trình khởi chạy.
Thứ tự và cách sắp xếp (Danh sách liên kết chiếm ưu thế)	Được lưu lại trên một dãy các ô nhớ liền kề	Được lưu lại trên các ô nhớ bất kỳ
Truy cập (Mảng chiếm ưu thế)	Bằng cách sử dụng chỉ số mảng, cho phép truy cập đến một phần tử ngẫu nhiên: O(1)	Muốn truy cập đến phần tử ngẫu nhiên cần phải trải qua quá 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 bằng 2 ngôn ngữ tuyến tính và nhị phân	Chỉ có thể tìm kiếm bằng tuyến tính

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 dữ liệu di động hay còn có thể hình dung như một danh sách mà trong đó mỗi phần tử đều liên kết với phần tử đứng sau nó.

Single Linked List được dùng phổ biến với ngôn ngữ lập trình C++. Trong Linked List C++, mỗi phần tử được cấu tạo nên từ hai thành phần chính. Đó là thành phần dữ liệu và thành phần liên kết. Thành phần dữ liệu chịu trách nhiệm lưu trữ thông tin về bản thân phần tử đó. Còn thành phần liên kết sẽ giúp lưu địa chỉ của phần tử đứng sau phần tử chủ thể đó. Nếu phần tử đượ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 phần tử hoàn chỉnh được cấu thành từ data (dữ 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).

>>>Mời bạn tham khảo thêm: Sử dụng MongoDB như thế nào? Ưu nhược điểm khi sử dụng

Đặc điểm của danh sách liên kết đơn

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

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

Tính liên kết của phần tử đầu và phần tử đứ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 phần tử đầu tiên và phần tử cuối cùng là người 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í bất kỳ thì phải tiến hành duyệt từ đầu đến phần tử đó. Ngoài ra, trong danh sách liên kết đơn C++ cũng chỉ cho phép người dùng tìm kiếm tuyến tính duy nhất 1 phân tử.

Cách cài đặt 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 bao gồm 2 phần là thành phần liên kết và thành phần dữ liệu. Đối với thành phần dữ liệu, bạn có thể tự tạo lên dữ liệu theo ý muốn (class) hoặc sử dụng dữ 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 dữ liệu như sau:

struct Node

{

int data;

Node* next;

};

Để tạo thêm 1 node mới, ta sẽ tiến hành khởi tạo giá trị ban đầu và trả địa chỉ về cho 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 được tạo chưa thêm vào danh sách nên chưa liên kết với phần tử 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ẽ tiến hành 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à có thể quản lý đượ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ó phần tử nào cả. Vì thế ta sẽ gắn phần đầu và cuối tạm vào NULL.

void CreateList(LinkedList& l)

{

l.head = NULL;

l.tail = NULL;

}

>>> Xem thêm : Lập trình ứng dụng di động – Xu hướng nghề nghiệp tương lai

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

Thêm phần tử đầu

Đầu tiên ta cần xác định 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& l, Node* node)

{

if (l.head == NULL)

{

l.head = node;

l.tail = node;

}

else

{

node->next = l.head;

l.head = node;

}

}

Thêm phần tử đuôi

Tương tự như cách thêm phần tử đầu, ta cũng sẽ xác định 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& 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ẽ thực hiện theo các bước sau: trỏ p->next = q->next, sau đó q->next = p. Khi hoàn thành, 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 tiếp tục gán p 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 ở đầu

Đầu tiên, ta tiến hành 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 hiện theo những bước sau. Đầu tiên là gán lại head vào vị trí đằng sau phần tử cần xóa, nhớ phải lưu head lại. Sau đó mới tiến hành 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;         // Hủy node head đi

if (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& l, Node* q, int& 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 chỉnh 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ó dữ liệu của node này. Tiếp tục thực hiện thao tác đó cho đến node NULL, đó chính tail của danh sách.

>>Mời bạn đọc tham khảo thêm: Lập trình web là làm gì? Những công việc của 1 lập trình viên

Vậy trong bài viết vừa rồi, Teky đã giúp bạn tìm hiểu thêm về các đặc điểm của danh sách liên kết đơn cũng như cách tạo một danh sách hoàn chỉnh. Mong rằng những kiến thức này sẽ giúp ích cho quá trình học tập và làm việc của bạn.

Học lập trình, công nghệ tại Teky – thông tin cần biết

TEKY là Học viện sáng tạo công nghệ với chương trình giảng dạy STEAM (Science – Technology – 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 vào tháng 6 năm 2016, TEKY quyết tâm thực hiện sứ mệnh mang đến cho thế hệ trẻ Việt Nam kiến thức toàn diện về STEAM, đặc biệt là các tư duy công nghệ, khoa học máy tính và kỹ năng thế kỷ 21 – 4Cs (Critical Thinking: Tư duy phản biện – Communication: Giao tiếp – Creativity: Sáng tạo – Collaboration: Làm việc nhóm).

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

•  Học tư duy phản biện thông qua việc phân tích các vấn đề.
•  Học tính sáng tạo tư duy Logic thông qua việc lắp đặt và lập trình robot th ông qua các mô hình Lego Mindstorm, app trò chơi. Giúp con học giỏi môn Toán trên lớp
•  Kỹ năng hợp tác thông qua các trò chơi team-building, các dự án nhóm trên lớp.
•  Phát huy khả năng giao tiếp hiệu quả bằng nhiều bài tập và hoạt động hấp dẫn.

Các bộ môn giảng dạy tại Teky gồm: Lập trình và phát triển ứng dụng, lập trình game, lập trình web với python  Lập trình Scratch Robotics Engineering, Công nghệ 3D và MultiMedia. Chúng tôi tin rằng trẻ em Việt Nam có cơ hội phát triển mạnh mẽ trong một nền kinh tế số và cần được trang bị sẵn sàng để trở thành những doanh nhân công nghệ trong tương lai.

Liên hệ ngay học viện công nghệ sáng tạo TEKY để được tư vấn khóa học:

• Cam kêt 7 tuổi có thể lập trình
• Top 10 dự án giáo dục có tầm ảnh hưởng nhất Đông Nam Á 2017 & 2018
• Top 3 Dự án xuất sắc 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

Website https://teky.edu.vn | Email: support@teky.edu.vn |