Cách tìm phần tử giữa trong LinkedList Android

Giới thiệu

Ví dụ này minh họa cách tìm phần tử ở giữa (middle element) của một LinkedList trong Android.

Bước 1: Tạo dự án mới

Mở Android Studio, chọn File → New Project và điền đầy đủ thông tin cần thiết.

Bước 2: Thiết kế giao diện (res/layout/activity_main.xml)

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="https://schemas.android.com/apk/res/android"
    xmlns:app="https://schemas.android.com/apk/res-auto"
    xmlns:tools="https://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:gravity="center"
    tools:context=".MainActivity">

    <TextView
        android:id="@+id/text"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:textSize="30sp"
        android:gravity="center"
        android:padding="16dp" />

</LinearLayout>

Bước 3: MainActivity.java

package com.example.myapplication;

import android.os.Bundle;
import android.widget.TextView;
import androidx.appcompat.app.AppCompatActivity;
import java.util.LinkedList;

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        LinkedList list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);

        // Cách 1: Dùng size() / 2 (phần tử giữa bên phải nếu chẵn)
        int middleIndex = list.size() / 2;
        int middleElement = list.get(middleIndex);

        TextView textView = findViewById(R.id.text);
        textView.setText("Danh sách: " + list + 
            "\nĐộ dài: " + list.size() + 
            "\nIndex giữa: " + middleIndex + 
            "\nPhần tử giữa: " + middleElement);
    }
}

Chạy ứng dụng

Kết nối thiết bị Android thật với máy tính. Trong Android Studio, nhấn Run và chọn thiết bị để chạy.

Kết quả

Danh sách: [1, 2, 3, 4, 5, 6, 7] (7 phần tử)

Index giữa = 7/2 = 3 (lấy phần nguyên)

Phần tử tại index 3: 4

Giải thích và mở rộng

Độ phức tạp: O(1) để lấy size, O(n) để get(index) vì LinkedList không hỗ trợ random access hiệu quả.

Cách tối ưu cho LinkedList lớn (Two Pointers - Slow/Fast):

// Tìm giữa chỉ duyệt 1 lần - O(n) nhưng không cần size()
public static  E findMiddle(LinkedList list) {
    if (list.isEmpty()) return null;
    
    var slow = list.listIterator(0);
    var fast = list.listIterator(0);
    
    while (fast.hasNext()) {
        fast.next();
        if (fast.hasNext()) {
            fast.next();
            slow.next();
        }
    }
    return slow.next();
}

Lưu ý: Code gốc dùng @RequiresApi(api = Build.VERSION_CODES.P) không cần thiết. LinkedList.get(index) hoạt động trên mọi API level.