✔ einfach verkettete Liste -> Element löschen

[Shinzo]

Hallo,

ich beschäftige mich gerade mit Listen. Dazu meine Frage:

Ist ein O(1) Algorithmus möglich, bei dem man ein Element einer EINFACH verketteten Liste löschen kann, wenn man nur die Referenz auf das zu löschende Element besitzt, und dabei die Integrität der Liste beibehalten werden soll ?

Meiner Meinung nach ist nur ein O Algorithmus möglich, da man den Vorgänger garnicht kennt oder ? Man müsste sozusagen am Anfang der Liste beginnen und solange durchgehen bis man ein Element gefunden hat, das auf das zu löschende Element verweist.

Oder ist es doch irgendwie möglich

Danke im Voraus,
Mfg Shinzo

 

[Anime-Otaku]

Kommt drauf an...

Wenn du ein Element an einem bestimmten Index löschen willst, dann muss ja "nur" der vorher X in der Kette auf den nach X in der Kette zeigen. Daher O(1).

Wenn du aber nur sozusagen nur das Object hast, haben wir ein O, da wir ja keine Ahnung haben, wo in der Liste das Object ist und somit linear darüber iterieren müssen. Um hierbei schnell zu sein bräuchte man zum Beispiel ein (Linked)HashSet

(siehe LinkedList implementation im JRE)

 

[Shinzo]

Nein, ich meinte eher eine dynamische Liste.

Problem gelöst, danke für die Hilfe.