{"id":28086,"date":"2022-03-16T17:24:26","date_gmt":"2022-03-16T16:24:26","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=28086"},"modified":"2024-11-27T15:12:47","modified_gmt":"2024-11-27T14:12:47","slug":"stack-implementieren-linked-list","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/stack-implementieren-linked-list\/","title":{"rendered":"Stack mit einer Linked List implementieren"},"content":{"rendered":"\n

Im vorangeganenen Teil haben wir einen Stack mit einem Array implementiert<\/a>. In diesem Teil zeige ich dir, wie du einen Stack mit einer einfach verketteten Liste programmierst.<\/p>\n\n\n\n

Der Algorithmus \u2013 Schritt f\u00fcr Schritt<\/h2>\n\n\n\n

Dies ist im Grunde ganz einfach: Eine top<\/code>-Referenz zeigt auf einen Knoten, der das oberste Element des Stacks enth\u00e4lt sowie einen next<\/code>-Zeiger auf den zweiten Knoten. Dieser wiederum enth\u00e4lt das zweite Element und einen Zeiger auf den dritten Knoten, usw. Der letzte Knoten enth\u00e4lt das unterste Element des Stacks; die next<\/code>-Referenz des letzten Knotens ist null<\/code>. <\/p>\n\n\n\n

Die folgende Grafik zeigt einen Beispiel-Stack, auf den die Elemente \"apple\", \"orange\" und \"pear\" (in dieser Reihenfolge) gepusht wurden:<\/p>\n\n\n\n

\"Stack
Stack mit einer verketteten Liste implementieren
<\/figcaption><\/figure><\/div>\n\n\n\n

Doch wie kommen wir dorthin?<\/p>\n\n\n\n

Enqueue-Algorithmus<\/h3>\n\n\n\n

Beginnen wir mit einem leeren Stack. Die top<\/code>-Referenz ist zun\u00e4chst null<\/code>:<\/p>\n\n\n\n

\"Stack
Stack mit verketteter Liste: leerer Stack<\/figcaption><\/figure><\/div>\n\n\n\n

Um das erste Element auf den Stack zu pushen, wrappen wir dieses in einen neuen Knoten und lassen top<\/code> auf diesen Knoten zeigen:<\/p>\n\n\n\n

\"Stack
Stack mit verketteter Liste: ein Element<\/figcaption><\/figure><\/div>\n\n\n\n

Jedes weitere Element f\u00fcgen wir zwischen top<\/code> und den ersten Knoten ein. Dazu brauchen wir drei Schritte:<\/p>\n\n\n\n

  1. Wir legen einen neuen Knoten an und wrappen damit das einzuf\u00fcgende Element.<\/li>
  2. Wir lassen die next<\/code>-Referenz des neuen Knotens auf denselben Knoten zeigen wie top<\/code>.<\/li>
  3. Wir lassen top<\/code> auf den neuen Knoten zeigen.<\/li><\/ol>\n\n\n\n

    Die folgende Grafik zeigt die drei Einf\u00fcge-Schritte:<\/p>\n\n\n\n

    \"Stack
    Stack mit verketteter Liste: Element einf\u00fcgen<\/figcaption><\/figure><\/div>\n\n\n\n

    Dequeue-Algorithmus<\/h3>\n\n\n\n

    Um ein Element mit pop()<\/code> wieder zu entnehmen, gehen wir wie folgt vor:<\/p>\n\n\n\n

    1. Wir merken uns das Element des Knotens, auf das top<\/code> zeigt (im Beispiel \"orange\").<\/li>
    2. Wir \u00e4ndern die top<\/code>-Referenz auf denjenigen Knoten auf den top.next<\/code> zeigt.<\/li>
    3. Wir geben das in Schritt 1 gemerkte Element zur\u00fcck.<\/li>
    4. In einer Sprache mit Garbage Collector (z. B. Java) sorgt dieser dann f\u00fcr das L\u00f6schen des nicht mehr referenzierten Knotens. In Sprachen ohne Garbage Collector (z. B. C++) m\u00fcssen wir das selbst tun.<\/li><\/ol>\n\n\n\n

      Die folgende Grafik zeigt die vier Schritte:<\/p>\n\n\n\n

      \"Stack
      Stack mit verketteter Liste: Element entnehmen<\/figcaption><\/figure><\/div>\n\n\n\n

      Der gestrichelte Rahmen um den \"orange\"-Knoten im zweiten und dritten Schritt soll andeuten, dass dieser Listenknoten nicht mehr referenziert wird.<\/p>\n\n\n\n

      Quellcode f\u00fcr den Stack mit einer Linked List<\/h2>\n\n\n\n

      Der folgende Quellcode zeigt die Implementierung des Stacks mit einer verketteten Liste (Klasse LinkedListStack<\/a> im GitHub-Repo). Die Klasse f\u00fcr die Knoten, Node<\/code>, findest du am Ende des Quellcodes als statische innere Klasse.<\/p>\n\n\n

      public<\/span> class<\/span> LinkedListStack<\/span><E<\/span>> implements<\/span> Stack<\/span><E<\/span>> <\/span>{\n\n  private<\/span> Node<E> top = null<\/span>;\n\n  @Override<\/span>\n  public<\/span> void<\/span> push<\/span>(E element)<\/span> <\/span>{\n    top = new<\/span> Node<>(element, top);\n  }\n\n  @Override<\/span>\n  public<\/span> E pop<\/span>()<\/span> <\/span>{\n    if<\/span> (isEmpty()) {\n      throw<\/span> new<\/span> NoSuchElementException();\n    }\n    E element = top.element;\n    top = top.next;\n    return<\/span> element;\n  }\n\n  @Override<\/span>\n  public<\/span> E peek<\/span>()<\/span> <\/span>{\n    if<\/span> (isEmpty()) {\n      throw<\/span> new<\/span> NoSuchElementException();\n    }\n    return<\/span> top.element;\n  }\n\n\n  @Override<\/span>\n  public<\/span> boolean<\/span> isEmpty<\/span>()<\/span> <\/span>{\n    return<\/span> top == null<\/span>;\n  }\n\n  private<\/span> static<\/span> class<\/span> Node<\/span><E<\/span>> <\/span>{\n    final<\/span> E element;\n    final<\/span> Node<E> next;\n\n    Node(E element, Node<E> next) {\n      this<\/span>.element = element;\n      this<\/span>.next = next;\n    }\n  }\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
      Vor- und Nachteile der Implementierung des Stacks mit einer Linked List<\/h2>\n\n\n\n
      Die Implementierung mit einer verketteten Liste hat gegen\u00fcber der Array-Variante den Vorteil, dass sie keinen Speicherplatz durch unbelegte Array-Felder verschwendet und dass sie keine Gr\u00f6\u00dfen\u00e4nderung des Arrays durch Kopieren des gesamten Arrays erfordert.<\/p>\n\n\n\n
      Die Knoten-Objekte wiederum belegen mehr Speicherplatz als ein einzelnes Feld in einem Array. Das Anlegen von Knoten-Objekten kostet mehr Zeit als das Setzen eines Array-Feldes. Eine verkettete Liste verursacht au\u00dferdem mehr Arbeit f\u00fcr den Garbage Collector, da dieser bei jedem Durchgang der kompletten Kette folgen muss.<\/p>\n\n\n\n
      In der Regel \u00fcberwiegen die Vorteile der Array-Implementierung, so dass diese h\u00e4ufiger anzutreffen ist.  <\/p>\n\n\n\n
      Ausblick<\/h2>\n\n\n\n
      Im n\u00e4chsten Teil des Tutorials zeige ich dir, wie man einen Stack mit einer Queue implementieren<\/a> kann.<\/p>\n\n\n\n
      Wenn du noch Fragen hast, stelle sie gerne \u00fcber die Kommentar-Funktion. M\u00f6chtest du \u00fcber neue Tutorials und Artikel informiert werden? Dann klicke hier<\/a>, um dich f\u00fcr den HappyCoders.eu-Newsletter anzumelden.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Wie implementiert man einen Stack mit einer verketteten Liste (\"linked list\")? Was sind die Vor- und Nachteile? Tutorial mit Grafiken und Java-Code-Beispielen.<\/p>\n","protected":false},"author":1,"featured_media":28553,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie implementiert man einen Stack mit einer verketteten Liste (linked list)? Was sind die Vor + Nachteile? Tutorial mit Grafiken + Java-Code-Beispielen","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":4414,"_post_count":0,"footnotes":""},"categories":[127],"tags":[191],"class_list":["post-28086","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-stack"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",1770,996,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",300,169,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",768,432,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",1024,576,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-224x126.jpg",224,126,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-336x189.jpg",336,189,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-504x284.jpg",504,284,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-672x378.jpg",672,378,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-400x225.jpg",400,225,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-600x338.jpg",600,338,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-800x450.jpg",800,450,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-944x531.jpg",944,531,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-1200x675.jpg",1200,675,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",1536,864,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/02\/bullion-932218.jpg",1770,996,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Wie implementiert man einen Stack mit einer verketteten Liste (\"linked list\")? Was sind die Vor- und Nachteile? Tutorial mit Grafiken und Java-Code-Beispielen.","public_identification_id":"5bbfe22f1f564fe3a974ba16f6e7cc71","private_identification_id":"45d0297c50234e1cb931f9071264d58f","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28086","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=28086"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28086\/revisions"}],"predecessor-version":[{"id":30202,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/28086\/revisions\/30202"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/28553"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=28086"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=28086"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=28086"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
      Wie die LinkedListStack<\/code>-Klasse eingesetzt wird, kannst du dir beispielhaft im Demo-Programm StackDemo<\/a> ansehen.<\/p>\n\n\n\n