Triển khai LinkedList bằng Java

Giới thiệu

Linked List (Danh sách được liên kết) là một cấu trúc dữ liệu bao gồm một chuỗi các phần tử, trong đó mỗi phần tử được gọi là một nút và mỗi nút có hai trường: trường dữ liệu lưu trữ phần tử và trường liên kết lưu trữ địa chỉ của nút tiếp theo . Nút đầu tiên được gọi là đầu head và nút cuối cùng được gọi là đuôi tail và trường liên kết của đuôi trỏ đến null.

Một Linked List khi triển khai thủ công trong Java sẽ gồm có 2 class là Node và LinkedList. Chú ý class Node chỉ lưu giá trị kiểu int, rất phổ biến trong các bài LeetCode trong thực tế thì sẽ đa dạng hơn rất nhiều.

Thực tế bạn có thể dùng sẵn class LinkedList trong package java.util. Class này được thiết kế để chấp nhận bất kỳ kiểu giá trị mà Node sẽ lưu trữ.

Node

Khai báo Node lưu giá trị kiểu int

public class Node {
  int val;
  Node next;

  Node(int val) {  //Constructor chỉ khởi tạo giá trị val
    this.val = val;
  }

  Node(int val, Node next) {  //Constructor khởi tạo giá trị và biến 
    this.val = val;
    this.next = next;
  }
}
java

Khai báo Node lưu kiểu bất kỳ sử dụng generic type `<T>`

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

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

LinkedList

public class LinkedList {
  Node head;
  public LinkedList(Node head) {
    this.head = head;
  }
}
java

Các thao tác lên LinkedList

Hầu hết các thao tác lên LinkedList đều là duyệt tuần tự từ phần tử đầu tiên head đến cuối. Độ phức tạp thuật toán là $O (n)$

1. Thêm một phần tử vào Linked List

Duyệt qua danh sách cho đến khi tìm thấy nút cuối cùng, sau đó tạo một nút mới với dữ liệu mong muốn và đặt trường tiếp theo của nó thành null

public void append(int data) {
     Node newNode = new Node(data);
     if (head == null) { // if the list is empty, set the new node as the head
         head = newNode;
         return;
     }
     Node current = head;
     while (current.next != null) { // traverse the list until the last node
         current = current.next;
     }
     current.next = newNode; // set the new node as the next node of the last node
}
java

2. Đếm số phần tử trong LinkedList

Cách đơn giản nhất là duyệt từ phần tử head cho đến phần tử cuối cùng (trước null), rồi tăng dần biến count. Cách này không nhanh, nhưng luôn đúng.

Cách thứ 2 nhanh hơn nhưng phức tạp hơn là luôn lưu biến thuộc tính trong LinkedList, rồi tăng hay giảm tuỳ theo tháo tác lên LinkedList.

public int size() {
     int count = 0;
     Node current = head;
     while (current != null) {
         count++;
         current = current.next;
     }
     return count;
}
java

3. Xoá một phần tử trong LinkedList

Có 3 kiểu xoá phần tử trong LinkedList

Xoá 1 phần tử đầu tiên chứa giá trị val bằng với tham số đầu vào
Xoá tất cả các phần tử có chứa giá trị val bằng với tham số đầu vào
Xoá phần tử là chính phần tử truyền trong tham số đầu vào

Ví dụ này chỉ minh hoạ cho kiểu số 1

public void remove(int data) {
     if (head == null) {
         return;
     }
     
     if (head.data == data) {
         head = head.next;
         return;
     }
     // Duyệt để xoá
     Node current = head;
     while (current.next != null) {
         if (current.next.data == data) {
             current.next = current.next.next;
             return;
         }
         current = current.next;
     }
}
java

4. Chuyển một LinkedList ra String

public String toString() {
  StringBuilder sb = new StringBuilder();
  Node current = head;
  while (current != null) {
      sb.append(current.data);
      sb.append(" - ");
      current = current.next;
  }
  return sb.toString();
}
java

Kết quả xuất ra chuỗi sẽ có dạng "1 - 4 - 3 - 12 - 5 - 8 - "
Hãy nghĩ cách để loại dấu " - " ở phần tử cuối cùng.

5. Chèn một phần tử đồng thời sắp xếp LinkedList

Khi chèn một phần tử đồng thời sắp xếp tăng dần theo giá trị data trong Node

public void insertSorted(int data) {
     Node newNode = new Node(data);
     if (head == null || head.data >= newNode.data) {
         newNode.next = head;
         head = newNode;
         return;
     }
     Node current = head;
     while (current.next != null && current.next.data < newNode.data) {
         current = current.next;
     }
     newNode.next = current.next;
     current.next = newNode;
}
java

6. Tìm kiếm một phần tử

Nếu tìm thấy thì trả về phần tử, không tìm thấy trả về null

public Node search(int data) {
  Node current = head;
  while (current != null) {
      if (current.data == data) {
          return current;
      }
      current = current.next;
  }
  return null;
}
java

7. Kiểm tra một phần tử có trong LinkedList không?

public boolean contains(int data) {
  Node current = head;
  while (current != null) {
      if (current.data == data) {
          return true;
      }
      current = current.next;
  }
  return false;
}
java

8. Xoá phần tử có giá trị lặp lại trong LinkedList

Sử dụng HashSet để lưu các phần tử lần đầu xuất hiện, nếu phần tử current đó lặp lai (có giá trị trùng với phần tử trong HashSet), thì chỉnh lại biến previous trước đây trỏ vào current nay bỏ qua trỏ thẳng sang current.next

public void removeDuplicates() {
  HashSet<Integer> set = new HashSet<>();
  Node current = head;
  Node previous = null;
  while (current != null) {
      if (set.contains(current.data)) {
          previous.next = current.next;
      } else {
          set.add(current.data);
          previous = current;
      }
      current = current.next;
  }
}
java