Linked List

Mục lục

1 Xây dựng danh sách liên kết

Linked list(Danh sách liên kết) là một tập hợp các thành phần dữ liệu, Các thành phần tử trong danh sách liên kết không có thứ tự mà thay vào đó mỗi phần tử sẽ trỏ đến phần tử tiếp theo. Mỗi phần tử trong danh sách liên kết được gọi là node, danh sách liên kết dạng đơn giản nhất ở mỗi node có chứa 2 thành phần là data và con trỏ đến phần tử tiếp theo trong danh sách liên kết.

Ưu điểm:

Danh sách liên kết cho phép thêm và xoá các phần tử hiệu quả trong một dãy các phần tử nối tiếp.
Danh sách liên kết là một cấu trúc dữ liệu động, chiều dài có thể co giãn theo số phần tử.

Nhược điểm:

Thời gian truy cập của danh sách liên kết là tuyến tính
Truy cập nhanh hoặc random là không thể trong danh sách liên kết
Tốn không gian lưu trữ con trỏ

Xây dựng danh sách liên kết

Node

Trong danh sách liên kết, mỗi phần tử là một node có 2 thành phần chính là Data và một con trỏ next reference đến phần tử tiếp theo.

package LinkedList;

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

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

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

Danh sách liên kết của chúng ta chỉ đơn giản là chứa một node Head là phần tử đầu tiên của mảng, các phần tử còn lại của danh sách liên kết đều được truy xuất thông qua Head.

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

    public LinkedList() {
        this.head = null;
    }
}

Xây dựng danh sách liên kết

Node

Linked List

Topics