Π Π°Π±ΠΎΡ‚Π° с динамичСскими списками Π² ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ΅ 1Π‘:ΠŸΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΠ΅ являСтся ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· Π±Π°Π·ΠΎΠ²Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ для любого Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ°. ΠΠ΅ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½Ρ‹ΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΊ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΏΠΎ коллСкциям Π΄Π°Π½Π½Ρ‹Ρ… ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ критичСскому замСдлСнию Ρ€Π°Π±ΠΎΡ‚Ρ‹ систСмы, особСнно ΠΏΡ€ΠΈ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… ΠΎΠ±ΡŠΠ΅ΠΌΠ°Ρ… записСй. Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ часто ΡΡ‚Π°Π»ΠΊΠΈΠ²Π°ΡŽΡ‚ΡΡ с ситуациСй, ΠΊΠΎΠ³Π΄Π° ΠΊΠΎΠ΄ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎ Π½Π° тСстовой Π±Π°Π·Π΅ с дСсятком строк, Π½ΠΎ «встаСт» Π½Π° Ρ€Π΅Π°Π»ΡŒΠ½ΠΎΠΉ эксплуатации ΠΏΡ€ΠΈ тысячах элСмСнтов.

Основная ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² Π²Ρ‹Π±ΠΎΡ€Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π° ΠΈ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠΈ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅ΠΉ структуры ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Ρ‚ΠΈΠΏΠ° БписокЗначСний ΠΈΠ»ΠΈ Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Π’Π°ΠΆΠ½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π°Ρ‚ΡŒ ситуации, ΠΊΠΎΠ³Π΄Π° трСбуСтся просто ΠΏΡ€ΠΎΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ Π΄Π°Π½Π½Ρ‹Π΅, ΠΈ случаи, ΠΊΠΎΠ³Π΄Π° Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΌΠΎΠ΄ΠΈΡ„ΠΈΡ†ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ структуру списка Β«Π½Π° Π»Π΅Ρ‚ΡƒΒ». Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ Ρ€Π°Π·Π±Π΅Ρ€Π΅ΠΌ тонкости Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Ρ†ΠΈΠΊΠ»ΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ обСспСчат ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ вашСго ΠΊΠΎΠ΄Π°.

ОсобоС Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ стоит ΡƒΠ΄Π΅Π»ΠΈΡ‚ΡŒ ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌΠ°ΠΌ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ ΠΈ индСксации, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° примСняСт ΠΏΡ€ΠΈ ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΠΈ ΠΊ элСмСнтам ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ. Π˜Π³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ этих особСнностСй часто ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ ошибкам выполнСния ΠΈΠ»ΠΈ нСпрСдсказуСмому повСдСнию ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹. ПониманиС Ρ€Π°Π·Π½ΠΈΡ†Ρ‹ ΠΌΠ΅ΠΆΠ΄Ρƒ прямым доступом ΠΏΠΎ индСксу ΠΈ использованиСм ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ Π²Π°ΠΌ ΠΏΠΈΡΠ°Ρ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ Π½Π°Π΄Π΅ΠΆΠ½Ρ‹ΠΉ ΠΈ ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅ΠΌΡ‹ΠΉ ΠΊΠΎΠ΄.

Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π° динамичСских ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΉ Π² 1Π‘

ΠŸΡ€Π΅ΠΆΠ΄Π΅ Ρ‡Π΅ΠΌ ΠΏΡ€ΠΈΡΡ‚ΡƒΠΏΠ°Ρ‚ΡŒ ΠΊ написанию Ρ†ΠΈΠΊΠ»ΠΎΠ², Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Ρ‡Π΅Ρ‚ΠΊΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ, с ΠΊΠ°ΠΊΠΈΠΌ Ρ‚ΠΈΠΏΠΎΠΌ Π΄Π°Π½Π½Ρ‹Ρ… Π²Ρ‹ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚Π΅. Π’ 1Π‘ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ распространСнными динамичСскими структурами ΡΠ²Π»ΡΡŽΡ‚ΡΡ БписокЗначСний ΠΈ Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Π₯отя внСшнС ΠΎΠ½ΠΈ ΠΏΠΎΡ…ΠΎΠΆΠΈ, внутрСнняя рСализация доступа ΠΊ элСмСнтам Ρƒ Π½ΠΈΡ… различаСтся, Ρ‡Ρ‚ΠΎ Π½Π°ΠΏΡ€ΡΠΌΡƒΡŽ влияСт Π½Π° Π²Ρ‹Π±ΠΎΡ€ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΎΠ±Ρ…ΠΎΠ΄Π°.

БписокЗначСний прСдставляСт собой упорядочСнный Π½Π°Π±ΠΎΡ€ элСмСнтов, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΈΠΌΠ΅Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, прСдставлСниС, ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΡƒ удалСния ΠΈ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ свойства. Доступ ΠΊ элСмСнту ΠΏΠΎ индСксу Π² этой структурС происходит быстро, ΠΎΠ΄Π½Π°ΠΊΠΎ вставка ΠΈΠ»ΠΈ ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠ΅ элСмСнтов Π² сСрСдинС списка ΠΌΠΎΠΆΠ΅Ρ‚ Ρ‚Ρ€Π΅Π±ΠΎΠ²Π°Ρ‚ΡŒ сдвига ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π­Ρ‚ΠΎ ΠΊΠ»ΡŽΡ‡Π΅Π²ΠΎΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ часто ΡƒΠΏΡƒΡΠΊΠ°ΡŽΡ‚ Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΈ.

Π’ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ простого списка, Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈΠΌΠ΅Π΅Ρ‚ Π±ΠΎΠ»Π΅Π΅ ΡΠ»ΠΎΠΆΠ½ΡƒΡŽ структуру с ΠΊΠΎΠ»ΠΎΠ½ΠΊΠ°ΠΌΠΈ ΠΈ строками. Π—Π΄Π΅ΡΡŒ Π²Π°ΠΆΠ½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π°Ρ‚ΡŒ ΠΎΠ±Ρ…ΠΎΠ΄ строк Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΈ ΠΎΠ±Ρ…ΠΎΠ΄ ΠΊΠΎΠ»ΠΎΠ½ΠΎΠΊ. Для строк справСдливо ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ: ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ доступ эффСктивнСС случайного. Если ваша Π·Π°Π΄Π°Ρ‡Π° Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ частого поиска ΠΏΠΎ ΠΊΠ»ΡŽΡ‡Ρƒ, Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, стоит Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ использованиС Π”Π΅Ρ€Π΅Π²ΠΎΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈΠ»ΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Ρ‚Π°Π±Π»ΠΈΡ† вмСсто цикличСского ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π°.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠŸΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с большими массивами Π΄Π°Π½Π½Ρ‹Ρ… (Π±ΠΎΠ»Π΅Π΅ 10 000 строк) ΠΈΠ·Π±Π΅Π³Π°ΠΉΡ‚Π΅ создания Π½ΠΎΠ²Ρ‹Ρ… ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ²-ΠΎΠ±Π΅Ρ€Ρ‚ΠΎΠΊ Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π°. Π­Ρ‚ΠΎ создаСт Π½Π°Π³Ρ€ΡƒΠ·ΠΊΡƒ Π½Π° сборщик мусора ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ Π½Π΅ΡΡ‚Π°Π±ΠΈΠ»ΡŒΠ½ΠΎΠΉ Ρ€Π°Π±ΠΎΡ‚Π΅ сСрвСра.

ΠšΠ»Π°ΡΡΠΈΡ‡Π΅ΡΠΊΠΈΠΉ Ρ†ΠΈΠΊΠ» ΠΏΠΎ индСксу: Π€ΠΎΡ€ ΠΈ Для КаТдого

Π‘Π°ΠΌΡ‹ΠΉ ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½Ρ‹ΠΉ способ ΠΏΠ΅Ρ€Π΅Π±Ρ€Π°Ρ‚ΡŒ список β€” ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ†ΠΈΠΊΠ» Для с счСтчиком ΠΎΡ‚ нуля Π΄ΠΎ количСства элСмСнтов минус ΠΎΠ΄ΠΈΠ½. Π­Ρ‚ΠΎΡ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π΄Π°Π΅Ρ‚ ΠΏΠΎΠ»Π½Ρ‹ΠΉ ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒ Π½Π°Π΄ Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ индСксом, Ρ‡Ρ‚ΠΎ ΡƒΠ΄ΠΎΠ±Π½ΠΎ, Ссли Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΎΠ±Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ ΠΊ сосСдним элСмСнтам ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Π΅ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΏΠΎ слоТному ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ.

Однако Ρƒ Ρ†ΠΈΠΊΠ»Π° Для Π΅ΡΡ‚ΡŒ ΡΠ΅Ρ€ΡŒΠ΅Π·Π½Ρ‹ΠΉ нСдостаток ΠΏΡ€ΠΈ ΠΌΠΎΠ΄ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ списка. Если Π²Ρ‹ удаляСтС элСмСнт Π² Ρ‚Π΅Π»Π΅ Ρ†ΠΈΠΊΠ»Π°, индСксы всСх ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… элСмСнтов ΡΠ΄Π²ΠΈΠ³Π°ΡŽΡ‚ΡΡ. Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΏΡ€ΠΎΠΏΡƒΡΡ‚ΠΈΡ‚ΡŒ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΡƒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ строки ΠΈΠ»ΠΈ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΎΡˆΠΈΠ±ΠΊΡƒ Π²Ρ‹Ρ…ΠΎΠ΄Π° Π·Π° Π³Ρ€Π°Π½ΠΈΡ†Ρ‹ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π°, Ссли Π½Π΅ скоррСктируСтС счСтчик Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ. Π­Ρ‚ΠΎ классичСская ошибка, с ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΡΡ‚Π°Π»ΠΊΠΈΠ²Π°ΡŽΡ‚ΡΡ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ.

Π‘ΠΎΠ»Π΅Π΅ бСзопасным ΠΈ ΠΏΡ€Π΅Π΄ΠΏΠΎΡ‡Ρ‚ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ для чтСния Π΄Π°Π½Π½Ρ‹Ρ… являСтся конструкция Для КаТдого. Она ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΎΡ€ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ автоматичСски управляСт ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠΌ ΠΊ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ элСмСнту. Π’Π°ΠΊΠΎΠΉ ΠΊΠΎΠ΄ Ρ‡ΠΈΡ‰Π΅, Ρ‡ΠΈΡ‚Π°Π±Π΅Π»ΡŒΠ½Π΅Π΅ ΠΈ ΠΌΠ΅Π½Π΅Π΅ ΠΏΠΎΠ΄Π²Π΅Ρ€ΠΆΠ΅Π½ ошибкам, связанным с Ρ€ΡƒΡ‡Π½Ρ‹ΠΌ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ индСксами.

  • πŸš€ Π¦ΠΈΠΊΠ» Для Π»ΡƒΡ‡ΡˆΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ, ΠΊΠΎΠ³Π΄Π° Π½ΡƒΠΆΠ΅Π½ доступ ΠΊ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΌΡƒ Π½ΠΎΠΌΠ΅Ρ€Ρƒ строки.
  • πŸ›‘οΈ ΠšΠΎΠ½ΡΡ‚Ρ€ΡƒΠΊΡ†ΠΈΡ Для КаТдого автоматичСски Π·Π°Ρ‰ΠΈΡ‰Π°Π΅Ρ‚ ΠΎΡ‚ ошибок Π²Ρ‹Ρ…ΠΎΠ΄Π° Π·Π° Π³Ρ€Π°Π½ΠΈΡ†Ρ‹ ΠΏΡ€ΠΈ Ρ‡Ρ‚Π΅Π½ΠΈΠΈ.
  • ⚠️ Никогда Π½Π΅ измСняйтС количСство элСмСнтов Π² ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π° Для КаТдого.
  • πŸ” Для слоТной Ρ„ΠΈΠ»ΡŒΡ‚Ρ€Π°Ρ†ΠΈΠΈ Π½Π° Π»Π΅Ρ‚Ρƒ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ списки вмСсто удалСния.
πŸ“Š Какой Ρ†ΠΈΠΊΠ» Π²Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚Π΅ Ρ‡Π°Ρ‰Π΅ всСго?
Для (ΠΏΠΎ индСксу)
Для КаТдого
Пока
НС знаю Ρ€Π°Π·Π½ΠΈΡ†Ρ‹

Π’Ρ‹Π±ΠΎΡ€ ΠΌΠ΅ΠΆΠ΄Ρƒ этими двумя ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Π°ΠΌΠΈ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π΄ΠΈΠΊΡ‚ΠΎΠ²Π°Ρ‚ΡŒΡΡ Π·Π°Π΄Π°Ρ‡Π΅ΠΉ. Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ просто вывСсти Π΄Π°Π½Π½Ρ‹Π΅ ΠΈΠ»ΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ расчСт Π±Π΅Π· измСнСния структуры списка, Для КаТдого β€” Π±Π΅Π·Π°Π»ΡŒΡ‚Π΅Ρ€Π½Π°Ρ‚ΠΈΠ²Π½Ρ‹ΠΉ Π»ΠΈΠ΄Π΅Ρ€ ΠΏΠΎ скорости написания ΠΈ бСзопасности ΠΊΠΎΠ΄Π°. Π’ случаях, ΠΊΠΎΠ³Π΄Π° Π»ΠΎΠ³ΠΈΠΊΠ° Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ удалСния элСмСнтов, ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΊΠ°Ρ€Π΄ΠΈΠ½Π°Π»ΡŒΠ½ΠΎ мСняСтся.

ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΠ° удалСния элСмСнтов Π²ΠΎ врСмя ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ

Битуация, ΠΊΠΎΠ³Π΄Π° Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΡ‚Ρ„ΠΈΠ»ΡŒΡ‚Ρ€ΠΎΠ²Π°Ρ‚ΡŒ список, удаляя нСподходящиС элСмСнты прямо Π² Ρ†ΠΈΠΊΠ»Π΅, являСтся ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· самых ΠΊΠΎΠ²Π°Ρ€Π½Ρ‹Ρ…. ΠŸΡ€ΠΈ использовании Ρ†ΠΈΠΊΠ»Π° Для ΠΎΡ‚ 0 Π΄ΠΎ ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ()-1, ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠ΅ элСмСнта ΠΏΠΎ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΌΡƒ индСксу сдвигаСт вСсь «хвост» списка Π²Π»Π΅Π²ΠΎ. Π‘Π»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ итСрация Π±Π΅Ρ€Π΅Ρ‚ индСкс + 1, фактичСски пропуская элСмСнт, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ сдвинулся Π½Π° мСсто ΡƒΠ΄Π°Π»Π΅Π½Π½ΠΎΠ³ΠΎ.

Π§Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ пропуска Π΄Π°Π½Π½Ρ‹Ρ…, Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ часто ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Β«ΠΊΠΎΡΡ‚Ρ‹Π»ΡŒΒ» Π² Π²ΠΈΠ΄Π΅ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½ΠΈΡ счСтчика Ρ†ΠΈΠΊΠ»Π° Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡ†Ρƒ послС удалСния. Π­Ρ‚ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚, Π½ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ ΠΊΠΎΠ΄ Π³Ρ€ΠΎΠΌΠΎΠ·Π΄ΠΊΠΈΠΌ ΠΈ Ρ‚Ρ€ΡƒΠ΄Π½ΠΎΡ‡ΠΈΡ‚Π°Π΅ΠΌΡ‹ΠΌ. БущСствуСт Π³ΠΎΡ€Π°Π·Π΄ΠΎ Π±ΠΎΠ»Π΅Π΅ элСгантноС ΠΈ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ β€” ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ».

Π˜Ρ‚Π΅Ρ€Π°Ρ†ΠΈΡ Π² ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠΌ порядкС (ΠΎΡ‚ ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ()-1 Π΄ΠΎ 0) ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡƒ сдвига индСксов. Когда Π²Ρ‹ удаляСтС элСмСнт с ΠΊΠΎΠ½Ρ†Π° ΠΈΠ»ΠΈ сСрСдины, индСксы элСмСнтов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΅Ρ‰Π΅ прСдстоит ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ (находящихся Π² Π½Π°Ρ‡Π°Π»Π΅ списка), Π½Π΅ ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ. Π­Ρ‚ΠΎ позволяСт бСзопасно ΡƒΠ΄Π°Π»ΡΡ‚ΡŒ любоС количСство строк Π±Π΅Π· Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ†ΠΈΠΈ счСтчика.

Для ИндСкс = Бписок.ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() - 1 По 0 Π¦ΠΈΠΊΠ»

Π­Π»Π΅ΠΌΠ΅Π½Ρ‚ = Бписок.ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ(ИндСкс);

Если НС Π£ΡΠ»ΠΎΠ²ΠΈΠ΅ΠŸΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ(Π­Π»Π΅ΠΌΠ΅Π½Ρ‚) Π’ΠΎΠ³Π΄Π°

Бписок.Π£Π΄Π°Π»ΠΈΡ‚ΡŒ(ИндСкс);

ΠšΠΎΠ½Π΅Ρ†Π•ΡΠ»ΠΈ;

ΠšΠΎΠ½Π΅Ρ†Π¦ΠΈΠΊΠ»Π°;

πŸ’‘

ΠŸΡ€ΠΈ ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠΈ элСмСнтов ΠΈΠ· списка всСгда ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» (ΠΎΡ‚ ΠΊΠΎΠ½Ρ†Π° ΠΊ Π½Π°Ρ‡Π°Π»Ρƒ). Π­Ρ‚ΠΎ ΠΈΡΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚ΠΈΡ€ΠΎΠ²ΠΊΠΈ индСкса ΠΈ ΠΏΡ€Π΅Π΄ΠΎΡ‚Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ пропуск строк.

Π•Ρ‰Π΅ ΠΎΠ΄ΠΈΠ½ Π²Π°ΠΆΠ½Ρ‹ΠΉ аспСкт β€” ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ удалСния. Π£Π΄Π°Π»Π΅Π½ΠΈΠ΅ элСмСнта ΠΈΠ· Π½Π°Ρ‡Π°Π»Π° списка (индСкс 0) Π² структурС Ρ‚ΠΈΠΏΠ° массива ΠΈΠ»ΠΈ списка Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ сдвига всСх ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Ρ… элСмСнтов. Если Π²Ρ‹ удаляСтС ΠΌΠ½ΠΎΠ³ΠΎ строк Π² прямом Ρ†ΠΈΠΊΠ»Π΅, ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ становится ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ. ΠžΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠ΅Ρ‚ количСство сдвигов, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ удалСния происходят прСимущСствСнно Π² ΠΊΠΎΠ½Ρ†Π΅ ΠΈΠ»ΠΈ сСрСдинС, Π½Π΅ затрагивая Π΅Ρ‰Π΅ Π½Π΅ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Π½Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅.

ΠžΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΏΡ€ΠΈ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… ΠΎΠ±ΡŠΠ΅ΠΌΠ°Ρ…

Когда количСство строк Π² спискС исчисляСтся дСсятками тысяч, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ лишний Π²Ρ‹Π·ΠΎΠ² ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΠΈΠ»ΠΈ созданиС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π° суммируСтся Π² Π·Π°ΠΌΠ΅Ρ‚Π½Ρ‹Π΅ Π·Π°Π΄Π΅Ρ€ΠΆΠΊΠΈ. ΠŸΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° 1Π‘ ΠΈΠΌΠ΅Π΅Ρ‚ свои особСнности Ρ€Π°Π±ΠΎΡ‚Ρ‹ с ΠΏΠ°ΠΌΡΡ‚ΡŒΡŽ, ΠΈ нСэффСктивный ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΡŽ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния запроса Π² Ρ€Π°Π·Ρ‹.

Одной ΠΈΠ· распространСнных ошибок являСтся ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΠ΅ ΠΊ свойствам ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π²Π½ΡƒΡ‚Ρ€ΠΈ условия Ρ†ΠΈΠΊΠ»Π°. НапримСр, запись Для i = 0 По Бписок.ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ() Π¦ΠΈΠΊΠ» заставляСт систСму Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡ‚ΡŒ количСство элСмСнтов Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ. Π₯отя ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ‚ΠΎΡ€ 1Π‘ часто справляСтся с этим, явноС сохранСниС количСства Π² ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ ΠΏΠ΅Ρ€Π΅Π΄ Ρ†ΠΈΠΊΠ»ΠΎΠΌ являСтся ΠΏΡ€Π°Π²ΠΈΠ»ΠΎΠΌ Ρ…ΠΎΡ€ΠΎΡˆΠ΅Π³ΠΎ Ρ‚ΠΎΠ½Π° ΠΈ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ отсутствиС Π»ΠΈΡˆΠ½ΠΈΡ… вычислСний.

Π’Π°ΠΊΠΆΠ΅ стоит ΠΈΠ·Π±Π΅Π³Π°Ρ‚ΡŒ получСния элСмСнта ΠΏΠΎ индСксу, Ссли это ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΎΡ€. ΠœΠ΅Ρ‚ΠΎΠ΄ ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ(ИндСкс) ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅, Ρ‡Π΅ΠΌ нСпосрСдствСнноС использованиС ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Ρ†ΠΈΠΊΠ»Π° Π² конструкции Для КаТдого, особСнно для слоТных Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… структур. Если ΠΆΠ΅ индСкс Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌ, ΡƒΠ±Π΅Π΄ΠΈΡ‚Π΅ΡΡŒ, Ρ‡Ρ‚ΠΎ Π²Ρ‹ Π½Π΅ Π²Ρ‹Π·Ρ‹Π²Π°Π΅Ρ‚Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄ получСния элСмСнта Π΄Π²Π°ΠΆΠ΄Ρ‹ Π·Π° ΠΎΠ΄Π½Ρƒ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΡŽ.

ΠœΠ΅Ρ‚ΠΎΠ΄ доступа Π‘ΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ (ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ) Π‘Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΡΡ‚ΡŒ ΠΏΡ€ΠΈ ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠΈ РСкомСндация
Для КаТдого Высокая Низкая (нСльзя ΡƒΠ΄Π°Π»ΡΡ‚ΡŒ) Волько Ρ‡Ρ‚Π΅Π½ΠΈΠ΅ Π΄Π°Π½Π½Ρ‹Ρ…
Для (прямой) БрСдняя Низкая (Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ†ΠΈΠΈ) Доступ ΠΏΠΎ индСксу
Для (ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ) Высокая Высокая Π€ΠΈΠ»ΡŒΡ‚Ρ€Π°Ρ†ΠΈΡ с ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠ΅ΠΌ
Π€ΠΈΠ»ΡŒΡ‚Ρ€ + Копия БрСдняя Высокая БлоТная Π»ΠΎΠ³ΠΈΠΊΠ° ΠΎΡ‚Π±ΠΎΡ€Π°

Если список содСрТит 10-20 элСмСнтов, Ρ€Π°Π·Π½ΠΈΡ†Ρ‹ ΠΌΠ΅ΠΆΠ΄Ρƒ ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌΠΈ Π²Ρ‹ Π½Π΅ Π·Π°ΠΌΠ΅Ρ‚ΠΈΡ‚Π΅. Π€ΠΎΠΊΡƒΡΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒΡΡ Π½Π° микросСкундах стоит Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² Ρ‚Π΅Ρ… участках ΠΊΠΎΠ΄Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ часто ΠΈΠ»ΠΈ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°ΡŽΡ‚ большиС массивы Π΄Π°Π½Π½Ρ‹Ρ….

πŸ’‘

Π“Π»Π°Π²Π½Ρ‹ΠΉ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ: ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠΉΡ‚Π΅ количСство ΠΎΠ±Ρ€Π°Ρ‰Π΅Π½ΠΈΠΉ ΠΊ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρƒ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ‚Π΅Π»Π° Ρ†ΠΈΠΊΠ»Π° ΠΈ ΠΈΠ·Π±Π΅Π³Π°ΠΉΡ‚Π΅ создания Π½ΠΎΠ²Ρ‹Ρ… ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ.

ΠΠ»ΡŒΡ‚Π΅Ρ€Π½Π°Ρ‚ΠΈΠ²Π½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ„ΠΈΠ»ΡŒΡ‚Ρ€Π°Ρ†ΠΈΠΈ ΠΈ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ

Иногда Ρ†ΠΈΠΊΠ» Π²ΠΎΠΎΠ±Ρ‰Π΅ Π½Π΅ Π½ΡƒΠΆΠ΅Π½. ΠŸΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° 1Π‘ прСдоставляСт ΠΌΠΎΡ‰Π½Ρ‹Π΅ встроСнныС ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с коллСкциями, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Ρ‹ Π½Π° ΡƒΡ€ΠΎΠ²Π½Π΅ ядра ΠΈ Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ быстрСС любого ΠΊΠΎΠ΄Π° Π½Π° встроСнном языкС. ИспользованиС этих ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² Π΄Π΅Π»Π°Π΅Ρ‚ ΠΊΠΎΠ΄ Π»Π°ΠΊΠΎΠ½ΠΈΡ‡Π½Ρ‹ΠΌ ΠΈ сниТаСт Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ ошибок.

Для Ρ‚ΠΈΠΏΠ° Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ сущСствуСт ΠΌΠ΅Ρ‚ΠΎΠ΄ Π€ΠΈΠ»ΡŒΡ‚Ρ€, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ позволяСт ΠΎΡ‚ΠΎΠ±Ρ€Π°Ρ‚ΡŒ Π½ΡƒΠΆΠ½Ρ‹Π΅ строки ΠΏΠΎ ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ Π±Π΅Π· явного ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π°. Аналогично, для БписокЗначСний ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠžΡ‚Ρ„ΠΈΠ»ΡŒΡ‚Ρ€ΠΎΠ²Π°Ρ‚ΡŒ. Π­Ρ‚ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ internally ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ часто ΠΎΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ быстрСС Ρ€ΡƒΡ‡Π½ΠΎΠ³ΠΎ Ρ†ΠΈΠΊΠ»Π°, особСнно Ссли условиС Ρ„ΠΈΠ»ΡŒΡ‚Ρ€Π°Ρ†ΠΈΠΈ простоС.

Если Π»ΠΎΠ³ΠΈΠΊΠ° ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ слоТная ΠΈ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½Π° ΠΎΠ΄Π½ΠΈΠΌ условиСм, Ρ…ΠΎΡ€ΠΎΡˆΠΈΠΌ ΠΏΠ°Ρ‚Ρ‚Π΅Ρ€Π½ΠΎΠΌ являСтся созданиС Π½ΠΎΠ²ΠΎΠ³ΠΎ списка. ВмСсто удалСния элСмСнтов ΠΈΠ· старого, Π²Ρ‹ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚Π΅ ΠΏΠΎ Π½Π΅ΠΌΡƒ Π² прямом Ρ†ΠΈΠΊΠ»Π΅ (бСзопасно для чтСния) ΠΈ добавляСтС подходящиС элСмСнты Π² Π½ΠΎΠ²ΡƒΡŽ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΡŽ. ПослС Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ Ρ†ΠΈΠΊΠ»Π° Π²Ρ‹ просто замСняСтС ссылку Π½Π° старый список Π½ΠΎΠ²ΠΎΠΉ.

  • βœ… Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ встроСнный ΠΌΠ΅Ρ‚ΠΎΠ΄ НайтиБтроки для поиска вмСсто Ρ†ΠΈΠΊΠ»Π° ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π°.
  • βœ… ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΠΉΡ‚Π΅ Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠ΅Ρ€Π΅Π΄ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΎΠΉ, Ссли Π²Π°ΠΆΠ΅Π½ порядок Π΄Π°Π½Π½Ρ‹Ρ….
  • ❌ Π˜Π·Π±Π΅Π³Π°ΠΉΡ‚Π΅ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Ρ†ΠΈΠΊΠ»ΠΎΠ², Ссли ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ соСдинСния Ρ‚Π°Π±Π»ΠΈΡ† ΠΈΠ»ΠΈ индСксы.
  • ⚑Methods like Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ or Π£ΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡŒ are faster than loops for bulk operations.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ВстроСнныС ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Ρ„ΠΈΠ»ΡŒΡ‚Ρ€Π°Ρ†ΠΈΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π½Π΅ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ, Ссли условиС ΠΎΡ‚Π±ΠΎΡ€Π° Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π²Ρ‹Π·ΠΎΠ²Π° слоТных Π²Π½Π΅ΡˆΠ½ΠΈΡ… Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈΠ»ΠΈ обращСния ΠΊ Π±Π°Π·Π΅ Π΄Π°Π½Π½Ρ‹Ρ… для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ строки. Π’ Ρ‚Π°ΠΊΠΈΡ… случаях Ρ†ΠΈΠΊΠ» остаСтся СдинствСнным Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ.

Π‘Π΅ΠΊΡ€Π΅Ρ‚ быстрой Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π’Π°Π±Π»ΠΈΡ†Π΅ΠΉ Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ

Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ часто ΠΈΡΠΊΠ°Ρ‚ΡŒ строки ΠΏΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΌΡƒ полю, создайтС индСкс ΠΏΠΎ этому полю ΠΏΠ΅Ρ€Π΅Π΄ Π½Π°Ρ‡Π°Π»ΠΎΠΌ Ρ†ΠΈΠΊΠ»ΠΎΠ² поиска. Π­Ρ‚ΠΎ ускорит Ρ€Π°Π±ΠΎΡ‚Ρƒ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° НайтиБтроки Π² Ρ€Π°Π·Ρ‹.

ΠŸΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠΈΠ΅ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ ΠΈ Π»ΡƒΡ‡ΡˆΠΈΠ΅ ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠΈ

Рассмотрим Ρ‚ΠΈΠΏΠΈΡ‡Π½ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ: Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€ΠΎΠΉΡ‚ΠΈ ΠΏΠΎ списку Π½ΠΎΠΌΠ΅Π½ΠΊΠ»Π°Ρ‚ΡƒΡ€Ρ‹, ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ Ρ‚ΠΎΠ²Π°Ρ€Π° Π½Π° складС ΠΈ ΡƒΠ΄Π°Π»ΠΈΡ‚ΡŒ ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ, Π³Π΄Π΅ остаток Ρ€Π°Π²Π΅Π½ Π½ΡƒΠ»ΡŽ. РСализация Ρ‡Π΅Ρ€Π΅Π· прямой Ρ†ΠΈΠΊΠ» с ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠ΅ΠΌ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ ΠΊ ошибкС пропуска. РСализация Ρ‡Π΅Ρ€Π΅Π· ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» Ρ€Π΅ΡˆΠΈΡ‚ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡƒ, Π½ΠΎ ΠΊΠΎΠ΄ Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ Π½Π΅ΠΌΠ½ΠΎΠ³ΠΎ слоТнСС.

Π›ΡƒΡ‡ΡˆΠΈΠΌ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ΠΌ Π² Π΄Π°Π½Π½ΠΎΠΌ случаС, Ссли Π»ΠΎΠ³ΠΈΠΊΠ° ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ проста, Π±ΡƒΠ΄Π΅Ρ‚ использованиС Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΈΠ»ΠΈ Ρ„ΠΈΠ»ΡŒΡ‚Ρ€Π°. Однако, Ссли ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π²Ρ‹Π·ΠΎΠ²Π° Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒΠžΡΡ‚Π°Ρ‚ΠΊΠΈΠ’ΠΎΠ²Π°Ρ€Π°(), которая Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ, Ρ‚ΠΎ ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» ΠΏΠΎ БпискуЗначСний Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΌΡ‹ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠ΅ΠΌ количСство ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ измСнСния структуры Π΄Π°Π½Π½Ρ‹Ρ….

ВсСгда ΡΡ‚Ρ€Π΅ΠΌΠΈΡ‚Π΅ΡΡŒ ΠΊ Ρ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ‚Π΅Π»ΠΎ Ρ†ΠΈΠΊΠ»Π° выполняло ΠΌΠΈΠ½ΠΈΠΌΡƒΠΌ дСйствий. ВынСситС всС ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ, объявлСния ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… ΠΈ статичСскиС расчСты Π·Π° ΠΏΡ€Π΅Π΄Π΅Π»Ρ‹ Ρ†ΠΈΠΊΠ»Π°. Если Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π° Π΅ΡΡ‚ΡŒ Π²Π΅Ρ‚Π²Π»Π΅Π½ΠΈΠ΅ Если, ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡŒΡ‚Π΅ условиС Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ вСроятного исхода ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠΊΡ€Π°Ρ‚ΠΈΡ‚ΡŒ количСство ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΎΠΊ.

// ΠŸΠ»ΠΎΡ…ΠΎΠΉ ΠΏΡ€ΠΈΠΌΠ΅Ρ€: созданиС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Π° Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π°

Для КаТдого Π­Π»Π΅ΠΌΠ΅Π½Ρ‚ Из Бписок Π¦ΠΈΠΊΠ»

ΠΠΎΠ²Ρ‹ΠΉΠžΠ±ΡŠΠ΅ΠΊΡ‚ = Новый Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π°;

//.. Ρ€Π°Π±ΠΎΡ‚Π°

ΠšΠΎΠ½Π΅Ρ†Π¦ΠΈΠΊΠ»Π°;

// Π₯ΠΎΡ€ΠΎΡˆΠΈΠΉ ΠΏΡ€ΠΈΠΌΠ΅Ρ€: ΠΏΠ΅Ρ€Π΅ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΠ΅

Для КаТдого Π­Π»Π΅ΠΌΠ΅Π½Ρ‚ Из Бписок Π¦ΠΈΠΊΠ»

ΠžΠ±ΡŠΠ΅ΠΊΡ‚.ΠžΡ‡ΠΈΡΡ‚ΠΈΡ‚ΡŒ();

//.. Ρ€Π°Π±ΠΎΡ‚Π°

ΠšΠΎΠ½Π΅Ρ†Π¦ΠΈΠΊΠ»Π°;

β˜‘οΈ Π§Π΅ΠΊ-лист ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Ρ†ΠΈΠΊΠ»Π°

Π’Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ: 0 / 4

Часто Π·Π°Π΄Π°Π²Π°Π΅ΠΌΡ‹Π΅ вопросы (FAQ)

МоТно Π»ΠΈ Π΄ΠΎΠ±Π°Π²Π»ΡΡ‚ΡŒ элСмСнты Π² список Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π° «Для КаТдого»?

ВСхничСски ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ΡŒ это ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ, Π½ΠΎ это ΠΊΡ€Π°ΠΉΠ½Π΅ опасно. Π”ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ элСмСнта измСняСт Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΡŽΡŽ структуру ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ±ΠΈΡ‚ΡŒ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΎΡ€, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ Π»ΠΈΠ±ΠΎ ΠΊ Π·Π°Ρ†ΠΈΠΊΠ»ΠΈΠ²Π°Π½ΠΈΡŽ (бСсконСчный Ρ†ΠΈΠΊΠ»), Π»ΠΈΠ±ΠΎ ΠΊ пропуску элСмСнтов, Π»ΠΈΠ±ΠΎ ΠΊ ошибкС выполнСния. Никогда Π½Π΅ измСняйтС Ρ€Π°Π·ΠΌΠ΅Ρ€ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΈ ΠΏΡ€ΠΈ использовании ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΎΡ€Π°.

Π§Ρ‚ΠΎ быстрСС: Ρ†ΠΈΠΊΠ» «Для» ΠΈΠ»ΠΈ «Для КаТдого»?

Для ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ чтСния Ρ€Π°Π·Π½ΠΈΡ†Π° ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ negligible (Π½Π΅Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½Π°), Π° ΠΈΠ½ΠΎΠ³Π΄Π° «Для КаТдого» Π΄Π°ΠΆΠ΅ быстрСС Π·Π° счСт ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΠΎΡ€Π°. Однако Ρ†ΠΈΠΊΠ» «Для» Π²Ρ‹ΠΈΠ³Ρ€Ρ‹Π²Π°Π΅Ρ‚, ΠΊΠΎΠ³Π΄Π° Π½ΡƒΠΆΠ΅Π½ доступ ΠΊ индСксу Π±Π΅Π· Π²Ρ‹Π·ΠΎΠ²Π° ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ. ΠŸΡ€ΠΈ ΡƒΠ΄Π°Π»Π΅Π½ΠΈΠΈ элСмСнтов ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» «Для» являСтся СдинствСнным бСзопасным ΠΈ быстрым Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠΌ.

Как ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ список, Ссли условиС удалСния зависит ΠΎΡ‚ ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅ΠΉ строки?

Π’ этом случаС ΠΎΠ±Ρ€Π°Ρ‚Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π΅ΡƒΠ΄ΠΎΠ±Π΅Π½, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ «прСдыдущая» строка находится Π² ΠΊΠΎΠ½Ρ†Π΅ Π½Π΅ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Π½Π½ΠΎΠΉ части. Π›ΡƒΡ‡ΡˆΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Ρ†ΠΈΠΊΠ» Пока с Ρ€ΡƒΡ‡Π½Ρ‹ΠΌ ΡƒΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ индСксом, Π»ΠΈΠ±ΠΎ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ копию списка для Π°Π½Π°Π»ΠΈΠ·Π°, Π° ΡƒΠ΄Π°Π»ΡΡ‚ΡŒ ΠΈΠ· ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»Π°. Π’Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Ρ…Ρ€Π°Π½ΠΈΡ‚ΡŒ индСкс ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅Π³ΠΎ элСмСнта Π² ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ.

ΠŸΠΎΡ‡Π΅ΠΌΡƒ ΠΊΠΎΠ΄ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ Π½Π° тСстовой Π±Π°Π·Π΅, Π½ΠΎ Ρ‚ΠΎΡ€ΠΌΠΎΠ·ΠΈΡ‚ Π½Π° ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ?

Π‘ΠΊΠΎΡ€Π΅Π΅ всСго, Π½Π° ΠΏΡ€ΠΎΠ΄ΡƒΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π±Π°Π·Π΅ объСм Π΄Π°Π½Π½Ρ‹Ρ… Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ большС. АлгоритмичСская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ вашСго Ρ†ΠΈΠΊΠ»Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ (O(n^2)), Ρ‡Ρ‚ΠΎ Π½Π΅Π·Π°ΠΌΠ΅Ρ‚Π½ΠΎ Π½Π° 100 строках, Π½ΠΎ ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎ Π½Π° 100 000. ΠŸΡ€ΠΎΠ²Π΅Ρ€ΡŒΡ‚Π΅, Π½Π΅Ρ‚ Π»ΠΈ Ρƒ вас Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Ρ†ΠΈΠΊΠ»ΠΎΠ² ΠΈΠ»ΠΈ поиска Π²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΌΠ΅Π½ΠΈΡ‚ΡŒ Π½Π° ΠΈΠ½Π΄Π΅ΠΊΡΠ°Ρ†ΠΈΡŽ ΠΈΠ»ΠΈ ΠΏΡ€Π΅Π΄Π²Π°Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΡƒΡŽ Π·Π°Π³Ρ€ΡƒΠ·ΠΊΡƒ Π΄Π°Π½Π½Ρ‹Ρ… Π² ΡΠ»ΠΎΠ²Π°Ρ€ΡŒ.