Struktur data cepat dengan contoh. Bagian satu: daftar tertaut

Kata Pengantar

Manakah dari pengembang iOS yang tidak bermimpi bekerja di tempat bergengsi seperti Yandex atau Avito. Sayangnya, hanya jam bertanya tentang mimpi di wawancara, tetapi pewawancara pengembang mengajukan pertanyaan yang agak berbeda. Apa perbedaan antara tipe referensi dan tipe nilai atau batasan dari bingkai? Pertanyaan yang masing-masing dari kita telah dengar lebih dari satu kali saat wawancara. Jika wawancara Anda dimulai dengan pertanyaan tentang perbedaan antara jenis signifikan dan referensi atau dalam semangat "ceritakan tentang SOLID", maka Anda jelas berada di jalur untuk mencari pekerjaan di So-so-Perspectives LLC.

Dalam perusahaan yang layak, Anda tidak akan ditanyai omong kosong seperti itu. Bersiaplah untuk pertanyaan tentang pengiriman, tabel samping, dan antrian yang mendasarinya. Pengetahuan tentang nuansa seperti itu tidak akan membantu mencapai 60 FPS saat menggulir, memuat elemen sel dan tidak akan menjadikan Anda pengembang terhormat Rusia. Mereka akan membantu Anda mengenali seseorang yang tidak hanya mengubah tingkat xib selama 4 tahun dan sekarang menganggap dirinya sebagai Pengembang iOS Senior, tetapi benar-benar tertarik pada platform. Akan selalu menjadi misteri bagi saya pada titik mana seseorang memutuskan bahwa ia telah mencapai tingkat Menengah atau Senior. Mungkin berpartisipasi dalam kompetisi semua-Rusia, di mana ROS-GOS-iOS memberikan penghargaan kategori dan judul untuk memenuhi standar dan hadiah.

Kembali ke wawancara. Majikan bergengsi tidak hanya akan mengajukan pertanyaan rumit tentang platform, tetapi ia juga akan bertanya tentang arsitektur. Tunggu pertanyaan: "Mengapa Anda menggunakan VIPER alih-alih MVVM di tempat terakhir?". Anda mungkin bertanya-tanya: "Apa itu MVC buruk?". Nah, paku terakhir di tutup peti mati adalah algoritma. Sekalipun Anda sangat berpengalaman dalam iOS dan arsitektur aplikasi seluler, tetapi tidak tahu kelemahan array dan tidak dapat mengoptimalkan pencarian elemen, maka setelah wawancara, tunggu jawaban melalui pos:


Di hamparan Internet berbahasa Rusia penuh dengan artikel tentang algoritma dan struktur data. Satu-satunya kelemahan yang dapat mengaburkan penelitian adalah kelangkaan contoh dan implementasi pada Swift. Sangat sulit untuk memahami topik ini ketika Anda mendapatkan banyak kata-kata yang tidak jelas dan lebih banyak lagi contoh-contoh C ++ yang tidak jelas.

Untuk semua orang yang ingin minum smoothie setiap hari di kantor yang apik dan di pertemuan alumni untuk berbicara tentang bagaimana dia sendiri menyeret semua pengembangan ponsel Sber, saya menyiapkan beberapa artikel tentang struktur data. Artikel ditujukan untuk pengembang yang sudah terbiasa dengan obat generik, telah bekerja dengan array / set / kamus, memahami perbedaan antara kelas dan struktur dan berpura-pura bahwa mereka memahami rekursi. Saya tidak akan melukis teorinya. Ini sudah dilakukan sebelum saya dan saya yakin itu cukup informatif. Mari kita fokus pada contoh-contohnya.

Daftar tertaut

Wikipedia akan membantu dengan teorinya . Mari kita mulai dengan membuat simpul yang sama .


_{* Pastikan untuk mengubah skema warna Xcode Anda menjadi gelap jika tidak, Anda tidak akan melihat pekerjaan di Mail}

Pembaca yang penuh perhatian harus bertanya: "Mengapa pengembang Momkin memutuskan untuk mengimplementasikan node sebagai kelas, bukan struktur? Artikel ini tentang struktur data! " Saya sarankan mendiskusikan keputusan ini di komentar. Mari beralih ke daftar yang paling terhubung. Implementasi awal akan terlihat seperti ini:



Setiap pakar bor yang menghargai diri sendiri akan mencatat bahwa WeakReference adalah tipe yang tidak diketahui dan akan membutuhkan implementasi.



Tambahkan ke metode implementasi yang bertanggung jawab untuk mengisi daftar kami:




_{* Kompleksitas O (1) hanya valid jika tidak perlu menyalin struktur. Kalau tidak, kita akan memiliki kompleksitas O (n). Ini berlaku untuk semua metode bermutasi.}

Tambahkan metode yang bertanggung jawab untuk menghapus dari daftar:




_{* @ discardableResult akan menyelamatkan kita dari keharusan menulis "_ =" sebelum memanggil fungsi ketika nilai kembali tidak menarik bagi kita}

Kerajinan kami sudah terlihat seperti daftar tautan yang berfungsi. Mari kita coba menjadikannya sebagai berorientasi Swift mungkin. Untuk melakukan ini, kita hanya perlu mengimplementasikan dua hal: protokol BidirectionalCollection dan teknik copy-on-write . Mari kita mulai dengan protokol. Ada beberapa metode di dalamnya, dan hal yang paling sulit adalah memahami dan mengimplementasikan Index.




Hebat! Sekarang semua koleksi koleksi kami tersedia di daftar kami. Kami dapat menerapkan peta, compactMap, filter, berisi, dll. Sekarang giliran copy-on-write. Kami menerapkan metode copyIfNeeded () karena kurangnya kompiler sekarang mengisyaratkan bahwa kode tidak ditulis oleh D'Artagnan:



Mereka yang ingin mengajukan pertanyaan pintar atau menunjukkan kekurangan sedang menunggu di komentar.
PS Saya berterima kasih kepada ivlevAstef untuk bantuan dalam memperbaiki bug. Belum ada yang mengusulkan implementasi kerja tanpa pembungkus lemah.

Kode Github