Bài 2.2. Thêm node và duyệt danh sách liên kết đơn

Nội dung bài học

1. Tạo danh sách liên kết đơn
2. Thêm vào đầu danh sách liên kết
3. Thêm vào cuối danh sách liên kết
4. Thêm vào sau node có giá trị x
5. Duyệt danh sách liên kết đơn
6. Ví dụ minh họa
7. Bài tập thực hành

Video lý thuyết

Video minh họa

Tạo danh sách liên kết đơn

• Tạo node: inner class tên là Node chứa thuộc tính data, một node next
• Tạo linked list: outer class đặt tên LinkedList chứa một node head và một node tail

public class LinkedList<T> {
    private Node<T> head;
    private Node<T> tail;

    static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
}

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

• Giả sử ta muốn chèn node p vào đầu danh sách liên kết. Các bước thực hiện:
  • Kiểm tra xem node head có null hay không, nếu null ta gán luôn head và tail là p
  • Nếu head khác null:
    B1: gán head cho p.next: p.next = head;
    B2: gán lại head bằng p: head = p;

public void insertHead(T data) {
    Node<T> p = new Node<>(data);
    if(head == null) {
        head = tail = p;
    } else {
        p.next = head;
        head = p;
    }
}

Thêm vào cuối danh sách liên kết

• Giả sử ta muốn thêm node p vào cuối danh sách liên kết hiện tại. Các bước thực hiện:
  • Kiểm tra xem head có null hay không. Nếu null ta gán p cho head và tail
  • Nếu head không null, ta thực hiện:
    B1: gán p cho tail.next: tail.next = p;
    B2: gán lại tail: tail = p;

public void insertTail(T data) {
    Node<T> p = new Node<>(data);
    if(head == null) {
        head = tail = p;
    } else {
        tail.next = p;
        tail = p;
    }
}

Thêm vào sau node có giá trị x

• Giả sử ta muốn thêm node p sau node có giá trị C:
  • Tìm node chứa giá trị X == C, gọi là nodeX.
  • Nếu tìm thấy và nodeX là node cuối: gọi phương thức chèn vào đầu danh sách.
  • Nếu tìm thấy và nodeX không phải node cuối danh sách:
    B1: gán nodeX.next cho p.next: p.next = nodeX.next;
    B2: gán p cho nodeX.next: nodeX.next = p;
  • Nếu không tìm thấy ta thông báo ra màn hình và kết thúc.

public void insertAfterX(T data, T x) {
    Node<T> nodeX = head;
    while (nodeX != null) {
        if(nodeX.data == x) {
            break;
        }
        nodeX = nodeX.next;
    }
    if(nodeX != null) { // tìm thấy node x
        if(nodeX.equals(tail)) {
            insertTail(data);
        } else {
            Node<T> p = new Node<>(data);
            p.next = nodeX.next;
            nodeX.next = p;
        }
    } else {
        System.out.println("Không tìm thấy node mục tiêu.");
    }
}

Duyệt danh sách liên kết đơn

• Các bước thực hiện:
  • Khai báo node p và khởi tạo bằng head: p = head;
  • Lặp chừng nào p còn khác null:
    B1: xuất ra giá trị của p: xuất p.data;
    B2: cập nhật p: p = p.next;

public void showList() {
    for (var node = head; node != null; node = node.next) {
        System.out.print(node.data + " -> ");
    }
}

Ví dụ minh họa

// file LinkedList.java

public class LinkedList<T> {
    private Node<T> head;
    private Node<T> tail;

    static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    public void insertHead(T data) {
        Node<T> p = new Node<>(data);
        if(head == null) {
            head = tail = p;
        } else {
            p.next = head;
            head = p;
        }
    }

    public void insertTail(T data) {
        Node<T> p = new Node<>(data);
        if(head == null) {
            head = tail = p;
        } else {
            tail.next = p;
            tail = p;
        }
    }

public void insertAfterX(T data, T x) {
    Node nodeX = head;
    while (nodeX != null) {
        if(nodeX.data == x) {
            break;
        }
        nodeX = nodeX.next;
    }
    if(nodeX != null) { // tìm thấy node x
        if(nodeX.equals(tail)) { // nếu node x là node cuối
            insertTail(data); // gọi chèn cuối dslk
        } else {
            Node p = new Node<>(data);
            p.next = nodeX.next;
            nodeX.next = p;
        }
    } else {
        System.out.println("Không tìm thấy node mục tiêu.");
    }
}

    public void showList() {
        for (var node = head; node != null; node = node.next) {
            System.out.print(node.data + " -> ");
        }
        System.out.println("NULL");
    }
}

// file Test.java

public class Test {
    public static void main(String[] args) {
        LinkedList<String> linkedListNames = new LinkedList<>();
        // them vao cuoi danh sach
        linkedListNames.insertTail("Hong");
        linkedListNames.insertTail("Nam");
        linkedListNames.insertTail("Huong");
        linkedListNames.insertTail("Hoa");
        linkedListNames.insertTail("Loan");
        linkedListNames.insertTail("Thang");
        // hien thi
        linkedListNames.showList();
        // them vao dau danh sach
        linkedListNames.insertHead("Thong");
        linkedListNames.insertHead("Quang");
        linkedListNames.showList();
        // them node sau node co gia tri "Nam"
        linkedListNames.insertAfterX("Khanh", "Nam");
        linkedListNames.showList();

        // dslk luu gia tri int
        LinkedList<Integer> linkedListNumbers = new LinkedList<>();
        linkedListNumbers.insertHead(1);
        linkedListNumbers.insertHead(2);
        linkedListNumbers.insertHead(3);
        linkedListNumbers.insertHead(50);
        linkedListNumbers.showList();
    }
}

// kết quả:
Hong -> Nam -> Huong -> Hoa -> Loan -> Thang -> NULL
Quang -> Thong -> Hong -> Nam -> Huong -> Hoa -> Loan -> Thang -> NULL
Quang -> Thong -> Hong -> Nam -> Khanh -> Huong -> Hoa -> Loan -> Thang -> NULL
50 -> 3 -> 2 -> 1 -> NULL

Bài tập thực hành

• Tải đề bài: nhấn vào đây
• Bài giải mẫu: nhấn vào đây