Java LinkedList

Trong hướng dẫn này, chúng ta sẽ tìm hiểu chi tiết về Java LinkedList với sự trợ giúp của các ví dụ.

Các LinkedListlớp học của khuôn khổ bộ sưu tập Java cung cấp các chức năng của cấu trúc dữ liệu danh sách liên kết (gấp đôi linkedlist).Java Double LinkedList

Mỗi phần tử trong danh sách liên kết được gọi là một nút . Nó bao gồm 3 trường:

• Prev – stores an address of the previous element in the list. It is null for the first element
• Next – stores an address of the next element in the list. It is null for the last element
• Data – stores the actual data

Tạo danh sách liên kết Java

Đây là cách chúng ta có thể tạo danh sách liên kết trong Java:

LinkedList<Type> linkedList = new LinkedList<>();

Ở đây, Loại cho biết loại danh sách được liên kết. Ví dụ,

// create Integer type linked list
LinkedList<Integer> linkedList = new LinkedList<>();

// create String type linked list
LinkedList<String> linkedList = new LinkedList<>();

Ví dụ: Tạo LinkedList trong Java

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);
  }
}

Đầu ra

LinkedList: [Dog, Cat, Cow]

Trong ví dụ trên, chúng tôi đã tạo ra một con vậtLinkedList được đặt tên .

Ở đây, chúng tôi đã sử dụng add()phương pháp để thêm các phần tử vào LinkedList. Chúng ta sẽ tìm hiểu thêm về add()phương pháp sau trong hướng dẫn này.

Hoạt động của một Java LinkedList

Các phần tử trong danh sách liên kết không được lưu trữ theo trình tự. Thay vào đó, chúng được phân tán và kết nối thông qua các liên kết ( Trước và Tiếp theo ).Triển khai danh sách liên kết Java

Ở đây chúng tôi có 3 yếu tố trong một danh sách được liên kết.

• Dog – it is the first element that holds null as previous address and the address of Cat as the next address
• Cat – it is the second element that holds an address of Dog as the previous address and the address of Cow as the next address
• Cow – it is the last element that holds the address of Cat as the previous address and null as the next element

Để tìm hiểu thêm, hãy truy cập Cấu trúc dữ liệu LinkedList .

Các phương thức của Java LinkedList

LinkedListcung cấp các phương pháp khác nhau cho phép chúng tôi thực hiện các hoạt động khác nhau trong danh sách được liên kết. Chúng ta sẽ xem xét bốn Toán tử LinkedList thường được sử dụng trong hướng dẫn này:

• Add elements
• Access elements
• Change elements
• Remove elements

1. Thêm các phần tử vào LinkedList

Chúng ta có thể sử dụng add()phương thức để thêm một phần tử (nút) vào cuối LinkedList. Ví dụ,

import java.util.LinkedList;

class Main {
  public static void main(String[] args){
    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // add() method without the index parameter
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    // add() method with the index parameter
    animals.add(1, "Horse");
    System.out.println("Updated LinkedList: " + animals);
  }
}

Đầu ra

LinkedList: [Dog, Cat, Cow]
Updated LinkedList: [Dog, Horse, Cat, Cow]

Trong ví dụ trên, chúng tôi đã tạo một LinkedList có tên là động vật . Ở đây, chúng tôi đã sử dụng add()phương pháp để thêm các yếu tố cho động vật .

Lưu ý tuyên bố,

animals.add(1, "Horse");

Ở đây, chúng tôi đã sử dụng tham số số chỉ mục . Nó là một tham số tùy chọn chỉ định vị trí mà phần tử mới được thêm vào.

Để tìm hiểu thêm về cách thêm phần tử vào LinkedList, hãy truy cập chương trình Java để thêm phần tử vào LinkedList .

2. Truy cập các phần tử LinkedList

Các get()phương pháp của lớp LinkedList được sử dụng để truy cập vào một phần tử từ LinkedList. Ví dụ,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in the linked list
    languages.add("Python");
    languages.add("Java");
    languages.add("JavaScript");
    System.out.println("LinkedList: " + languages);

    // get the element from the linked list
    String str = languages.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

Đầu ra

LinkedList: [Python, Java, JavaScript]
Element at index 1: Java

Trong ví dụ trên, chúng ta đã sử dụng get()phương thức với tham số 1 . Ở đây, phương thức trả về phần tử ở chỉ mục 1 .

Chúng tôi cũng có thể yếu tố tiếp cận của LinkedList sử dụng iterator()và listIterator()phương pháp. Để tìm hiểu thêm, hãy truy cập chương trình Java để truy cập các phần tử của LinkedList .

3. Thay đổi các yếu tố của một danh sách liên kết

Các set()phương pháp của LinkedListlớp được sử dụng để thay đổi các yếu tố của LinkedList. Ví dụ,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in the linked list
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Java");
    System.out.println("LinkedList: " + languages);

    // change elements at index 3
    languages.set(3, "Kotlin");
    System.out.println("Updated LinkedList: " + languages);
  }
}

Đầu ra

LinkedList: [Java, Python, JavaScript, Java]
Updated LinkedList: [Java, Python, JavaScript, Kotlin]

Trong ví dụ trên, chúng tôi đã tạo một ngôn ngữ có tên LinkedList. Lưu ý dòng,

languages.set(3, "Kotlin");

Ở đây, set()phương thức thay đổi phần tử ở chỉ mục 3 thành Kotlin .

4. Xóa phần tử khỏi LinkedList

Các remove()phương pháp của LinkedListlớp được sử dụng để loại bỏ một phần tử từ LinkedList. Ví dụ,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in LinkedList
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Kotlin");
    System.out.println("LinkedList: " + languages);

    // remove elements from index 1
    String str = languages.remove(1);
    System.out.println("Removed Element: " + str);

    System.out.println("Updated LinkedList: " + languages);
  }
}

Đầu ra

LinkedList: [Java, Python, JavaScript, Kotlin]
Removed Element: Python
New LinkedList: [Java, JavaScript, Kotlin]

Ở đây, remove()phương thức lấy số chỉ mục làm tham số. Và, loại bỏ phần tử được chỉ định bởi số chỉ mục.

Để tìm hiểu thêm về cách xóa các phần tử khỏi danh sách liên kết, hãy truy cập chương trình Java để xóa các phần tử khỏi LinkedList. .

Các phương pháp khác

Methods	Decfscription
contains()	checks if the LinkedList contains the element
indexOf()	returns the index of the first occurrence of the element
lastIndexOf()	returns the index of the last occurrence of the element
clear()	removes all the elements of the LinkedList
iterator()	returns an iterator to iterate over LinkedList

LinkedList dưới dạng Deque và Queue

Vì LinkedListlớp cũng triển khai hàng đợi và giao diện Deque , nên nó cũng có thể triển khai các phương thức của các giao diện này. Dưới đây là một số phương pháp thường được sử dụng:

Methods	Decfscriptions
addFirst()	adds the specified element at the beginning of the linked list
addLast()	adds the specified element at the end of the linked list
getFirst()	returns the first element
getLast()	returns the last element
removeFirst()	removes the first element
removeLast()	removes the last element
peek()	returns the first element (head) of the linked list
poll()	returns and removes the first element from the linked list
offer()	adds the specified element at the end of the linked list

Ví dụ: Java LinkedList as Queue

import java.util.LinkedList;
import java.util.Queue;

class Main {
  public static void main(String[] args) {
    Queue<String> languages = new LinkedList<>();

    // add elements
    languages.add("Python");
    languages.add("Java");
    languages.add("C");
    System.out.println("LinkedList: " + languages);

    // access the first element
    String str1 = languages.peek();
    System.out.println("Accessed Element: " + str1);

    // access and remove the first element
    String str2 = languages.poll();
    System.out.println("Removed Element: " + str2);
    System.out.println("LinkedList after poll(): " + languages);

    // add element at the end
    languages.offer("Swift");
    System.out.println("LinkedList after offer(): " + languages);
  }
}

Đầu ra

LinkedList: [Python, Java, C]
Accessed Element: Python
Removed Element: Python
LinkedList after poll(): [Java, C]
LinkedList after offer(): [Java, C, Swift]

Ví dụ: LinkedList as Deque

import java.util.LinkedList;
import java.util.Deque;

class Main {
  public static void main(String[] args){
    Deque<String> animals = new LinkedList<>();

    // add element at the beginning
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    animals.addFirst("Dog");
    System.out.println("LinkedList after addFirst(): " + animals);

    // add elements at the end
    animals.addLast("Zebra");
    System.out.println("LinkedList after addLast(): " + animals);

    // remove the first element
    animals.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + animals);

    // remove the last element
    animals.removeLast();
    System.out.println("LinkedList after removeLast(): " + animals);
  }
}

Đầu ra

LinkedList: [Cow]
LinkedList after addFirst(): [Dog, Cow]
LinkedList after addLast(): [Dog, Cow, Zebra]
LinkedList after removeFirst(): [Cow, Zebra]
LinkedList after removeLast(): [Cow]

Lặp lại qua LinkedList

Chúng ta có thể sử dụng Java for-each loop để lặp qua LinkedList. Ví dụ,

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        // Creating a linked list
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        // Using forEach loop
        System.out.println("Accessing linked list elements:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

Đầu ra

LinkedList: [Cow, Cat, Dog]
Accessing linked list elements:
Cow, Cat, Dog,

LinkedList Vs. Lập danh sách

Cả Java ArrayList và LinkedListhiện thực Listgiao diện của Collectionskhung. Tuy nhiên, tồn tại một số khác biệt giữa chúng.

LinkedList	ArrayList
Implements List, Queue, and Deque interfaces.	Implements List interface.
Stores 3 values (previous address, data, and next address) in a single position.	Stores a single value in a single position.
Provides the doubly-linked list implementation.	Provides a resizable array implementation.
Whenever an element is added, prev and next address are changed.	Whenever an element is added, all elements after that position are shifted.
To access an element, we need to iterate from the beginning to the element.	Can randomly access elements using indexes.

Lưu ý : Chúng tôi cũng có thể tạo một LinkedList bằng cách sử dụng các giao diện trong Java. Ví dụ,

// create linkedlist using List
List<String> animals1 = new LinkedList<>();

// creating linkedlist using Queue
Queue<String> animals2 = new LinkedList<>();

// creating linkedlist using Deque
Deque<String> animals3 = new LinkedList<>();

Ở đây, nếu LinkedList được tạo bằng một giao diện, thì chúng ta không thể sử dụng các phương pháp được cung cấp bởi các giao diện khác. Có nghĩa là, animal1 không thể sử dụng các phương thức dành riêng cho Queuevà các Dequegiao diện.