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ỏ.
Nội dung chính
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:
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:
Chào thân ái và quyết thắng!
 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){kind=link}