Larik Dinamis

1. Introduction

Visualisasi dari salah satu struktur data paling sederhana: Larik (dan bentuk terurutnya) ternyata belum pernah dilakukan di VisuAlgo sejak lahirnya 2011 - Januari 2024...
Tetaplah bersama kami sementara kami meningkatkan halaman ini dan fitur-fiturnya.

2. Motivasi

Larik (Padat) merupakan salah satu struktur data paling mudah dan serbaguna dalam Ilmu Komputer. Larik sudah tersedia di hampir semua bahasa pemrograman, misalnya C++, Python (di Python, 'array' disebut sebagai 'list'), Java, dan lain-lain.
Kita dapat menggunakan Larik (Padat) untuk mengimplementasikan ADT Daftar.
Kita dapat menggunakan Larik (Padat) untuk menyelesaikan banyak soal klasik. Ketika tidak digunakan sebagai implementasi ADT Daftar (dengan pentingnya urutan posisi), seringkali lebih bermanfaat untuk terlebih dahulu mengurutkan elemen-elemen tersebut sehingga kita dapat memanfaatkan algoritma yang lebih cepat.

2-1. ADT Daftar

Silahkan lihat ringkasan ADT Daftar.

2-2. Implementasi Larik (Bagian 1)

Larik (Padat) bagus untuk mengimplementaikan ADT Daftar karena merupakan konstruksi sederhana untuk menangani kumpulan item.
Yang kita maksud dari larik padat adalah larik tersebut tidak memiliki celah, yaitu jika terdapat N item dalam larik (yang memiliki ukuran M, dengan M ≥ N), makan hanya indeks [0..N-1] yang terisi dan indeks lainnya [N..M-1] harus tetap kosong.

2-3. Implementasi Larik (Bagian 1)

Misalkan larik padat A dengan indeks [0..N-1] mempunyai item pada daftar.


get(i), tinggal mengembalikan A[i].
Operasi sederhana ini menjadi rumit yang tidak perlu jika larik tersebut tidak padat.


search(v), kita bisa mengecek setiap indeks i ∈ [0..N-1] satu per satu untuk lihat jika A[i] == v.
Ini karena nilai v (jika ada) dapat berada di manapun di indeks [0..N-1].
Karena visualisasi ini hanya menerima item berbeda, v hanya dapat ditemukan tidak lebih dari sekali.
Dalam ADT Daftar general, kita mungkin mau membuat search(v) menembalikan sebuah daftar dengan indeks-indeks.


insert(i, v), kita menggeser item ∈ [i..N-1] ke [i+1..N] (dari belakang) dan set A[i] = v.
Ini agar v dimasukkan ke indeks i secara benar dan lariknya akan tetap padat.


remove(i), kita menggeser item ∈ [i+1..N-1] ke [i..N-2], menimpa nilai lama A[i].
Dengan ini, lariknya akan tetap padat.

2-4. Ringkasan Kompleksitas Waktu

get(i) sangat cepat: hanya satu operasi akses O(1).
Terdapat kelas Ilmu Komputer lain: 'Organsisasi Komputer' yang membahas rincian dari kompleksitas waktu O(1) dari operasi indeks larik.


search(v)
Dalam kasus terbaik, v berada di posisi pertama, O(1).
Dalam kasus terburuk, v tidak berada di larik tersebut dan kita memerlukan pencarian linear O(N) untuk menentukan itu.


insert(i, v)
Dalam kasus terbaik, memasukan elemen pada i = N, tidak ada penggeseran elemen, O(1).
Dalam kasus terburuk, memasukan elemen pada i = 0, kita menggeser semua N elemen, O(N).


remove(i)
Dalam kasus terbaik, penghapusan elemen pada i = N-1, tidak ada penggeseran elemen, O(1).
Dalam kasus terburuk, penghapusan elemen pada i = 0, kita menggeser semua N elemen, O(N).

2-5. Masalah Ukuran Tetap

Ukuran dari larik padat M terhingga. Ini akan membuat masalah karena ukuran maksimum tersebut belum tentu diketahui dari awal untuk banyak aplikasi.
Jika M terlalu besar, maka posisi yang tidak digunakan hangus. Jika M terlalu kecil, maka kita akan mudah kehabisan ruang.

2-6. Ukuran Bervariasi

Solusi: Jadikan M sebuah variabel. Saat larik penuh, kita bisa membuat larik yang lebih besar (biasanya dua kali lebih besar) dan pindahkan elemen-elemen dari larik lama ke larik baru. Maka, tidak ada lagi batasan pada ukuran selain ukuran memori fisik komputer (yang biasanya besar).


C++ STL std::vector, Python list, Java Vector, atau Java ArrayList semua mengimplementasikan larik dengan ukuran bervariabel ini. Cata bahwa list Python dan ArrayList Java bukan Senarai Berantai, tetapi adalah larik ukuran bervariabel. Visualisasi larik ini mengimplementasikan ide membuat larik dua kali lebih besar ukurannya jika larik penuh.


Akan tetapi, masalah klasik larik seperti pemborosan ruang dan overhead penyalinan/penggeseran item masih menjadi masalah.

2-7. Aplikasi Larik Padat

Terdapat banyak operasi yang dapat kita lakukan pada sebuah Larik Padat (dengan indeks bilangan bulat) A:

  1. Mencari sebuah nilai spesifik v dalam larik A,
  2. Mencari nilai min/max atau nilai terkecil/terbesar ke-k dalam larik (statik) A,
  3. Mengecek keunikan nilai dan menghapus nilai duplikat dalam larik A,
  4. Menghitung banyaknya nilai v muncul dalam larik A,
  5. Mencari irisan atau gabungan antara larik A dan larik terurut lainnya B,
  6. Mencari sebuah pasangan target x ∈ A dan y ∈ A sehingga x+y sama dengan target z,
  7. Menghitung banyaknya nilai dalam larik A yang berada dalam rentang [lo..hi], dll.

Lihatlah larik tidak terurut dan larik terurut untuk petunjuk.

3. Tindakan

Kami akan menjelaskan tindakan-tindakan yang mungkin dapat Anda lakukan di halaman ini. Untuk sekarang, coba tebak berdasarkan nama fungsinya.

4. Visualisasi

Kita akan membahas dua mode: larik (isi dapat tidak terurut) versus larik terurut (isi harus selalu terurut, tanpa mengurangi keumuman: terurut dalam urutan tidak menurun).

5. Larik (Tidak Terurut)

Sudah banyak aplikasi (sederhana) yang bisa kita lakukan dengan array yang tidak terurut.

5-1. Ide Algoritma (Larik Tidak Terurut)

  1. Kita dapat menggunakan pencarian liner (linear search) dalam O(N) (dari paling kiri ke paling kanan atau sebaliknya) untuk mencari v,
  2. Untuk min/max, kita dapat menggunakan pencarian liner O(N) lagi;
    untuk terkecil/terbesar ke-k, kita bisa menggunakan algoritma O(kN)1,
  3. Kita bisa menggunakan O(N^2) perulangan bersarang (nested-loop) untuk mengecek apakah terdapat dua indeks dalam A mempunyai nilai yang sama,
  4. Kita mungkin memperlukan Tabel Hash untuk mendapatkan kompleksitas O(N),
  5. Diperlukan perulangan bersarang dalam O(N^2).
  6. Diperlukan perulangan bersarang dalam O(N^2).
  7. Kita mungkin memperlukan Tabel Hash untuk mendapatkan kompleksitas O(N),

Terdapat beberapa cara yang lebih bagus, terumata jika lariknya terurut.


1Terdapat solusi lebih cepat dengan ekspektasi kompeksitas waktu O(N) QuickSelect atau O(N) kasus paling jelek seleksi waktu liner.

6. Larik (Terurut)

Ketika larik terurut, banyak kemungkinan yang terbuka.

6-1. Ide Algoritma (Larik Terurut)

  1. Kita bisa menggunakan pencarian biner (binary search) dalam O(log N) pada larik terurut,
  2. A[0]/A[k-1]/A[N-k]/A[N-1] merupakan nilai min/terkecil ke-k/terbesar ke-k/max dalam larik (statik terurut) A,
  3. Nilai kembar, jika ada, akan bersebelahan pada larik terurut A,
  4. Sama dengan atas,
  5. Kita bisa menggunakan modifikasi dari rutinitas merge dari Merge Sort.
  6. Kita bisa menggunakan metode two pointers,
  7. Indeks dari y - indeks dari x + 1 (menggunakan dua kali pencarian biner).

Bisa terdapat banyak cara lain.