Chương trình Java triển khai LinkedList

Trong bài viết này, chúng ta sẽ hiểu cách triển khai LinkedList. Lớp java.util.LinkedList thực hiện các thao tác như mong đợi cho danh sách liên kết kép (doubly-linked list). Các thao tác truy xuất theo chỉ số sẽ duyệt list từ đầu hoặc cuối, tùy phía gần chỉ số chỉ định hơn.

Minh họa dưới đây:

Giả sử đầu vào là:

Run the program

Đầu ra mong muốn:

The elements of the linked list are: 100 150 200 250

Thuật toán

Bước 1 - BẮT ĐẦU 
Bước 2 - Tạo class với các thành viên cần thiết 
Bước 3 - Định nghĩa hàm 'insert' thêm phần tử vào list 
Bước 4 - Trong 'main', tạo instance mới của class 
Bước 5 - Tạo list, thêm phần tử bằng 'insert' 
Bước 6 - Duyệt list, hiển thị giá trị node hiện tại 
Bước 7 - Chuyển sang node tiếp theo, lặp lại 
Bước 8 - Làm đến khi hết list 
Bước 9 - Hiển thị kết quả 
Bước 10 - DỪNG

Ví dụ 1

Gom thao tác dưới 'main'.

public class Demo { 
    Node head; 
    static class Node { 
        int data; 
        Node next_element; 
        Node(int element){ 
            data = element; 
            next_element = null; 
        } 
    } 
    
    public static Demo insert(Demo input_list, int data){ 
        Node new_node = new Node(data); 
        new_node.next_element = null; 
        if (input_list.head == null) { 
            input_list.head = new_node; 
        } else { 
            Node last = input_list.head; 
            while (last.next_element != null) { 
                last = last.next_element; 
            } 
            last.next_element = new_node; 
        } 
        return input_list; 
    } 
    
    public static void main(String[] args){ 
        Demo input_list = new Demo(); 
        System.out.print("A linked list is declared: \n"); 
        input_list = insert(input_list, 100); 
        input_list = insert(input_list, 150); 
        input_list = insert(input_list, 200); 
        input_list = insert(input_list, 250); 
        Node current_node = input_list.head; 
        System.out.print("The elements of the linked list are: \n"); 
        while (current_node != null) { 
            System.out.print(current_node.data + " "); 
            current_node = current_node.next_element; 
        } 
    } 
}

Kết quả

A linked list is declared: 
The elements of the linked list are: 100 150 200 250

Ví dụ 2

Đóng gói thao tác vào hàm thể hiện lập trình hướng đối tượng.

public class Demo { 
    Node head; 
    static class Node { 
        int data; 
        Node next_element; 
        Node(int element){ 
            data = element; 
            next_element = null; 
        } 
    } 
    
    public static Demo insert(Demo input_list, int data){ 
        Node new_node = new Node(data); 
        new_node.next_element = null; 
        if (input_list.head == null) { 
            input_list.head = new_node; 
        } else { 
            Node last = input_list.head; 
            while (last.next_element != null) { 
                last = last.next_element; 
            } 
            last.next_element = new_node; 
        } 
        return input_list; 
    } 
    
    public static void print_list(Demo input_list){ 
        Node current_node = input_list.head; 
        System.out.print("The elements of the linked list are: \n"); 
        while (current_node != null) { 
            System.out.print(current_node.data + " "); 
            current_node = current_node.next_element; 
        } 
    } 
    
    public static void main(String[] args){ 
        Demo input_list = new Demo(); 
        System.out.print("A linked list is declared: \n"); 
        input_list = insert(input_list, 100); 
        input_list = insert(input_list, 150); 
        input_list = insert(input_list, 200); 
        input_list = insert(input_list, 250); 
        print_list(input_list); 
    } 
}

Kết quả

A linked list is declared: 
The elements of the linked list are: 100 150 200 250