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ỏ.

Mô hình một danh sách liên kết

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:

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!

Bạn thấy chất lượng bài viết này tốt không?

Thả 1->5 ❤️ để đánh giá chất lượng bài viết.

Xếp hạng 1 / 5. Số lượng đánh giá 1

Hãy đánh giá để ủng hộ và giúp chúng tôi cải thiện bài viết tốt hơn cho bạn!

Chúng tôi xin lỗi vì bài viết chưa được chất lượng. Chúng tôi sẽ cải thiện nó sớm nhất!

Hãy gửi phản hồi của bạn cho chúng tôi

Tại sao bài viết này lại không chất lượng?

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