[CTDL] - Danh Sách Liên Kết đơn - Linked List - Phần 1. Giới Thiệu

🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, bài này chúng ta sẽ tìm hiểu về Linked List(danh sách liên kết đơn) trong series tự học về cấu trúc dữ liệu và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Giống như kiểu dữ liệu array (mảng), Linked List là một cấu trúc dữ liệu tuyến tính. Tuy nhiên khác với array, các phần tử của linked list không được lưu trữ tại các vị trí ô nhớ liền kề nhau, mà các phần tử của linked list sẽ được liên kết với nhau bằng cách sử dụng các con trỏ.

1. Tại sao lại là Linked List?

Array (mảng) có thể được sử dụng để lưu trữ dữ liệu thuộc cùng một kiểu dữ liệu, một cách tuyến tính. Nhưng array tồn tại các hạn chế sau:

1. Kích thước của các arrays là cố định: Vì vậy chúng ta sẽ phải biết trước giới hạn trên (upper limit) về số phần tử. Ngoài ra, chúng ta cũng phải cấp phát số lượng ô nhớ bằng với giới hạn trên về số phần tử, bất kể ta có sử dụng hết số ô nhớ đó hay không.

2. Việc chèn thêm một phần tử mới vào một mảng tốn khá nhiều công đoạn, vì chúng ta sẽ phải tạo chỗ chứa cho phần tử mới, và để tạo ra chỗ chứa này thì các phần tử hiện tại trong mảng sẽ phải được dịch chuyển (dịch sang trái, hoặc dịch sang phải tùy trường hợp).

Ví dụ, trong một hệ thống, nếu chúng ta duy trì một danh sách đã được sắp xếp các IDs bên trong một mảng tên là id[].:

id[] = [1000, 1010, 1050, 2000, 2040].

Và nếu chúng ta muốn chèn thêm một ID là 1005 vào mảng id[], vậy thì, để duy trì được thứ tự đã được sắp xếp của mảng, chúng ta sẽ phải dịch chuyển tất cả các phần tử nằm sau 1000 (ngoại trừ 1000) sang phải.

Việc xóa bỏ phần tử khỏi mảng cũng khá mất công, trừ khi sử dụng một số kỹ thuật đặc biệt. Ví dụ, để xóa 1010 khỏi mảng id[], thì mọi phần tử nằm sau 1010 sẽ phải được dịch chuyển sang trái.

2. Ưu điểm của Linked List so với Array

1. Linked List có kích thước động

2. Dễ dàng chèn thêm phần tử vào mảng, và xóa phần tử khỏi mảng.

3. Hạn chế của Linked List

1. Không thể thực hiện truy cập ngẫu nhiên (random access). Chúng ta phải truy cập đến các phần tử của Linked List một cách tuần tự, bắt đầu từ node đầu tiên. Vì vậy chúng ta sẽ không thể thực hiện tìm kiếm nhị phân (binary search) với Linked List một cách hiệu quả, đối với dạng cài đặt mặc định của Linked List.

2. Mỗi phần tử của Linked List đều chứa một con trỏ (pointer) và cần phải cấp phát bộ nhớ (ô nhớ) cho các con trỏ này.

3. Linked List không thân thiện với bộ nhớ cache. Bởi vì các phần tử trong Array được bố trí nằm liền kề, liên tiếp nhau, nên chúng ta có thể dễ dàng truy cập đến các phần tử của Array thông qua các vị trí tham chiếu được thể hiện bằng các chữ số, trong khi đó điều này là không thể đối với Linked List.

4. Mô tả

Một Linked List (danh sách liên kết) sẽ được biểu diễn bởi một con trỏ (pointer) trỏ đến node đầu tiên của Linked List đó. Node đầu tiên của Linked List được gọi là node head. Nếu Linked List là trống, giá trị của node head sẽ là NULL.

Mỗi node ở bên trong một Linked List sẽ bao gồm ít nhất hai thành phần sau:

1. data (dữ liệu, có thể là kiểu số, kiểu ký tự, …)

2. pointer (con trỏ) hoặc có thể hiểu là reference (tham chiếu) tới node tiếp theo trong Linked List.

Trong ngôn ngữ lập trình C, chúng ta có thể biểu diễn một node bằng cách sử dụng kiểu dữ liệu struct. Dưới đây là ví dụ về một node có kiểu dữ liệu integer của một Linked List.

Trong Java hoặc C#, Linked List có thể được biểu diễn dưới dạng một class và một Node có thể được biểu diễn thành một class khác nữa. class LinkedList chứa một reference (tham chiếu) thuộc kiểu dữ liệu class Node.

Code C

// A linked list node struct Node { int data; struct Node* next; };

Code C++

class Node { public: int data; Node* next; };

Code Java

class LinkedList { Node head; // head of the list /* Linked list Node*/ class Node { int data; Node next; // Constructor to create a new node // Next is by default initialized // as null Node(int d) { data = d; } } }

Code Python

# Node class class Node: # Function to initialize the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize # next as null # Linked List class class LinkedList: # Function to initialize the Linked # List object def __init__(self): self.head = None

Code C#

brightness_4 class LinkedList { // The first node(head) of the linked list // Will be an object of type Node (null by default) Node head; class Node { int data; Node next; // Constructor to create a new node Node(int d) { data = d; } } }

Trong ví dụ dưới đây, chúng ta sẽ tạo ra một linked list đơn giản với 3 nodes:

Code C

// A simple C program to introduce // a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; // Program to create a simple linked // list with 3 nodes int main() { struct Node* head = NULL; struct Node* second = NULL; struct Node* third = NULL; // allocate 3 nodes in the heap head = (struct Node*)malloc(sizeof(struct Node)); second = (struct Node*)malloc(sizeof(struct Node)); third = (struct Node*)malloc(sizeof(struct Node)); /* Three blocks have been allocated dynamically. We have pointers to these three blocks as head, second and third head second third | | | | | | +---+-----+ +----+----+ +----+----+ | # | # | | # | # | | # | # | +---+-----+ +----+----+ +----+----+ # represents any random value. Data is random because we haven’t assigned anything yet */ head->data = 1; // assign data in first node head->next = second; // Link first node with // the second node /* data has been assigned to the data part of the first block (block pointed by the head). And next pointer of first block points to second. So they both are linked. head second third | | | | | | +---+---+ +----+----+ +-----+----+ | 1 | o----->| # | # | | # | # | +---+---+ +----+----+ +-----+----+ */ // assign data to second node second->data = 2; // Link second node with the third node second->next = third; /* data has been assigned to the data part of the second block (block pointed by second). And next pointer of the second block points to the third block. So all three blocks are linked. head second third | | | | | | +---+---+ +---+---+ +----+----+ | 1 | o----->| 2 | o-----> | # | # | +---+---+ +---+---+ +----+----+ */ third->data = 3; // assign data to third node third->next = NULL; /* data has been assigned to data part of third block (block pointed by third). And next pointer of the third block is made NULL to indicate that the linked list is terminated here. We have the linked list ready. head | | +---+---+ +---+---+ +----+------+ | 1 | o----->| 2 | o-----> | 3 | NULL | +---+---+ +---+---+ +----+------+ Note that only head is sufficient to represent the whole list. We can traverse the complete list by following next pointers. */ return 0; }

Code C++

// A simple CPP program to introduce // a linked list #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; // Program to create a simple linked // list with 3 nodes int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // allocate 3 nodes in the heap head = new Node(); second = new Node(); third = new Node(); /* Three blocks have been allocated dynamically. We have pointers to these three blocks as head, second and third head second third | | | | | | +---+-----+ +----+----+ +----+----+ | # | # | | # | # | | # | # | +---+-----+ +----+----+ +----+----+ # represents any random value. Data is random because we haven’t assigned anything yet */ head->data = 1; // assign data in first node head->next = second; // Link first node with // the second node /* data has been assigned to the data part of first block (block pointed by the head). And next pointer of the first block points to second. So they both are linked. head second third | | | | | | +---+---+ +----+----+ +-----+----+ | 1 | o----->| # | # | | # | # | +---+---+ +----+----+ +-----+----+ */ // assign data to second node second->data = 2; // Link second node with the third node second->next = third; /* data has been assigned to the data part of the second block (block pointed by second). And next pointer of the second block points to the third block. So all three blocks are linked. head second third | | | | | | +---+---+ +---+---+ +----+----+ | 1 | o----->| 2 | o-----> | # | # | +---+---+ +---+---+ +----+----+ */ third->data = 3; // assign data to third node third->next = NULL; /* data has been assigned to the data part of the third block (block pointed by third). And next pointer of the third block is made NULL to indicate that the linked list is terminated here. We have the linked list ready. head | | +---+---+ +---+---+ +----+------+ | 1 | o----->| 2 | o-----> | 3 | NULL | +---+---+ +---+---+ +----+------+ Note that only the head is sufficient to represent the whole list. We can traverse the complete list by following the next pointers. */ return 0; } // This code is contributed by rathbhupendra

Code Java

// A simple Java program to introduce a linked list class LinkedList { Node head; // head of list /* Linked list Node. This inner class is made static so that main() can access it */ static class Node { int data; Node next; Node(int d) { data = d; next = null; } // Constructor } /* method to create a simple linked list with 3 nodes*/ public static void main(String[] args) { /* Start with the empty list. */ LinkedList llist = new LinkedList(); llist.head = new Node(1); Node second = new Node(2); Node third = new Node(3); /* Three nodes have been allocated dynamically. We have references to these three blocks as head, second and third llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | null | | 2 | null | | 3 | null | +----+------+ +----+------+ +----+------+ */ llist.head.next = second; // Link first node with the second node /* Now next of the first Node refers to the second. So they both are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | null | | 3 | null | +----+------+ +----+------+ +----+------+ */ second.next = third; // Link second node with the third node /* Now next of the second Node refers to third. So all three nodes are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | o-------->| 3 | null | +----+------+ +----+------+ +----+------+ */ } }

Code Python

# A simple Python program to introduce a linked list # Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__(self): self.head = None # Code execution starts here if __name__=='__main__': # Start with the empty list llist = LinkedList() llist.head = Node(1) second = Node(2) third = Node(3) ''' Three nodes have been created. We have references to these three blocks as head, second and third llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | None | | 2 | None | | 3 | None | +----+------+ +----+------+ +----+------+ ''' llist.head.next = second; # Link first node with second ''' Now next of first Node refers to second. So they both are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | null | | 3 | null | +----+------+ +----+------+ +----+------+ ''' second.next = third; # Link second node with the third node ''' Now next of second Node refers to third. So all three nodes are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | o-------->| 3 | null | +----+------+ +----+------+ +----+------+ '''

Code C#

// A simple C# program to introduce a linked list using System; public class LinkedList { Node head; // head of list /* Linked list Node. This inner class is made static so that main() can access it */ public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } // Constructor } /* method to create a simple linked list with 3 nodes*/ public static void Main(String[] args) { /* Start with the empty list. */ LinkedList llist = new LinkedList(); llist.head = new Node(1); Node second = new Node(2); Node third = new Node(3); /* Three nodes have been allocated dynamically. We have references to these three blocks as head, second and third llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | null | | 2 | null | | 3 | null | +----+------+ +----+------+ +----+------+ */ llist.head.next = second; // Link first node with the second node /* Now next of first Node refers to second. So they both are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | null | | 3 | null | +----+------+ +----+------+ +----+------+ */ second.next = third; // Link second node with the third node /* Now next of the second Node refers to third. So all three nodes are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | o-------->| 3 | null | +----+------+ +----+------+ +----+------+ */ } }

5. Duyệt Linked List

Ở ví dụ trước, chúng ta đã tạo ra một linked list đơn giản gồm 3 nodes. Tiếp theo, chúng ta sẽ duyệt qua linked list này và in ra phần data (dữ liệu) của từng node. Để duyệt linked list, ta sẽ viết một hàm tên là printList(), hàm này sẽ in ra mọi linked list được truyền vào làm tham số cho nó. Ví dụ:

Code C

// A simple C program for traversal of a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; // This function prints contents of linked list starting from // the given node void printList(struct Node* n) { while (n != NULL) { printf(" %d ", n->data); n = n->next; } } int main() { struct Node* head = NULL; struct Node* second = NULL; struct Node* third = NULL; // allocate 3 nodes in the heap head = (struct Node*)malloc(sizeof(struct Node)); second = (struct Node*)malloc(sizeof(struct Node)); third = (struct Node*)malloc(sizeof(struct Node)); head->data = 1; // assign data in first node head->next = second; // Link first node with second second->data = 2; // assign data to second node second->next = third; third->data = 3; // assign data to third node third->next = NULL; printList(head); return 0; }

Code C++

// A simple C++ program for traversal of a linked list #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; // This function prints contents of linked list // starting from the given node void printList(Node* n) { while (n != NULL) { cout << n->data << " "; n = n->next; } } // Driver code int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // allocate 3 nodes in the heap head = new Node(); second = new Node(); third = new Node(); head->data = 1; // assign data in first node head->next = second; // Link first node with second second->data = 2; // assign data to second node second->next = third; third->data = 3; // assign data to third node third->next = NULL; printList(head); return 0; }

Code Java

// A simple Java program for traversal of a linked list class LinkedList { Node head; // head of list /* Linked list Node. This inner class is made static so that main() can access it */ static class Node { int data; Node next; Node(int d) { data = d; next = null; } // Constructor } /* This function prints contents of linked list starting from head */ public void printList() { Node n = head; while (n != null) { System.out.print(n.data + " "); n = n.next; } } /* method to create a simple linked list with 3 nodes*/ public static void main(String[] args) { /* Start with the empty list. */ LinkedList llist = new LinkedList(); llist.head = new Node(1); Node second = new Node(2); Node third = new Node(3); llist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node llist.printList(); } }

Python 3

# A simple Python program for traversal of a linked list # Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__(self): self.head = None # This function prints contents of linked list # starting from head def printList(self): temp = self.head while (temp): print (temp.data) temp = temp.next # Code execution starts here if __name__=='__main__': # Start with the empty list llist = LinkedList() llist.head = Node(1) second = Node(2) third = Node(3) llist.head.next = second; # Link first node with second second.next = third; # Link second node with the third node llist.printList()

Code C#

// A simple C# program for traversal of a linked list using System; public class LinkedList { Node head; // head of list /* Linked list Node. This inner class is made static so that main() can access it */ public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } // Constructor } /* This function prints contents of linked list starting from head */ public void printList() { Node n = head; while (n != null) { Console.Write(n.data + " "); n = n.next; } } /* method to create a simple linked list with 3 nodes*/ public static void Main(String[] args) { /* Start with the empty list. */ LinkedList llist = new LinkedList(); llist.head = new Node(1); Node second = new Node(2); Node third = new Node(3); llist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node llist.printList(); } }

Kết quả in ra là:

1 2 3

Nguồn và Tài liệu tiếng anh tham khảo:

• w3schools
• Geeksforgeeks
• codechef
• dev.to

Tài liệu từ cafedev:

• Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
• Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
• Các series tự học lập trình khác

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!