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

Chúng ta đã tìm hiểu về Linked list ở bài biết trước. Chúng ta đã biết cấu trúc của một danh sách kết như thế nào rồi. Bây giờ, chúng ta sẽ đi tìm hiểu cách thêm một phần tử vào danh sách sẽ như thế nào nha.

Mình sẽ hướng dẫn 3 cách thêm chính trong danh sách liên kết

1. Thêm vào đầu danh sách liên kết
2. Thêm vào cuối danh sách liên kết
3. Thêm vào vị trí bất kỳ trong danh sách liên kết

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

Để thêm một node vào đầu danh sách liên kết, ta có 3 bước chính.

/**
     * Insert to head of Linked list
     * @Param: T data
     */
    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.setNext(this.head);
        this.head = newNode;
    }

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

Để thêm một node mới vào cuối danh sách liên kết, ta có 3 bước chính

/**
     * Insert to end of Linked list
     * @Param: T data
     */

    public void addEnd(T data) {
        Node<T> newNode = new Node<>(data);
        // If the Linked list is empty, newNode will be head node
        if (this.head == null) {
            this.head = newNode;
            return;
        }

        // Go to the last node
        Node<T> last = this.head;
        while (last.getNext() != null) {
            last = last.getNext();
        }

        // Append newNode to end the linked list
        last.setNext(newNode);
    }

Thêm node vào vị trí bất kỳ trong danh sách liên kết

Để thêm một node vào một vị trí bất kỳ, điều kiện đầu tiên là 0 <= pos < size, với size là tổng số lượng phần tử trong danh sách liên kết.

Trường hợp pos = 0, thì chúng ta sẽ quay về lại trường hợp thêm node vào đầu danh sách liên kết.

Chúng ta có các bước làm chính như sau

/**
  * Insert newNode to a posotion in linked list
  * @Param: T data, int pos
  */
public void addPos(T data, int pos) {
        if (pos < 0) {
            return;
        }

        // If pos is zero, It's add to first
        if (pos == 0) {
            this.addFirst(data);
            return;
        }

        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;
        }

        // insert newNode to pos

        Node<T> newNode = new Node<>(data);
        newNode.setNext(cur.getNext());
        cur.setNext(newNode);
}

Link full source code linked list: LinkedList