1. Π‘ΠΏΠΈΡΠΎΠΊ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΉ
ΠΠ°ΠΊ ΡΡ ΠΌΠΎΠΆΠ΅ΡΡ ΠΏΠΎΠΌΠ½ΠΈΡΡ, Π² Java Π΅ΡΡΡ ΡΠ΄ΠΎΠ±Π½ΡΠΉ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½Ρ Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΡ ΡΠΈΠΏΠΎΠ² β ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ.
ΠΠΎΠΏΡΠΎΠ±ΡΠ΅ΠΌ Π²ΡΠΏΠΎΠΌΠ½ΠΈΡΡ ΠΎΡΠ½ΠΎΠ²Π½ΡΠ΅ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΉ:
List, Set, Map ΠΈ Queue.
ΠΠ°ΠΊ Π²ΠΎΠ΄ΠΈΡΡΡ, Π½Π΅Ρ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΠΈΠ»ΠΈ Π½Π΅ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΡΡ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½ΡΠΎΠ², Π΅ΡΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΈΡ ΠΏΠΎ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ. Π Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ ΠΌΡ Ρ ΡΠΎΠ±ΠΎΠΉ Π΄ΠΎΠ»ΠΆΠ½Ρ Ρ ΠΎΡΠΎΡΠ΅Π½ΡΠΊΠΎ ΡΠ°Π·ΠΎΠ±ΡΠ°ΡΡΡΡ Π² ΠΈΡ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΡΡ , ΡΡΠΎΠ±Ρ Π·Π½Π°ΡΡ, ΠΊΠΎΠ³Π΄Π° ΠΈ ΠΊΠ°ΠΊΡΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ.
1. List
ΠΠ°Π²Π°ΠΉ Π½Π°ΡΠ½Π΅ΠΌ Ρ ΡΠ°ΠΌΠΎΠΉ ΡΠ°ΡΡΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΉ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ.
List ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ ΡΡ ΠΎΠΆ Ρ ΡΠ°ΠΌΡΠΌ ΠΎΠ±ΡΡΠ½ΡΠΌ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠΌ. ΠΠ°Π·Π²Π°Π½ΠΈΠ΅ ΠΆΠ΅ Π½Π°ΠΌ Π³ΠΎΠ²ΠΎΡΠΈΡ ΠΎ ΡΠΎΠΌ, ΡΡΠΎ ΡΡΠΎ ΡΠΏΠΈΡΠΎΠΊ (list).
ΠΡΠ° ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡ Π΄Π°Π΅Ρ Π½Π°ΠΌ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΡΠ΄ΠΎΠ±Π½ΠΎ Ρ ΡΠ°Π½ΠΈΡΡ Π² ΡΠ΅Π±Π΅ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠΈΠΏΠ°, Π½Π΅ Π·Π°Π±ΠΎΡΡΡΡ ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ΅ ΡΠ°ΠΌΠΎΠΉ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ, ΠΊΠ°ΠΊ ΠΌΡ ΡΡΠΎ Π΄Π΅Π»Π°Π»ΠΈ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ ΠΌΠ°ΡΡΠΈΠ²Ρ. ΠΠ±ΡΠ°ΡΠ΅Π½ΠΈΠ΅ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ ΠΏΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ. ΠΡΠ»ΠΈ ΠΌΡ ΡΠΎΡΠ½ΠΎ Π·Π½Π°Π΅ΠΌ, Π½Π° ΠΊΠ°ΠΊΠΎΠΌ ΠΌΠ΅ΡΡΠ΅ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΠΎΠ±ΡΠ΅ΠΊΡ ΠΈ Π½Π°ΠΌ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠ°ΡΡΠΎ ΠΊ Π½Π΅ΠΌΡ ΠΎΠ±ΡΠ°ΡΠ°ΡΡΡΡ, ΠΏΡΠΈ ΡΡΠΎΠΌ Π½Π°ΠΌ Π½Π΅ Π½ΡΠΆΠ½ΠΎ ΡΠ°ΡΡΠΎ Π΄ΠΎΠ±Π°Π²Π»ΡΡΡ ΠΈΠ»ΠΈ ΡΠ΄Π°Π»ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, List β ΡΡΠΎ ΠΈΠ΄Π΅Π°Π»ΡΠ½ΡΠΉ Π²Π°ΡΠΈΠ°Π½Ρ.
2. Set
Set (ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ) ΠΈΠΌΠ΅Π΅Ρ ΡΠΎΠ²ΡΠ΅ΠΌ Π΄ΡΡΠ³ΡΡ ΡΡΡΡΠΊΡΡΡΡ.
Π ΠΏΠ΅ΡΠ²ΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ, Set ΡΡΠΎΠΈΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ, ΠΊΠΎΠ³Π΄Π° Π½Π°ΠΌ Π½ΡΠΆΠ½ΠΎ Ρ ΡΠ°Π½ΠΈΡΡ ΡΠ½ΠΈΠΊΠ°Π»ΡΠ½ΡΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΡ. ΠΠΎΠΏΡΡΡΠΈΠΌ, ΡΡΠΎ Π½Π°Π±ΠΎΡ Π°Π²ΡΠΎΡΠΎΠ² Π² Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅, Π³Π΄Π΅ ΠΊΠ°ΠΆΠ΄ΡΠΉ Π°Π²ΡΠΎΡ ΡΠ½ΠΈΠΊΠ°Π»Π΅Π½. ΠΠΎ ΠΌΡ Π½Π΅ ΠΌΠΎΠΆΠ΅ΠΌ ΠΏΡΠΎΡΡΠΎ ΡΠ°ΠΊ ΠΎΠ±ΡΠ°ΡΠΈΡΡΡΡ ΠΊ Π½Π°ΡΠ΅ΠΌΡ Π½Π°Π±ΠΎΡΡ Π°Π²ΡΠΎΡΠΎΠ² ΠΈ Π΄ΠΎΡΡΠ°ΡΡ ΠΈΠ· Π½Π΅Π³ΠΎ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΠΎΠ³ΠΎ Π°Π²ΡΠΎΡΠ°. Π€ΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π» Set-Π° Π΄Π°Π΅Ρ Π½Π°ΠΌ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ Π±ΡΡΡΡΠΎ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ, ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ Π»ΠΈ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΠΉ Π°Π²ΡΠΎΡ Π² Π½Π°ΡΠ΅ΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ Π΅Π³ΠΎ Π½Π°Π»ΠΈΡΠΈΠ΅ Π² ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ Set. Π’Π°ΠΊΠΆΠ΅ Π΅ΡΡΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΠΏΡΠΎΠΉΡΠΈΡΡ ΠΏΠΎ Π²ΡΠ΅ΠΉ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ, ΠΏΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, Π½ΠΎ ΡΡΠΎ Π½Π΅ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ.
Π’ΠΎ Π΅ΡΡΡ, Π² Π½Π°ΡΠ΅ΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅ Set ΠΌΠΎΠΆΠ΅Ρ ΡΠ»ΡΠΆΠΈΡΡ ΡΠ΅ΠΌ-ΡΠΎ Π²ΡΠΎΠ΄Π΅ Π½Π°Π±ΠΎΡΠ° Π²ΡΠ΅Ρ Π°Π²ΡΠΎΡΠΎΠ², Π΄Π»Ρ Π±ΡΡΡΡΠΎΠΉ ΠΏΡΠΎΠ²Π΅ΡΠΊΠΈ, ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ Π»ΠΈ ΡΡΠΎΡ Π°Π²ΡΠΎΡ Π² Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅.
3. Map
Map (ΡΠ»ΠΎΠ²Π°ΡΡ) Π±ΠΎΠ»ΡΡΠ΅ ΠΏΠΎΡ ΠΎΠΆΠ° Π½Π° ΠΊΠ°ΡΡΠΎΡΠ΅ΠΊΡ, Π³Π΄Π΅ ΠΊΠ°ΠΆΠ΄Π°Ρ ΡΡΠ΅ΠΉΠΊΠ° ΠΏΠΎΠ΄ΠΏΠΈΡΠ°Π½Π°, ΠΈ Π² Π½Π΅ΠΉ ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ Ρ ΡΠ°Π½ΠΈΡΡ ΠΊΠ°ΠΊ ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΡ, ΡΠ°ΠΊ ΠΈ ΡΠ΅Π»ΡΠ΅ ΡΡΡΡΠΊΡΡΡΡ. Map ΡΡΠΎΠΈΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π² ΡΠ»ΡΡΠ°ΡΡ , ΠΊΠΎΠ³Π΄Π° Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠΎΡ ΡΠ°Π½ΠΈΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΊ Π΄ΡΡΠ³ΠΎΠΌΡ.
Π Map ΡΡΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΊΠ»ΡΡ β Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅.
Π‘ ΡΠ°ΠΊΠΎΠΉ ΡΡΡΡΠΊΡΡΡΠΎΠΉ Π² Π½Π°ΡΠ΅ΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅ ΠΌΡ ΡΠΌΠΎΠΆΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΎΠ±ΡΠ΅ΠΊΡ Π°Π²ΡΠΎΡΠ° ΠΊΠ°ΠΊ ΠΊΠ»ΡΡ, Π° ΡΠΏΠΈΡΠΎΠΊ (List) ΠΊΠ½ΠΈΠ³ ΠΊΠ°ΠΊ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΏΡΠΎΠ²Π΅ΡΠΈΠ² Π² Set Π½Π°Π»ΠΈΡΠΈΠ΅ Π°Π²ΡΠΎΡΠ° Π² Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅, ΠΌΡ ΡΠΌΠΎΠΆΠ΅ΠΌ ΠΏΠΎ ΡΡΠΎΠΌΡ ΠΆΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΡ Π°Π²ΡΠΎΡΠ° Π΄ΠΎΡΡΠ°ΡΡ List Ρ Π΅Π³ΠΎ ΠΊΠ½ΠΈΠ³Π°ΠΌΠΈ ΠΈΠ· Map.
4. Queue
Queue (ΠΎΡΠ΅ΡΠ΅Π΄Ρ) β ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΡΡΡΠΎΠ΅Π½Π° ΠΊΠ°ΠΊ ΠΎΡΠ΅ΡΠ΅Π΄Ρ. ΠΡΠΈΡΠ΅ΠΌ ΡΡΠ° ΠΎΡΠ΅ΡΠ΅Π΄Ρ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ LIFO (Last In First Out β ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΉ Π·Π°ΡΠ΅Π», ΠΏΠ΅ΡΠ²ΡΠΉ Π²ΡΡΠ΅Π»), Π½ΠΎ ΠΈ FIFO (First In First Out β ΠΏΠ΅ΡΠ²ΡΠΉ Π·Π°ΡΠ΅ΠΉ, ΠΏΠ΅ΡΠ²ΡΠΉ Π²ΡΡΠ΅Π»). Π Π΅ΡΠ΅ ΠΎΡΠ΅ΡΠ΅Π΄Ρ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π΄Π²ΡΠ½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½Π°Ρ, Ρ Π²ΡΡ ΠΎΠ΄Π°ΠΌΠΈ Ρ ΠΎΠ±ΠΎΠΈΡ ΡΡΠΎΡΠΎΠ½.
ΠΡΠΎΡ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½Ρ ΡΠ΄ΠΎΠ±Π΅Π½ Π² ΡΠ»ΡΡΠ°ΡΡ , ΠΊΠΎΠ³Π΄Π° ΠΎΠ±ΡΠ΅ΠΊΡΡ, ΠΏΠΎΡΡΡΠΏΠ°ΡΡΠΈΠ΅ Π² Π½Π°Ρ ΠΊΠ»Π°ΡΡ, ΠΌΠ΅ΡΠΎΠ΄, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π² ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΠΈΡ ΠΏΠΎΡΡΡΠΏΠ»Π΅Π½ΠΈΡ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π² Π½Π°ΡΠ΅ΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅.
ΠΡ ΠΌΠΎΠΆΠ΅ΠΌ Π΄ΠΎΠ±Π°Π²Π»ΡΡΡ Π²Π½ΠΎΠ²Ρ ΠΏΡΠΈΠ±ΡΠ²ΡΠΈΡ ΠΏΠΎΡΠ΅ΡΠΈΡΠ΅Π»Π΅ΠΉ Π² Queue ΠΈ ΠΏΠΎ ΠΎΡΠ΅ΡΠ΅Π΄ΠΈ ΠΈΡ ΠΎΠ±ΡΠ»ΡΠΆΠΈΠ²Π°ΡΡ, Π²ΡΠ΄Π°Π²Π°Ρ ΠΊΠ½ΠΈΠ³ΠΈ, Π·Π° ΠΊΠΎΡΠΎΡΡΠΌΠΈ ΠΎΠ½ΠΈ ΠΊ Π½Π°ΠΌ ΠΏΡΠΈΡ ΠΎΠ΄ΡΡ.
ΠΠ°ΠΊ ΠΌΡ Ρ ΡΠΎΠ±ΠΎΠΉ ΠΌΠΎΠΆΠ΅ΠΌ Π²ΠΈΠ΄Π΅ΡΡ, Π²ΡΠ΅ ΡΡΡΡΠΊΡΡΡΡ Ρ ΠΎΡΠΎΡΠΈ, Π΅ΡΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΈΡ ΠΏΠΎ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ. Π Π² ΠΏΡΠ΅Π΄Π΅Π»Π°Ρ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ°, Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ, ΠΌΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π»ΠΈ Π²ΡΠ΅ ΡΠ΅ΡΡΡΠ΅ ΡΠΈΠΏΠ° ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΉ.
2. Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ
ΠΠ°ΠΊ ΡΠΆΠ΅ Π±ΡΠ»ΠΎ ΠΎΡΠΌΠ΅ΡΠ΅Π½ΠΎ, ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π»ΠΈ Π²ΡΡΠ΅, ΡΡΠΎ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΡ, Π° Π·Π½Π°ΡΠΈΡ Ρ Π½ΠΈΡ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΡ ΠΈ Π±ΡΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ.
ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π·Π°Π±ΠΈΠ²Π°ΡΡ Π³Π²ΠΎΠ·Π΄ΠΈ ΠΌΠΈΠΊΡΠΎΡΠΊΠΎΠΏΠΎΠΌ β Π½Π΅ ΡΠ°ΠΌΠ°Ρ Π»ΡΡΡΠ°Ρ ΠΈΠ΄Π΅Ρ, Π½Π°ΠΌ ΡΡΠΎΠΈΡ Π·Π½Π°ΡΡ, ΠΊΠ°ΠΊΡΡ ΠΈΠΌΠ΅Π½Π½ΠΎ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΈ Π»ΡΡΡΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π² ΡΠΎΠΉ ΠΈΠ»ΠΈ ΠΈΠ½ΠΎΠΉ ΡΠΈΡΡΠ°ΡΠΈΠΈ.
Π§Π°ΡΠ΅ Π²ΡΠ΅Π³ΠΎ, Π²ΡΠ±ΠΈΡΠ°Ρ ΡΠΎΡ ΠΈΠ»ΠΈ ΠΈΠ½ΠΎΠΉ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½Ρ, ΠΌΡ ΡΠΌΠΎΡΡΠΈΠΌ Π½Π° 2 ΠΏΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ:
- Π½Π°ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΡΠΎΡ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½Ρ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΠΈΡ ΠΏΠΎΠ΄ Π·Π°Π΄Π°ΡΡ
- Π½Π°ΡΠΊΠΎΠ»ΡΠΊΠΎ Π±ΡΡΡΡΠΎ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡΡ ΡΠ°Π±ΠΎΡΠ° Ρ Π½ΠΈΠΌ
ΠΡΠ»ΠΈ Ρ Π²ΡΠ±ΠΎΡΠΎΠΌ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ΅Π³ΠΎ ΠΏΠΎΠ΄ Π·Π°Π΄Π°ΡΡ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½ΡΠ° ΠΌΡ ΠΊΠΎΠ΅-ΠΊΠ°ΠΊ ΡΠ°Π·ΠΎΠ±ΡΠ°Π»ΠΈΡΡ, ΡΠΎ ΡΠΊΠΎΡΠΎΡΡΡ Π΅Π³ΠΎ ΡΠ°Π±ΠΎΡΡ β ΡΡΠΎ ΡΡΠΎ-ΡΠΎ Π½ΠΎΠ²Π΅Π½ΡΠΊΠΎΠ΅.
ΠΠΎΠΊΠ°Π·Π°ΡΠ΅Π»Ρ ΡΠΊΠΎΡΠΎΡΡΠΈ ΡΠ°Π±ΠΎΡΡ ΡΠ°ΡΡΠΎ Π²ΡΡΠ°ΠΆΠ°ΡΡ ΡΠ΅ΡΠ΅Π· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡ Π±ΠΎΠ»ΡΡΠΎΠΉ Π±ΡΠΊΠ²ΠΎΠΉ Π.
Π§ΡΠΎ Π²ΠΎΠΎΠ±ΡΠ΅ ΡΠ°ΠΊΠΎΠ΅ ΡΡΠ° Π²ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ?
ΠΡΠΎΡΡΡΠΌΠΈ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ, ΡΡΠ° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΠΊΠ°Π·ΡΠ²Π°Π΅Ρ Π½Π° Π²ΡΠ΅ΠΌΡ ΠΎΡΡΠ°Π±ΠΎΡΠΊΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, ΠΊΠΎΡΠΎΡΡΠΉ Π·Π°Π»ΠΎΠΆΠ΅Π½ Π² ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡ Π΄Π»Ρ ΡΠΎΠ³ΠΎ ΠΈΠ»ΠΈ ΠΈΠ½ΠΎΠ³ΠΎ Π΄Π΅ΠΉΡΡΠ²ΠΈΡ (Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅, ΡΠ΄Π°Π»Π΅Π½ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΏΠΎΠΈΡΠΊ).
ArrayList vs LinkedList
ΠΠ°Π²Π°ΠΉ ΡΠ°ΡΡΠΌΠΎΡΡΠΈΠΌ ΡΡΠΎ Π½Π° ΠΏΡΠΈΠΌΠ΅ΡΠ΅ Π΄Π²ΡΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΉ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΠ° List β ArrayList ΠΈ LinkedList.
Π§Π°ΡΡΠΈΡΠ½ΠΎ ΠΏΡΠΎ ΡΠ°Π·Π»ΠΈΡΠΈΠ΅ ΡΡΠΈΡ Π΄Π²ΡΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΉ ΡΠΏΠΎΠΌΠΈΠ½Π°Π΅ΡΡΡ Π² ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠ΅.
ΠΠ½Π΅ΡΠ½Π΅, ΡΠ°Π±ΠΎΡΠ° Ρ ΡΡΠΈΠΌΠΈ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΡΠΌΠΈ ΠΏΠΎΡ ΠΎΠΆΠ°:
List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
List<String> linkedList = new LinkedList<>();
linkedList.add(String);
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
ΠΠ°ΠΊ ΡΡ ΠΌΠΎΠ³ Π·Π°ΠΌΠ΅ΡΠΈΡΡ, Π² ΠΎΠ±ΠΎΠΈΡ ΡΠ»ΡΡΠ°ΡΡ ΠΌΡ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΠΌ, Π±Π΅ΡΠ΅ΠΌ ΠΈ ΡΠ΄Π°Π»ΡΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΈΠ· ΡΠΏΠΈΡΠΊΠ°. ΠΡΠΎ ΠΈΠ·-Π·Π° ΡΠΎΠ³ΠΎ, ΡΡΠΎ ΠΌΡ ΡΠΎΠ·Π΄Π°Π΅ΠΌ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ ΠΎΠ΄Π½ΠΎ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΠ°. ΠΠΎ Π½Π° ΡΡΠΎΠΌ ΡΡ ΠΎΠ΄ΡΡΠ²ΠΎ Ρ Π½ΠΈΡ Π·Π°ΠΊΠ°Π½ΡΠΈΠ²Π°Π΅ΡΡΡ.
ΠΠ»Π°Π³ΠΎΠ΄Π°ΡΡ ΡΠ°Π·Π½ΠΎΠΉ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡΠ° List ΡΡΠΈ Π΄Π²Π΅ ΡΡΡΡΠΊΡΡΡΡ ΠΈΠΌΠ΅ΡΡ ΡΠ°Π·Π½ΡΡ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΡ ΠΏΡΠΈ ΡΠ°Π·Π½ΠΎΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΏΡΠΈΠΌΠ΅Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°.
ΠΡΠ»ΠΈ Π½Π°ΠΌ Π½ΡΠΆΠ½ΠΎ Π±ΡΠ΄Π΅Ρ ΡΠ΄Π°Π»ΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΈΠ· ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ ΡΠΏΠΈΡΠΊΠ° ArrayList, ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ°Π· ΠΌΡ Π±ΡΠ΄Π΅ΠΌ ΠΏΠ΅ΡΠ΅ΠΏΠΈΡΡΠ²Π°ΡΡ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ ΡΠ°ΡΡΡ ΡΠΏΠΈΡΠΊΠ°, ΡΠ»Π΅Π΄ΡΡΡΡΡ Π·Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠΌ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΡ ΡΠ΄Π°Π»ΡΠ΅ΠΌ.
ΠΠΎΠΏΡΡΡΠΈΠΌ, Ρ Π½Π°Ρ Π΅ΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΈΠ· 5-ΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΈ Π½Π°ΠΌ Π½ΡΠΆΠ½ΠΎ ΡΠ΄Π°Π»ΠΈΡΡ 3-ΠΉ.
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
Π ΡΠ°ΠΊΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ Ρ Π½Π°Ρ ΠΎΡΠ²ΠΎΠ±ΠΎΠ΄ΠΈΡΡΡ ΠΎΠ΄Π½Π° ΡΡΠ΅ΠΉΠΊΠ°, ΠΈ ΠΌΡ Π±ΡΠ΄Π΅ΠΌ Π²ΡΠ½ΡΠΆΠ΄Π΅Π½Ρ ΠΏΠ΅ΡΠ΅Π·Π°ΠΏΠΈΡΠ°ΡΡ 4-ΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π½Π° ΠΌΠ΅ΡΡΠΎ 3-Π³ΠΎ, Π° 5-ΠΉ Π½Π° ΠΌΠ΅ΡΡΠΎ 4-Π³ΠΎ.
ΠΡΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ Π½Π΅ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ.
Π’ΠΎ ΠΆΠ΅ ΡΠ°ΠΌΠΎΠ΅ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡΡ ΠΈ ΠΏΡΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ ΡΠΏΠΈΡΠΊΠ°.
LinkedList ΠΆΠ΅ ΡΡΡΡΠΎΠ΅Π½ ΠΏΠΎ-Π΄ΡΡΠ³ΠΎΠΌΡ. ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ ΠΈΠ»ΠΈ ΡΠ΄Π°Π»Π΅Π½ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΈΠ· Π½Π΅Π³ΠΎ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ Π±ΡΡΡΡΠΎ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π½Π°ΠΌ Π²ΡΠ΅Π³ΠΎ Π»ΠΈΡΡ Π½ΡΠΆΠ½ΠΎ ΠΈΠ·ΠΌΠ΅Π½ΠΈΡΡ ΡΡΡΠ»ΠΊΠΈ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΌ ΠΈ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ΅, ΠΈΡΠΊΠ»ΡΡΠΈΠ² ΠΈΠ· ΡΠ΅ΠΏΠΎΡΠΊΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΎΠ±ΡΠ΅ΠΊΡ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΡ ΡΠ΄Π°Π»ΡΠ΅ΠΌ.
ΠΠ° ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΡΠΎΠ³ΠΎ ΠΆΠ΅ ΡΠΏΠΈΡΠΊΠ° ΠΈΠ· 5-ΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΡΠ΄Π°Π»ΠΈΠ² ΠΈΠ· Π½Π΅Π³ΠΎ 3-ΠΉ, ΠΌΡ Π΄ΠΎΠ»ΠΆΠ½Ρ ΠΏΡΠΎΡΡΠΎ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΡΡΡΠ»ΠΊΡ Π½Π° ΡΠ»Π΅Π΄ΡΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π²ΠΎ 2-ΠΌ ΠΈ ΡΡΡΠ»ΠΊΡ Π½Π° ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠΈΠΉ Π² 4-ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ΅.
Π’ΠΎ ΠΆΠ΅ ΡΠ°ΠΌΠΎΠ΅, ΡΠΎΠ»ΡΠΊΠΎ Π½Π°ΠΎΠ±ΠΎΡΠΎΡ, ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ ΠΏΡΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΠΏΠΈΡΠΎΠΊ.
ΠΠ±ΡΠ°ΡΠΈΡΠ΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, Π½Π°ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΌΠ΅Π½ΡΡΠ΅ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ Π½Π°ΠΌ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡΠΎΠΈΠ·Π²Π΅ΡΡΠΈ Π² LinkedList Π² ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΈ Ρ ArrayList. Π ΡΡΠΎ Π²ΡΠ΅Π³ΠΎ Π»ΠΈΡΡ 5 ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΡΠ΄Ρ Π² ΡΠΏΠΈΡΠΊΠ΅ 100 ΠΈ Π±ΠΎΠ»ΡΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΏΡΠ΅Π²ΠΎΡΡ ΠΎΠ΄ΡΡΠ²ΠΎ LinkedList Π±ΡΠ»ΠΎ Π±Ρ Π±ΠΎΠ»Π΅Π΅ ΠΎΡΡΡΠΈΠΌΠΎ.
ΠΠΎ ΠΊΠ°ΠΊ ΠΏΠΎΠΌΠ΅Π½ΡΠ΅ΡΡΡ ΡΠΈΡΡΠ°ΡΠΈΡ, Π΅ΡΠ»ΠΈ ΠΌΡ Π±ΡΠ΄Π΅ΠΌ ΠΎΠ±ΡΠ°ΡΠ°ΡΡΡΡ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΏΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ?
Π’ΡΡ Π²ΡΠ΅ Π±ΡΠ΄Π΅Ρ ΡΠΎΠ²Π½ΠΎ Π½Π°ΠΎΠ±ΠΎΡΠΎΡ.
Π’Π°ΠΊ ΠΊΠ°ΠΊ ArrayList ΡΡΡΡΠΎΠ΅Π½ ΠΊΠ°ΠΊ ΠΎΠ±ΡΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ², Π½Π°ΠΌ Π±ΡΠ΄Π΅Ρ ΠΎΡΠ΅Π½Ρ ΠΏΡΠΎΡΡΠΎ Π²Π·ΡΡΡ Π»ΡΠ±ΠΎΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠΎ Π΅Π³ΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ. ΠΡ ΠΏΡΠΎΡΡΠΎ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΡΠΈΠΌ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ ΠΌΠ΅ΡΡΠΎ ΠΈ Π²ΠΎΠ·ΡΠΌΠ΅ΠΌ ΠΈΠ· ΡΡΠ΅ΠΉΠΊΠΈ ΡΠ»Π΅ΠΌΠ΅Π½Ρ.
ΠΠΎ Π² LinkedList ΡΠ°ΠΊ ΠΏΡΠΎΡΡΠΎ Π½Π΅ ΠΏΠΎΠ»ΡΡΠΈΡΡΡ. ΠΠ°ΠΌ ΠΏΡΠΈΠ΄Π΅ΡΡΡ ΠΏΡΠΎΠΉΡΠΈΡΡ ΠΏΠΎ Π²ΡΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ ΠΌΠ°ΡΡΠΈΠ²Π°, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ. Π’ΠΎΠ»ΡΠΊΠΎ Π² Π΄Π°Π½Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΈΠΌΠ΅Π΅Ρ ΡΠΌΡΡΠ» Π½Π°Π·ΡΠ²Π°ΡΡ ΡΡΠΎ Π½Π΅ ΠΈΠ½Π΄Π΅ΠΊΡ, Π° ΠΏΠΎΡΡΠ΄ΠΊΠΎΠ²ΡΠΉ Π½ΠΎΠΌΠ΅Ρ.
ΠΠ°Π²Π°ΠΉ ΠΏΠΎΠΏΡΠΎΠ±ΡΠ΅ΠΌ Π²ΡΡΠ°Π·ΠΈΡΡ ΡΡΠΎ Π²ΡΠ΅ ΡΠ΅ΡΠ΅Π· Π±ΠΎΠ»ΡΡΡΡ Π?
ΠΠ°ΡΠ½Π΅ΠΌ Ρ ΠΎΠ±ΡΠ°ΡΠ΅Π½ΠΈΡ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΏΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ.
Π ArrayList ΡΡΠΎ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ Π² ΠΎΠ΄Π½ΠΎ Π΄Π΅ΠΉΡΡΠ²ΠΈΠ΅, Π²Π½Π΅ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ ΠΌΠ΅ΡΡΠΎΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΡΠΏΠΈΡΠΊΠ΅. Π Π½Π°ΡΠ°Π»Π΅ ΠΎΠ½ ΠΈΠ»ΠΈ Π² ΠΊΠΎΠ½ΡΠ΅.
ΠΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π² Π΄Π°Π½Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π±ΡΠ΄Π΅Ρ Π(1).
Π LinkedList Π½Π°ΠΌ ΠΏΡΠΈΠ΄Π΅ΡΡΡ ΠΏΠ΅ΡΠ΅Π±ΡΠ°ΡΡ ΡΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΈΠ½Π΄Π΅ΠΊΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π½Π°ΠΌ Π½ΡΠΆΠ΅Π½.
ΠΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π΄Π»Ρ ΡΠ°ΠΊΠΎΠ³ΠΎ Π΄Π΅ΠΉΡΡΠ²ΠΈΡ Π±ΡΠ΄Π΅Ρ Π(n) β Π³Π΄Π΅ n β ΡΡΠΎ ΠΈΠ½Π΄Π΅ΠΊΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΊΠΎΡΠΎΡΡΠΉ Π½Π°ΠΌ Π½ΡΠΆΠ΅Π½.
ΠΠΎΠ»ΡΡΠ°Π΅ΡΡΡ, ΠΏΠΎΠ΄ ΡΠΊΠΎΠ±ΠΊΠΈ Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ Π ΠΌΡ ΠΏΠΎΠΌΠ΅ΡΠ°Π΅ΠΌ ΡΠΈΡΠ»ΠΎ, ΠΊΠΎΡΠΎΡΠΎΠ΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΠΌΡΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ.
ΠΠ΅ΡΠ½Π΅ΠΌΡΡ ΠΊ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ?
ΠΠ°ΡΠ½Π΅ΠΌ Ρ LinkedList.
Π’Π°ΠΊ ΠΊΠ°ΠΊ Π½Π°ΠΌ Π½Π΅ Π½ΡΠΆΠ½ΠΎ Π΄Π΅Π»Π°ΡΡ Π±ΠΎΠ»ΡΡΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ Π΄Π»Ρ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ ΠΈΠ»ΠΈ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΈ ΡΠΊΠΎΡΠΎΡΡΡ ΡΡΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π½ΠΈΠΊΠ°ΠΊ Π½Π΅ Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ ΡΠΎΠ³ΠΎ, Π³Π΄Π΅ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, ΡΠ»ΠΎΠΆΠ½ΠΎ Π±ΡΠ΄Π΅Ρ Π²ΡΠ³Π»ΡΠ΄Π΅ΡΡ ΡΠ°ΠΊ β Π(1) ΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ½ΠΎΠΉ.
Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΡΠΎΠΉ ΠΆΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π΄Π»Ρ ArrayList Π±ΡΠ΄Π΅Ρ ΡΠΆΠ΅ Π(n) ΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ.
Π Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°Ρ Ρ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π½Π°ΠΏΡΡΠΌΡΡ Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΊΠΎΡΠΎΡΡΠ΅ ΠΏΡΠ΅Π΄ΡΡΠΎΠΈΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠ°ΡΡ. Π’Π°ΠΊΠΆΠ΅ ΡΡΠΎ ΠΌΠΎΠΆΠ΅Ρ Π·Π°Π²ΠΈΡΠ΅ΡΡ ΠΈ ΠΎΡ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, Π² Π½Π°ΡΠ°Π»Π΅ ΡΠΏΠΈΡΠΊΠ° ΠΈΠ»ΠΈ Π±Π»ΠΈΠΆΠ΅ ΠΊ ΠΊΠΎΠ½ΡΡ.
Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ Π΅ΡΠ΅ Π±ΡΠ²Π°Π΅Ρ Π»ΠΎΠ³Π°ΡΠΈΡΠΌΠΈΡΠ΅ΡΠΊΠΎΠΉ. ΠΡΠ³Π»ΡΠ΄ΠΈΡ ΠΎΠ½Π° Π²ΠΎΡ ΡΠ°ΠΊ β O(log n).
Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΡΠΈΠΌΠ΅ΡΠ° ΠΌΠΎΠΆΠ΅ΠΌ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅ΡΡ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ TreeSet ΡΠΏΠΈΡΠΎΠΊ ΠΈΠ· 10-ΡΠΈ ΡΠΈΡΠ΅Π», Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π½Π°ΠΌ Π½ΡΠΆΠ½ΠΎ Π½Π°ΠΉΡΠΈ ΡΠΈΡΠ»ΠΎ 2.
Π’Π°ΠΊ ΠΊΠ°ΠΊ ΡΠΏΠΈΡΠΎΠΊ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½ ΠΈ Π² Π½Π΅ΠΌ Π½Π΅Ρ Π΄ΡΠ±Π»ΠΈΠΊΠ°ΡΠΎΠ², ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ ΡΠ°Π·Π΄Π΅Π»ΠΈΡΡ Π΅Π³ΠΎ ΠΏΠΎΠΏΠΎΠ»Π°ΠΌ ΠΈ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ, Π² ΠΊΠ°ΠΊΠΎΠΉ ΡΠ°ΡΡΠΈ ΡΠΏΠΈΡΠΊΠ° ΠΎΡΡΠ°Π»ΠΎΡΡ ΠΈΡΠΊΠΎΠΌΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΠΎΡΠΊΠΈΠ½ΡΡΡ ΠΎΠ΄Π½Ρ ΠΈΠ· ΡΠ°ΡΡΠ΅ΠΉ ΠΈ ΠΏΠΎΠ²ΡΠΎΡΠΈΡΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΡ ΡΠ½ΠΎΠ²Π°, ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΠΉΠ΄Π΅ΠΌ Π΄ΠΎ ΠΈΡΠΊΠΎΠΌΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. Π ΠΈΡΠΎΠ³Π΅ ΠΌΡ Π½Π°ΠΉΠ΄Π΅ΠΌ ΡΠΈΡΠ»ΠΎ, ΠΎΠ±ΡΠ°Π±ΠΎΡΠ°Π² log(n) ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
ΠΠ°Π²Π°ΠΉ Π²Π·Π³Π»ΡΠ½Π΅ΠΌ Π½Π° ΡΠ°Π±Π»ΠΈΡΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΎΠΏΠΈΡΠ°Π½Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΉ.
ΠΠΎ ΠΈΠ½Π΄Π΅ΠΊΡΡ | ΠΠΎ ΠΊΠ»ΡΡΡ | ΠΠΎΠΈΡΠΊ | ΠΡΡΠ°Π²ΠΊΠ° Π² ΠΊΠΎΠ½Π΅Ρ | ΠΡΡΠ°Π²ΠΊΠ° Π² ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Ρ | Π£Π΄Π°Π»Π΅Π½ΠΈΠ΅ | |
---|---|---|---|---|---|---|
ArrayList | O(1) | N/A | Π(n) | O(1) | O(n) | O(n) |
LinkedList | O(n) | N/A | O(n) | O(1) | O(1) | O(1) |
HashSet | N/A | O(1) | O(1) | N/A | O(1) | O(1) |
TreeSet | N/A | O(1) | O(log n) | N/A | O(log n) | O(log n) |
HashMap | N/A | O(1) | O(1) | N/A | O(1) | O(1) |
TreeMap | N/A | O(1) | O(log n) | N/A | O(log n) | O(log n) |
ArrayDeque | N/A | N/A | O(n) | O(1) | O(1) | O(1) |
Π’Π΅ΠΏΠ΅ΡΡ, ΠΊΠΎΠ³Π΄Π° Ρ Π½Π°Ρ Ρ ΡΠΎΠ±ΠΎΠΉ Π΅ΡΡΡ ΡΠ°Π±Π»ΠΈΡΠ°, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠΊΠ°Π·Π°Π½Π° Π²ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π΄Π»Ρ ΠΏΠΎΠΏΡΠ»ΡΡΠ½ΡΡ ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΉ, ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ ΠΎΡΠ²Π΅ΡΠΈΡΡ Π½Π° Π²ΠΎΠΏΡΠΎΡ, ΠΏΠΎΡΠ΅ΠΌΡ ΠΈΠ· ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΊΠΎΠ»Π»Π΅ΠΊΡΠΈΠΉ ΠΌΡ ΡΠ°ΡΠ΅ Π²ΡΠ΅Π³ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌ ArrayList, HashSet ΠΈ HashMap.
ΠΠ½ΠΈ ΠΏΡΠΎΡΡΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½Ρ Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²Π° Π·Π°Π΄Π°Ρ :)