Xoá phần tử trong danh sách liên kết

Ở bài viết này chúng ta sẽ cùng nhau bàn luận về các hàm xoá phần tử trong danh sách liên kết. Mình xin trình bày một số function xoá phần tử trong danh sách liên kết mà mình nghĩ là nó cần thiết.

1. Xoá phần tử đầu danh sách liên kết
2. Xoá phần tử cuối danh sách
3. Xoá phần tử tại vị trí bất kỳ 
4. Xoá phần tử dựa vào khoá(Data)

Xoá phần tử trong danh sách liên kết

Xoá phần tử đầu tiên trong danh sách liên kết, chỉ đơn giản là dời biến head qua phần tử tiếp theo của head trỏ đến.

/**
 * Remove element the first at the top of Linked list
 */

public void removeHead() {
    this.head = this.head.getNext();
}

Xoá phần tử cuối danh sách liên kết

Để xoá phần tử cuối cùng của danh sách liên kết, mình sẽ tìm đến phần tử kế cận phần tử cuối cùng và lấy con trỏ trỏ về null. Như vậy phần tử kế cận này sẽ trở thành phần tử cuối cùng của danh sách liên kết.

/**
 * Remove element the first at the top of Linked list
 */

public void removeLast() {
    if (this.head == null)
        return;

    if (this.head.getNext() == null)
        removeHead();

    Node<T> preLast = this.head;
    while (preLast.getNext().getNext() != null) {
        preLast = preLast.getNext();
    }
    preLast.setNext(null);
 }

Xoá phần tử tại vị trí bất kỳ trong danh sách liên kết

Đến xoá một phần tử tại vị trí X pos, chúng ta sẽ tìm đến phần tử pre_delete tại vị trí pos – 1, Gán pre_delete->Next = pre_delete->Next -> Next

/**
 * Remove element in linked list by pos
 * @Param int pos
 */

public boolean removePos(int pos) {
    if (pos < 0) {
        return false;
    }

    if (pos == 0) {
        this.removeHead();
    }

    int i = 0;
    Node<T> cur = this.head;
    while (i < pos - 1 && cur != null) {
        i++;
        cur = cur.getNext();
    }

    // pos is outIndex of linked list
    if (i != pos - 1) {
        return false;
    }

    cur.setNext(cur.getNext().getNext());
    return true;
}

Xoá phần tử dựa vào key(data)

Xoá phần tử đầu tiên có key bằng với key cần xoá

VD: 1 -> 3 -> 2 -> -1 -> 2 -> 5 -> 3 Xoá phần tử có key  = 3 Output: 1 -> 2 -> -1 -> 2 -> 5 -> 3

 

Để xoá phần tử đầu tiên có key giống với key cần xoá, Chúng ta sẽ tìm đến phần tử kế cận nó là pre_delete và thực hiện pre_delete-> Next = pre_delete-> Next -> Next

/**
 * Remove element in linked list by key in the first meeting
 * @Param T key
 */

public boolean removeAtFirst(T key) {
    if (this.head.getData().equals(key)) {
        this.removeHead();
        return true;
    }

    Node<T> cur = this.head;
    while (cur.getNext() != null && !cur.getNext().getData().equals(key)) {
        cur = cur.getNext();
    }
    if (cur.getNext() == null)
        return false;

    cur.setNext(cur.getNext().getNext());
    return true;
}

Xoá phần tử cuối cùng có key bằng với key cần xoá

VD: 1 -> 3 -> 2 -> -1 -> 2 -> 5 -> 3 Xoá phần tử có key  = 3 Output: 1 -> 3 -> 2 -> -1 -> 2 -> 5

 

B1: Duyệt danh sách liên kết, với mỗi node cur       (a) Nếu cur->Next.data = key            – Nếu đoạn cur-> Next -> Next đến node cuối cùng không có node  nào có data bằng key cần xoá thì Xoá node cur->Next          – Ngược lại cur = cur – > Next

 

Hàm isUniqueInRange dùng để kiểm tra xem những phần tử còn lại trong danh sách liên kết có chứa key cần xoá hay không

private boolean isUniqueInRange(Node<T> cur, T data) {
        if (cur == null)
            return false;
        while (cur.getNext() != null) {
            if (cur.getNext().getData().equals(data))
                return true;
            cur = cur.getNext();
        }
        return false;
    }

/**
 * Remove element in linked list by key in the last meeting
 * @Param T key
 */

public boolean removeAtLast(T key) {
    if (this.head.getData().equals(key) && !this.isUniqueInRange(this.head, key)){
        this.removeHead();
        return true;
    }

    Node<T> cur = this.head;
    while (cur.getNext() != null && !cur.getNext().getData().equals(key) || this.isUniqueInRange(cur.getNext(), key))  {
        cur = cur.getNext();
    }

    if (cur.getNext() == null)
        return false;

    cur.setNext(cur.getNext().getNext());
    return true;
}

Link full source code: LinkedList