Kapan menggunakan daftar tertaut di atas daftar array / array?

Saya menggunakan banyak daftar dan array tetapi saya belum menemukan skenario di mana daftar array tidak dapat digunakan semudah, jika tidak lebih mudah daripada, daftar tertaut. Saya berharap seseorang dapat memberi saya beberapa contoh ketika daftar yang tertaut jauh lebih baik.

Daftar tertaut lebih disukai daripada array ketika:

1. Anda memerlukan penyisipan / penghapusan waktu-konstan dari daftar (seperti dalam komputasi waktu nyata di mana prediktabilitas waktu sangat penting)

2. Anda tidak tahu berapa banyak item yang akan ada dalam daftar. Dengan array, Anda mungkin perlu mendeklarasikan ulang dan menyalin memori jika array terlalu besar

3. Anda tidak perlu akses acak ke elemen apa pun

4. Anda ingin dapat memasukkan item di tengah daftar (seperti antrian prioritas)

Array lebih disukai ketika:

1. Anda perlu diindeks / akses acak ke elemen

2. Anda tahu jumlah elemen dalam array sebelumnya sehingga Anda dapat mengalokasikan jumlah memori yang benar untuk array

3. Anda membutuhkan kecepatan saat mengulangi semua elemen secara berurutan. Anda bisa menggunakan pointer matematika pada array untuk mengakses setiap elemen, sedangkan Anda perlu mencari simpul berdasarkan pointer untuk setiap elemen dalam daftar tertaut, yang dapat mengakibatkan kesalahan halaman yang dapat mengakibatkan kinerja hit.

4. memori adalah masalah. Array yang diisi membutuhkan lebih sedikit memori daripada daftar yang ditautkan. Setiap elemen dalam array hanyalah data. Setiap node daftar tertaut memerlukan data serta satu (atau lebih) pointer ke elemen lain dalam daftar tertaut.

Daftar Array (seperti yang ada di .Net) memberi Anda manfaat dari array, tetapi mengalokasikan sumber daya secara dinamis untuk Anda sehingga Anda tidak perlu terlalu khawatir tentang ukuran daftar dan Anda dapat menghapus item pada indeks apa pun tanpa upaya apa pun atau kembali. mengocok elemen di sekitar. Dari segi kinerja, daftar array lebih lambat daripada array mentah.

Array memiliki O (1) akses acak, tetapi sangat mahal untuk menambahkan barang ke atau menghapus barang dari.

Daftar tertaut benar-benar murah untuk menambah atau menghapus item di mana saja dan untuk beralih, tetapi akses acak adalah O (n).

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists baik untuk write-once-read-many atau appenders, tetapi buruk untuk add / remove dari depan atau tengah.

Untuk menambah jawaban lain, sebagian besar implementasi daftar array mencadangkan kapasitas ekstra di akhir daftar sehingga elemen baru dapat ditambahkan ke akhir daftar dalam waktu O (1). Ketika kapasitas daftar array terlampaui, array baru yang lebih besar dialokasikan secara internal, dan semua elemen lama disalin. Biasanya, array baru dua kali lipat dari ukuran yang lama. Ini berarti bahwa rata-rata , menambahkan elemen baru ke akhir daftar array adalah operasi O (1) dalam implementasi ini. Jadi, bahkan jika Anda tidak tahu jumlah elemen sebelumnya, daftar array mungkin masih lebih cepat dari daftar yang ditautkan untuk menambahkan elemen, selama Anda menambahkannya di akhir. Jelas, memasukkan elemen baru di lokasi sembarang dalam daftar array masih merupakan operasi O (n).

Mengakses elemen dalam daftar array juga lebih cepat dari daftar yang ditautkan, meskipun aksesnya berurutan. Ini karena elemen array disimpan dalam memori yang berdekatan dan dapat di-cache dengan mudah. Node daftar tertaut berpotensi tersebar di banyak halaman berbeda.

Saya akan merekomendasikan hanya menggunakan daftar tertaut jika Anda tahu bahwa Anda akan menyisipkan atau menghapus item di lokasi sewenang-wenang. Daftar array akan lebih cepat untuk hampir semua hal lainnya.

Keuntungan daftar muncul jika Anda harus memasukkan item di tengah dan tidak ingin mulai mengubah ukuran array dan menggeser hal-hal di sekitar.

Anda benar karena biasanya tidak demikian. Saya punya beberapa kasus yang sangat spesifik seperti itu, tetapi tidak terlalu banyak.

Itu semua tergantung jenis operasi apa yang Anda lakukan saat iterasi, semua struktur data memiliki trade off antara waktu dan memori dan tergantung pada kebutuhan kita, kita harus memilih DS yang tepat. Jadi ada beberapa kasus di mana LinkedList lebih cepat daripada array dan sebaliknya. Pertimbangkan tiga operasi dasar pada struktur data.

• Mencari

Karena array adalah indeks, pencarian struktur data yang berbasis array. Get (indeks) akan mengambil O (1) waktu sementara linkedlist bukan indeks DS sehingga Anda perlu melintasi hingga indeks, di mana indeks <= n, n adalah ukuran daftar tertaut, jadi array lebih cepat daftar tertaut ketika memiliki akses acak elemen.

Q. Jadi apa keindahan di balik ini?

Karena Array adalah blok memori yang berdekatan, bongkahan besar dari mereka akan dimuat ke dalam cache saat akses pertama ini membuatnya relatif cepat untuk mengakses elemen-elemen array yang tersisa, sebanyak kita mengakses elemen-elemen dalam array lokalitas referensi juga meningkat sehingga kurang menangkap meleset, Cache locality mengacu pada operasi yang ada di cache dan dengan demikian mengeksekusi lebih cepat dibandingkan dengan di memori, pada dasarnya Dalam array kita memaksimalkan peluang akses elemen berurutan berada di cache. Sementara daftar Linked tidak harus dalam blok memori yang berdekatan, tidak ada jaminan bahwa item yang muncul secara berurutan dalam daftar sebenarnya disusun berdekatan satu sama lain dalam memori, ini berarti lebih sedikit hit cache misalnya

• Insersi

Ini mudah dan cepat di LinkedList karena penyisipan adalah operasi O (1) di LinkedList (di Jawa) dibandingkan dengan array, pertimbangkan kasus ketika array penuh, kita perlu menyalin konten ke array baru jika array menjadi penuh yang membuat memasukkan sebuah elemen ke ArrayList of O (n) dalam kasus terburuk, sementara ArrayList juga perlu memperbarui indeksnya jika Anda memasukkan sesuatu di mana saja kecuali pada akhir array, jika daftar tertaut kita tidak perlu mengubah ukurannya, Anda hanya perlu perbarui petunjuk.

• Penghapusan

Ia bekerja seperti penyisipan dan lebih baik di LinkedList daripada array.

Itu adalah implementasi Koleksi yang paling umum digunakan.

Daftar Array:

• masukkan / hapus pada akhirnya umumnya O (1) kasus terburuk O (n)

• masukkan / hapus di tengah O (n)

• mengambil posisi apa pun O (1)

LinkedList:

• masukkan / hapus di posisi apa pun O (1) (perhatikan jika Anda memiliki referensi ke elemen)

• ambil di tengah O (n)

• mengambil elemen O pertama atau terakhir (1)

Vektor: jangan gunakan itu. Ini adalah implementasi lama yang mirip dengan ArrayList tetapi dengan semua metode disinkronkan. Ini bukan pendekatan yang benar untuk daftar bersama di lingkungan multithreading.

HashMap

masukkan / hapus / ambil dengan kunci di O (1)

TreeSet menyisipkan / menghapus / mengandung O (log N)

Masukkan HashSet / hapus / berisi / ukuran dalam O (1)

Pada kenyataannya memori lokalitas memiliki pengaruh kinerja yang sangat besar dalam pemrosesan nyata.

Meningkatnya penggunaan disk streaming dalam pemrosesan "data besar" vs akses acak menunjukkan bagaimana penataan aplikasi Anda di sekitar ini dapat secara dramatis meningkatkan kinerja pada skala yang lebih besar.

Jika ada cara untuk mengakses array secara berurutan yang sejauh ini berkinerja terbaik. Merancang dengan ini sebagai tujuan harus setidaknya dipertimbangkan jika kinerja itu penting.

Hmm, Arraylist dapat digunakan dalam kasus-kasus seperti berikut ini saya kira:

1. Anda tidak yakin berapa banyak elemen yang akan hadir
2. tetapi Anda perlu mengakses semua elemen secara acak melalui pengindeksan

Misalnya, Anda perlu mengimpor dan mengakses semua elemen dalam daftar kontak (ukurannya tidak diketahui oleh Anda)

Gunakan daftar tertaut untuk Radix Sort over arrays dan untuk operasi polinomial.

1) Seperti dijelaskan di atas, operasi insert dan remove memberikan kinerja yang baik (O (1)) di LinkedList dibandingkan dengan ArrayList (O (n)). Oleh karena itu jika ada persyaratan penambahan dan penghapusan yang sering dalam aplikasi maka LinkedList adalah pilihan terbaik.

2) Operasi pencarian (metode get) cepat di Arraylist (O (1)) tetapi tidak di LinkedList (O (n)) jadi jika ada lebih sedikit operasi tambah dan hapus operasi dan lebih banyak persyaratan operasi pencarian, ArrayList akan menjadi taruhan terbaik Anda.

Saya pikir perbedaan utama adalah apakah Anda sering perlu memasukkan atau menghapus barang dari bagian atas daftar.

Dengan sebuah array, jika Anda menghapus sesuatu dari daftar paling atas maka kompleksitasnya adalah o (n) karena semua indeks elemen-elemen array harus bergeser.

Dengan daftar yang ditautkan, ini adalah o (1) karena Anda hanya perlu membuat simpul, menugaskan kembali kepala dan menetapkan referensi berikutnya sebagai kepala sebelumnya.

Ketika sering memasukkan atau menghapus di akhir daftar, array lebih disukai karena kompleksitasnya adalah o (1), tidak diperlukan pengindeksan ulang, tetapi untuk daftar yang ditautkan itu akan menjadi o (n) karena Anda harus pergi dari kepala ke simpul terakhir.

Saya pikir pencarian di dalam daftar yang ditautkan dan array akan menjadi o (log n) karena Anda mungkin akan menggunakan pencarian biner.

Saya melakukan beberapa pembandingan, dan menemukan bahwa kelas daftar sebenarnya lebih cepat daripada LinkedList untuk memasukkan secara acak:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

Dibutuhkan 900 ms untuk daftar tertaut dan 100 ms untuk kelas daftar.

Ini membuat daftar angka integer berikutnya. Setiap integer baru dimasukkan setelah nomor acak yang sudah ada dalam daftar. Mungkin kelas Daftar menggunakan sesuatu yang lebih baik dari sekedar array.

Array, sejauh ini, adalah struktur data yang paling banyak digunakan. Namun, daftar tertaut terbukti bermanfaat dalam cara unik mereka sendiri di mana array canggung - atau mahal, untuk sedikitnya.

Linked Linked berguna untuk mengimplementasikan tumpukan dan antrian dalam situasi di mana ukurannya dapat bervariasi. Setiap node dalam daftar tertaut dapat didorong atau muncul tanpa mengganggu mayoritas node. Hal yang sama berlaku untuk penyisipan / penghapusan node di suatu tempat di tengah. Dalam array, bagaimanapun, semua elemen harus digeser, yang merupakan pekerjaan yang mahal dalam hal waktu eksekusi.

Pohon biner dan pohon pencarian biner, tabel hash, dan percobaan adalah beberapa struktur data di mana - setidaknya di C - Anda perlu daftar terkait sebagai bahan dasar untuk membangunnya.

Namun, daftar tertaut harus dihindari dalam situasi di mana ia diharapkan dapat memanggil elemen sewenang-wenang dengan indeksnya.

Jawaban sederhana untuk pertanyaan dapat diberikan dengan menggunakan poin-poin ini:

1. Array harus digunakan ketika kumpulan elemen data tipe serupa diperlukan. Sedangkan, daftar tertaut adalah kumpulan elemen tertaut data tipe campuran yang dikenal sebagai simpul.

2. Dalam array, seseorang dapat mengunjungi elemen apa pun dalam waktu O (1). Sedangkan, dalam daftar tertaut kita perlu menelusuri seluruh daftar tertaut dari kepala ke simpul yang diperlukan dengan mengambil O (n) waktu.

3. Untuk array, ukuran spesifik perlu dideklarasikan pada awalnya. Tetapi daftar tertaut bersifat dinamis.