Giới thiệu về danh sách

Giới thiệu

Danh sách, ngăn xếp, hàng đợi và hàng đợi ưu tiên là cấu trúc dữ liệu cổ điển thường được bao phủ trong một khóa học về cấu trúc dữ liệu. Chúng được hỗ trợ trong Java API, và các ứng dụng của chúng được trình bày trong phần Danh sách, Các ngăn xếp, Hàng đợi và Hàng đợi Ưu tiên. Trong phần này sẽ xem xét các cấu trúc dữ liệu được cài đặt như thế nào.

Những tính năng chung đối với danh sách

Những tính năng chung của danh sách được định nghĩa trong interface List.

Danh sách là một cấu trúc dữ liệu phổ biến để lưu trữ dữ liệu theo trình tự – ví dụ: danh sách sinh viên, danh sách các phòng sẵn có, danh sách các thành phố, danh sách các quyển sách. Bạn có thể thực hiện các thao tác sau trong một danh sách:

• Lấy một phần tử khỏi danh sách
• Chèn một phần tử mới vào danh sách
• Xoá một phần tử khỏi danh sách
• Tìm xem có bao nhiêu phần tử có trong danh sách
• Xác định xem một phần tử có thuộc danh sách hay không
• Kiểm tra xem danh sách có rỗng hay không

Có hai cách để cài đặt một danh sách. Một là sử dụng một mảng (array) để lưu trữ các phần tử. Kích thước mảng là cố định. Nếu dung lượng của mảng bị vượt quá, bạn cần phải tạo một mảng lớn hơn và sao chép tất cả các phần tử từ mảng hiện tại sang mảng mới. Cách tiếp cận khác là sử dụng một cấu trúc liên kết (linked structure). Một cấu trúc liên kết bao gồm các nút. Mỗi nút được tạo tự động để giữ một phần tử. Tất cả các nút được liên kết với nhau để tạo thành một danh sách. Vì vậy bạn có thể xác định hai lớp cho danh sách. Để tiện lợi, hãy đặt tên chúng là MyArrayList và MyLinkedList. Hai lớp này có các thao tác chung nhưng sự thực thi của chúng lại khác nhau.

Đặt tên cho interface là MyList và lớp trừu tượng là MyAbstractList. Hình 24.2 chỉ ra mối quan hệ của MyList, MyAbstractList, MyArrayList và MyLinkedList. Các phương thức trong MyList và các phương thức được thực thi trong MyAbstractList được chỉ ra trong Hình 24.3. Listing 24.1 cung cấp mã nguồn cho MyList.


Hình 24.1 Cách làm việc của danh sách tạo từ mảng và danh sách liên kết

Hình 24.2 MyList định nghĩa interface chung cho MyAbstractList, MyArrayList, and MyLinkedList.

public interface MyList<E> extends java.lang.Iterable<E> {    public void add(E e);    public void add(int index, E e);    public void clear();    public boolean contains(E e);    public E get(int index);    public int indexOf(E e);    public boolean isEmpty();    public int lastIndexOf(E e);    public boolean remove(E e);    public E remove(int index);    public Object set(int index, E e);    public int size();}

MyAbstractList khai báo biến size cho biết số phần tử có trong danh sách. Các phương thức isEmpty(), size(), add(E), và remove(E) có thể được thực thi trong lớp như trong Listing 24.2.

Hình 24.3 MyList định nghĩa các phương thức để thao tác trong một danh sách. MyAbstractList cung cấp một phần sự thực thi của interface MyList

public abstract class MyAbstractList<E> implements MyList<E> {    protected int size = 0;    protected MyAbstractList() {    }    protected MyAbstractList(E[] objects) {        for (int i = 0; i < objects.length; i++) {            add(objects[i]);        }    }    @Override    public void add(E e) {        add(size, e);    }    @Override    public boolean isEmpty() {        return size == 0;    }    @Override    public int size() {        return size;    }    @Override    public boolean remove(E e) {        if (indexOf(e) >= 0) {            remove(indexOf(e));            return true;        } else {            return false;        }    }

Phần danh sách mảng và danh sách mảng liên kết tiếp theo cung cấp sự thực thi của MyArrayList và MyLinkedList