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.

B1: Khởi tạo new_node
B2: Lấy con trỏ của new_node trỏ đến phần tử đầu tiên trong danh sách liên kết
B3: Gán head = new_node

 

/**
     * 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

B1: Khởi tạo new_node
B2: Lấy con trỏ của phần tử cuối cùng trong mảng trỏ đến new_node
B3: Lấy con trỏ của new_node trỏ đến null 

 

/**
     * 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

B1: Khởi tạo new_node
B2: Lấy con trỏ tại vị trí prefix tại vị trí pos – 1 trỏ đến new_node
B3: Lấy con trỏ của new_node trỏ đến prefix -> next
/**
  * 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

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x