Mengapa menyisipkan di tengah daftar tertaut O (1)?

Menurut artikel Wikipedia tentang daftar tertaut , memasukkan di tengah daftar tertaut dianggap O (1). Saya akan berpikir itu akan menjadi O (n). Tidakkah Anda perlu menemukan node yang mungkin berada di dekat akhir daftar?

Apakah analisis ini tidak memperhitungkan penemuan operasi node (meskipun diperlukan) dan hanya penyisipan itu sendiri?

EDIT :

Daftar tertaut memiliki beberapa keunggulan dibandingkan array. Penyisipan elemen pada titik tertentu dari daftar adalah operasi waktu-konstan, sedangkan penyisipan dalam array mungkin memerlukan pemindahan setengah dari elemen, atau lebih.

Pernyataan di atas sedikit menyesatkan saya. Koreksi saya jika saya salah, tetapi menurut saya kesimpulannya harus:

Array:

• Menemukan titik penyisipan / penghapusan O (1)
• Melakukan penyisipan / penghapusan O (n)

Daftar Tertaut:

• Menemukan titik penyisipan / penghapusan O (n)
• Melakukan penyisipan / penghapusan O (1)

Saya pikir satu-satunya saat Anda tidak perlu menemukan posisi adalah jika Anda menyimpan semacam penunjuk ke sana (seperti kepala dan ekor dalam beberapa kasus). Jadi kami tidak bisa secara langsung mengatakan bahwa daftar tertaut selalu mengalahkan array untuk opsi sisipkan / hapus.

Anda benar, artikel menganggap "Pengindeksan" sebagai operasi terpisah. Jadi penyisipan itu sendiri adalah O (1), tetapi sampai ke simpul tengah itu adalah O (n).

Penyisipan itu sendiri adalah O (1). Penemuan node adalah O (n).

Tidak, ketika Anda memutuskan untuk memasukkan, diasumsikan Anda sudah di tengah iterasi melalui daftar.

Operasi pada Daftar Tertaut sering dilakukan sedemikian rupa sehingga tidak diperlakukan sebagai "daftar" generik, tetapi sebagai kumpulan node - anggap node itu sendiri sebagai iterator untuk loop utama Anda. Jadi saat Anda melihat-lihat daftar, Anda melihat sebagai bagian dari logika bisnis Anda bahwa node baru perlu ditambahkan (atau yang lama dihapus) dan Anda melakukannya. Anda dapat menambahkan 50 node dalam satu iterasi dan masing-masing node tersebut hanya O (1) waktu untuk memutuskan tautan dua node yang berdekatan dan memasukkan yang baru ..

Sunting: Sobat, Anda mengetik paragraf kedua dan tiba-tiba alih-alih menjadi responden pertama, Anda yang ke-5 mengatakan hal yang sama seperti 4 yang pertama!

Untuk tujuan membandingkan dengan larik, yang ditunjukkan bagan itu, itu adalah O (1) karena Anda tidak perlu memindahkan semua item setelah simpul baru.

Jadi ya, mereka berasumsi bahwa Anda sudah memiliki pointer ke node itu, atau mendapatkan pointer itu sepele. Dengan kata lain, masalahnya adalah: " diberi node di X , kode apa yang akan dimasukkan setelah node ini?" Anda bisa mulai dari titik sisipan.

Penyisipan ke dalam daftar tertaut berbeda dengan pengulangan di atasnya. Anda tidak menemukan item tersebut, Anda menyetel ulang penunjuk untuk meletakkan item di sana. Tidak masalah apakah itu akan disisipkan di dekat ujung depan atau dekat ujung, penyisipan masih melibatkan penunjuk yang ditugaskan kembali. Ini akan tergantung pada bagaimana itu diterapkan, tentu saja, tapi itulah kekuatan daftar - Anda dapat menyisipkan dengan mudah. Mengakses melalui indeks adalah tempat array bersinar. Untuk daftar, bagaimanapun, biasanya akan menjadi O (n) untuk menemukan item ke-n. Setidaknya itulah yang saya ingat dari sekolah.

Karena tidak melibatkan perulangan apapun.

Memasukkan itu seperti:

• masukkan elemen
• tautan ke sebelumnya
• tautan ke berikutnya
• selesai

ini adalah waktu yang konstan dalam hal apapun.

Akibatnya, memasukkan n elemen satu demi satu adalah O (n).

Apakah analisis ini tidak memperhitungkan penemuan operasi node (meskipun diperlukan) dan hanya penyisipan itu sendiri?

Anda mengerti. Penyisipan pada titik tertentu mengasumsikan bahwa Anda sudah menahan penunjuk ke item yang ingin Anda sisipkan setelah:

InsertItem(item * newItem, item * afterItem)

Menyisipkan adalah O (1) setelah Anda tahu di mana Anda akan meletakkannya.

Tidak, itu tidak termasuk pencarian. Tetapi jika Anda sudah memiliki penunjuk ke item di tengah daftar, memasukkan pada titik itu adalah O (1).

Jika Anda harus mencarinya, Anda harus menambahkan waktu untuk mencari, yang seharusnya O (n).

Artikel ini tentang membandingkan array dengan daftar. Menemukan posisi sisipan untuk kedua larik dan daftar adalah O (N), jadi artikel mengabaikannya.

O (1) tergantung pada fakta bahwa Anda memiliki item di mana Anda akan memasukkan item baru. (sebelum atau sesudah). Jika tidak, itu adalah O (n) karena Anda harus menemukan item itu.

Saya pikir itu hanya kasus apa yang Anda pilih untuk dihitung untuk notasi O (). Dalam kasus memasukkan operasi normal untuk menghitung adalah operasi salin. Dengan array, memasukkan di tengah melibatkan menyalin semua yang ada di atas lokasi ke dalam memori. Dengan daftar yang ditautkan, ini menjadi pengaturan dua petunjuk. Anda perlu menemukan lokasinya tidak peduli apa yang akan dimasukkan.

Jika Anda memiliki referensi node untuk disisipkan setelah operasi adalah O (1) untuk daftar tertaut.
Untuk sebuah array, nilainya tetap O (n) karena Anda harus memindahkan semua node konkutif.

Kasus yang paling umum mungkin menyisipkan di awal atau di akhir daftar (dan akhir daftar mungkin tidak perlu waktu untuk menemukannya).

Bandingkan dengan menyisipkan item di awal atau akhir larik (yang memerlukan pengubahan ukuran larik jika ada di akhir, atau mengubah ukuran dan memindahkan semua elemen jika di awal).