LinkedList trong java – GP Coder (Lập trình Java)

Posted on by adminChuyên mục:Kiến thức Internet

Giới thiệu

Danh sách có kết nối ( Linked List) là một trong các cách quản lý danh sách dữ liệu khắc phục được các nhược điểm của mảng.

Lớp LinkedList trong java sử dụng cấu trúc danh sách liên kết Doubly Linked List để lưu trữ các phần tử.

Chi tiết về cấu trúc dữ liệu LinkedList tôi sẽ trình bày ở bài viết khác, trong phạm vi bài này tôi chỉ giới thiệu cách sử dụng LinkedList trong Java.

Những điểm cần ghi nhớ về lớp LinkedList :

  • Có thể chứa các phần tử trùng lặp.
  • Duy trì thứ tự của phần tử được thêm vào.
  • Không đồng bộ (non-synchronized).
  • Thao tác thêm/ xóa (add/ remove) phần tử nhanh vì không cần phải dịch chuyển nếu bất kỳ phần tử nào thêm/ xoá khỏi danh sách.
  • LinkedList có thể được sử dụng như danh sách (list), stack (ngăn xếp) hoặc queue (hàng đợi).
  • Các phần tử trong LinkedList có thể nằm cách ly nhau (không liên tục) trong bộ nhớ. Nó là một liên kết có tính hai chiều giữa các phần tử. Mỗi phần tử trong danh sách cầm giữ một tham chiếu đến đối phần tử đằng trước nó và tham chiếu đến phần tử ngay sau nó.

Hierarchy của lớp LinkedList trong java

Lớp java.util.LinkedList được định nghĩa như sau:


public class LinkedList extends AbstractSequentialList
 	implements List, Deque, Cloneable, java.io.Serializable

Các phương pháp khởi tạo ( constructor ) của lớp LinkedList

  • LinkedList(): khởi tạo một list trống .
  • LinkedList(Collection c): khởi tạo một list với những thành phần của collection c .

Các phương thức (method) của lớp LinkedList

Phương thức Mô tả
void add(int index, Object element) Chèn element đã xác định tại index đã cho. Ném một IndexOutOfBoundsException nếu index đã cho là ở bên ngoài dãy (index < 0 || index > size())
boolean add(Object o) Phụ thêm phần tử đã cho tới cuối của List này
boolean addAll(Collection c) Phụ thêm tất cả phần tử trong collection đã cho tới cuối của list này, theo thứ tự mà chúng được trả về bởi Iterator của collection đã cho. Ném một NullPointerException nếu collection đã cho là null
boolean addAll(int index, Collection c) Chèn tất cả phần tử trong collection đã cho vào trong List này, bắt đầu từ vị trí đã cho. Ném NullPointerException nếu collection đã cho là null
void addFirst(Object o) Chèn phần tử đã cho vào phần đầu của list này
void addLast(Object o) Phụ thêm phần tử đã cho vào phần cuối của list này
void clear() Gỡ bỏ tất cả phần tử từ list này
Object clone() Trả về một shallow copy của LinkedList này
boolean contains(Object o) Trả về true nếu list này chứa phần tử đã cho. Chính thức hơn, trả về true nếu và chỉ nếu list này chứa ít nhất một phần tử e để mà (o==null ? e==null : o.equals(e))
Object get(int index) Trả về phần tử tại vị trí đã cho. Ném IndexOutOfBoundsException nếu index ở bên ngoài dãy (index < 0 || index >= size())
Object getFirst() Trả về phần tử đầu tiên trong list này. Ném NoSuchElementException nếu list này là trống
Object getLast() Trả về phần tử cuối trong list này. Ném NoSuchElementException nếu list này là trống
int indexOf(Object o) Trả về index trong list này cho sự xuất hiện đầu tiên của phần tử đã cho, hoặc -1 nếu List này không chứa phần tử này
int lastIndexOf(Object o) Trả về index trong list này cho sự xuất hiện cuối của phần tử đã cho, hoặc -1 nếu List này không chứa phần tử này
ListIterator listIterator(int index) Trả về một list-iterator của phần tử trong list này (trong dãy chính xác), bắt đầu từ vị trí đã cho trong list. Ném IndexOutOfBoundsException nếu index đã cho ở bên ngoài dãy (index < 0 || index >= size())
Object remove(int index) Gỡ bỏ phần tử tại vị trí đã cho. Ném NoSuchElementException nếu list này là trống
boolean remove(Object o) Gỡ bỏ sự xuất hiện đầu tiên của phần tử đã cho. Ném NoSuchElementException nếu list này trống. Ném IndexOutOfBoundsException nếu index ở bên ngoài dãy (index < 0 || index >= size())
Object removeFirst() Gỡ bỏ và trả về phần tử đầu tiên từ list này. Ném NoSuchElementException nếu list là trống
Object removeLast() Gỡ bỏ và trả về phần tử cuối từ list này. Ném NoSuchElementException nếu list là trống
Object set(int index, Object element) Thay thế phần tử tại vị trí đã cho trong list này với phần tử đã cho. Ném IndexOutOfBoundsException nếu index đã cho ở ngoài dãy (index < 0 || index >= size())
int size() Trả về số phần tử trong list này
Object[] toArray() Trả về một mảng chứa tất cả phần tử trong list này trong đúng thứ tự. Ném NullPointerException nếu mảng đã xác định là null
Object[] toArray(Object[] a) Trả về một mảng chứa tất cả phần tử trong list này trong đúng thứ tự; kiểu runtime của mảng trả về là như của mảng đã xác định

Ví dụ minh họa

Ví dụ sử dụng LinkedList với kiểu dữ liệu cơ bản (Wrapper)

package com.gpcoder.collection.linkedlist;

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
	public static final int NUM_OF_ELEMENT = 5;

	public static void main(String[] args) {
		// Create list with no parameter
		List list1 = new LinkedList<>();
		for (int i = 1; i <= NUM_OF_ELEMENT; i++) {
			// Add element to list
			list1.add("0" + i);
		}
		System.out.print("Init list1 = ");
		printData(list1);

		// addAll()
		List list2 = new LinkedList<>();
		list2.addAll(list1);
		list2.add("0" + 3);
		System.out.print("After list1.addAll(03): list2 = ");
		printData(list2);
        
        // IndexOf()
        System.out.println("list2.indexOf(03) = " + list2.indexOf("03"));
        System.out.println("list2.indexOf(06) = " + list2.indexOf("06"));
        
        // lastIndexOf()
        System.out.println("list2.lastIndexOf(03) = " + list2.lastIndexOf("03"));
        
        // Remove
        list2.remove("01");
		System.out.print("After list2.remove(01): list2 = ");
		printData(list2);
		
		// retainAll()
		List list4 = new LinkedList<>(list1);
        LinkedList list3 = new LinkedList();
        list3.add("0" + 3);
        list3.add("0" + 2);
        System.out.print("Init list3 = ");
        printData(list3);
        list4.retainAll(list3);
        System.out.print("After list1.retainAll(list3): list4 = ");
        printData(list4);
        
        // removeAll()
		List list5 = new LinkedList<>(list1);
		list5.removeAll(list3);
        System.out.print("After list1.removeAll(list3): list5 = ");
        printData(list5);
	}

	public static void printData(List list) {
		// Show list through for-each
		for (String item : list) {
			System.out.print(item + " ");
		}
		System.out.println();
	}

}

Kết quả thực thi chương trình trên :

Init list1 = 01 02 03 04 05 
After list1.addAll(03): list2 = 01 02 03 04 05 03 
list2.indexOf(03) = 2
list2.indexOf(06) = -1
list2.lastIndexOf(03) = 5
After list2.remove(01): list2 = 02 03 04 05 03 
Init list3 = 03 02 
After list1.retainAll(list3): list4 = 02 03 
After list1.removeAll(list3): list5 = 01 04 05

Ví dụ sử dụng LinkedList với kiểu do người dùng tự định nghĩa (Object)

package com.gpcoder.collection.linkedlist;

import java.util.LinkedList;
import java.util.List;

class Student {
	private int id;
	private String name;

	public Student(int id, String name) {
		this.id = id;
		this.name = name;
	}

	@Override
	public String toString() {
		return "Student [id=" + id + ", name=" + name + "]";
	}
}

public class LinkedListExample {
	public static final int NUM_OF_ELEMENT = 5;

	public static void main(String[] args) {
		// Create list 
		List students = new LinkedList<>();
		for (int i = 1; i <= NUM_OF_ELEMENT; i++) {
			// Add element to list
			Student student = new Student(i, "myname" + i);
			students.add(student);
		}

		// Show list student
		for (Student student : students) {
			System.out.println(student);
		}
	}
}

Kết quả thực thi chương trình trên :

Student [id=1, name=myname1]
Student [id=2, name=myname2]
Student [id=3, name=myname3]
Student [id=4, name=myname4]
Student [id=5, name=myname5]

Như các bạn thấy, cách khai báo, sử dụng LinkedList hoàn toàn tương tự như ArrayList. Vậy LinkedList và ArrayList có gì khác nhau, chúng ta hãy cùng tìm hiểu ở bài viết kế tiếp nhé.

4.9

Nếu bạn thấy hay thì hãy chia sẻ bài viết cho mọi người nhé!

Shares

Bình luận

phản hồi

admin