{"id":29792,"date":"2022-05-16T17:21:00","date_gmt":"2022-05-16T15:21:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=29792"},"modified":"2024-11-27T15:12:06","modified_gmt":"2024-11-27T14:12:06","slug":"queue-implementieren-linked-list","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/queue-implementieren-linked-list\/","title":{"rendered":"Queue mit einer Linked List implementieren"},"content":{"rendered":"\n

Im letzten Teil dieser Tutorialserie habe ich dir gezeigt, wie man eine Queue mit Stacks implementiert<\/a>. In diesem Teil werden wir eine Queue mit einer verketteten Liste implementieren.<\/p>\n\n\n\n

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

Unsere Queue besteht aus zwei Referenzen auf Listenknoten: einer head<\/code>- und einer tail<\/code>-Referenz.<\/p>\n\n\n\n

Die head<\/code>-Referenz zeigt auf einen Listenknoten, der das vorderste Element der Queue enth\u00e4lt sowie einen next<\/code>-Zeiger auf einen zweiten Listenknoten. Dieser wiederum enth\u00e4lt das zweite Element und einen Zeiger auf den dritten Listenknoten, usw. <\/p>\n\n\n\n

Der letzte Knoten wird sowohl vom next<\/code>-Zeiger des vorletzten Elements als auch vom tail<\/code>-Zeiger referenziert. Er enth\u00e4lt das letzte Queue-Element, und dessen next<\/code>-Referenz zeigt auf null<\/code>.<\/p>\n\n\n\n

Die folgende Grafik zeigt eine Beispiel-Queue, in die die Elemente \"banana\", \"cherry\" und \"grape\" (in dieser Reihenfolge) eingef\u00fcgt wurden:<\/p>\n\n\n\n

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

Wie gelangen wir diesen Zustand?<\/p>\n\n\n\n

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

Wir beginnen mit einer leeren Queue. Sowohl head<\/code>- aus auch tail<\/code>-Referenz sind null<\/code>.<\/p>\n\n\n\n

\"Queue
Queue mit verketteter Liste: leere Queue<\/figcaption><\/figure><\/div>\n\n\n\n

Das erste Element f\u00fcgen wir in die Queue ein, indem wir es in einen Listenknoten wrappen und sowohl head<\/code> als auch tail<\/code> auf diesen Knoten zeigen lassen:<\/p>\n\n\n\n

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

Weitere Elemente f\u00fcgen wir wie folgt ein:<\/p>\n\n\n\n

  1. Wir wrappen das einzuf\u00fcgende Element in einem neuen Listenknoten.<\/li>
  2. Wir lassen den next<\/code>-Zeiger des letzten Knotens, also tail.next<\/code>, auf den neuen Knoten zeigen. <\/li>
  3. Wir lassen ebenso tail<\/code> auf den neuen Knoten zeigen.<\/li><\/ol>\n\n\n\n

    In der folgenden Grafik siehst du, wie ein zweites Element, \"cherry\", in die Beispiel-Queue eingef\u00fcgt wird:<\/p>\n\n\n\n

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

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

    Die Entnahme des Kopf-Elements mit dequeue()<\/code> funktioniert dann wie folgt:<\/p>\n\n\n\n

    1. Wir merken uns das Element des Knotens, auf den head<\/code> zeigt (im Beispiel w\u00e4re das \"banana\").<\/li>
    2. Wir lassen head<\/code> auf head.next<\/code> zeigen (im Beispiel auf den Knoten, der \"cherry\" wrappt). Falls head<\/code> danach null<\/code> sein sollte (die Queue also leer ist), setzen wir auch tail<\/code> auf null<\/code>. <\/li>
    3. Wir geben das in Schritt 1 gemerkte Element zur\u00fcck (im Beispiel \"banana\").<\/li>
    4. In einer Programmiersprache mit Garbage Collector (z. B. Java) l\u00f6scht dieser den nicht mehr referenzierten Knoten; in anderen Sprachen (wie C++) m\u00fcssten wir ihn manuell l\u00f6schen.<\/li><\/ol>\n\n\n\n

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

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

      Der gestrichelte Rahmen um den \"banana\"-Knoten in Schritt 2 und 3 soll darstellen, dass dieser Knoten zu diesem Zeitpunkt nicht mehr referenziert wird.<\/p>\n\n\n\n

      Quellcode f\u00fcr die Queue mit einer Linked List<\/h2>\n\n\n\n

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

      public<\/span> class<\/span> LinkedListQueue<\/span><E<\/span>> implements<\/span> Queue<\/span><E<\/span>> <\/span>{\n\n  private<\/span> Node<E> head;\n  private<\/span> Node<E> tail;\n\n  @Override<\/span>\n  public<\/span> void<\/span> enqueue<\/span>(E element)<\/span> <\/span>{\n    Node<E> newNode = new<\/span> Node<>(element);\n    if<\/span> (isEmpty()) {\n      head = tail = newNode;\n    } else<\/span> {\n      tail.next = newNode;\n      tail = newNode;\n    }\n  }\n\n  @Override<\/span>\n  public<\/span> E dequeue<\/span>()<\/span> <\/span>{\n    if<\/span> (isEmpty()) {\n      throw<\/span> new<\/span> NoSuchElementException();\n    }\n    E element = head.element;\n    head = head.next;\n    if<\/span> (head == null<\/span>) {\n      tail = null<\/span>;\n    }\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> head.element;\n  }\n\n  @Override<\/span>\n  public<\/span> boolean<\/span> isEmpty<\/span>()<\/span> <\/span>{\n    return<\/span> head == null<\/span>;\n  }\n\n  private<\/span> static<\/span> class<\/span> Node<\/span><E<\/span>> <\/span>{\n    final<\/span> E element;\n    Node<E> next;\n\n    Node(E element) {\n      this<\/span>.element = element;\n    }\n  }\n}\n<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
      Ausblick<\/h2>\n\n\n\n
      Im n\u00e4chsten Teil des Tutorials zeige ich dir, wie man eine Queue mit einem Array implementiert<\/a>.<\/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 eine Queue mit einer verketteten Liste (linked list)? Tutorial mit Grafiken + Java-Code-Beispielen<\/p>\n","protected":false},"author":1,"featured_media":29812,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_titles_title":"","_seopress_titles_desc":"Wie implementiert man eine Queue mit einer verketteten Liste (linked list)? Tutorial mit Grafiken + Java-Code-Beispielen","_seopress_robots_index":"","_seopress_robots_follow":"","_seopress_robots_imageindex":"","_seopress_robots_snippet":"","_seopress_robots_primary_cat":"none","_seopress_robots_breadcrumbs":"","_seopress_robots_freeze_modified_date":"","_seopress_robots_custom_modified_date":"","_seopress_robots_canonical":"","_seopress_social_fb_title":"","_seopress_social_fb_desc":"","_seopress_social_fb_img":"","_seopress_social_fb_img_attachment_id":0,"_seopress_social_fb_img_width":0,"_seopress_social_fb_img_height":0,"_seopress_social_twitter_title":"","_seopress_social_twitter_desc":"","_seopress_social_twitter_img":"","_seopress_social_twitter_img_attachment_id":0,"_seopress_social_twitter_img_width":0,"_seopress_social_twitter_img_height":0,"_seopress_redirections_value":"","_seopress_redirections_enabled":"","_seopress_redirections_enabled_regex":"","_seopress_redirections_logged_status":"both","_seopress_redirections_param":"","_seopress_redirections_type":301,"_seopress_analysis_target_kw":"queue mit einer linked list,queue mit einer verketteten liste,queue mit verketteter liste","_seopress_news_disabled":"","_seopress_video_disabled":"","_seopress_video":[],"_seopress_pro_schemas_manual":[{"_seopress_pro_rich_snippets_type":"none"}],"_seopress_pro_rich_snippets_disable_all":"","_seopress_pro_rich_snippets_disable":[],"_seopress_pro_schemas":[],"_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":4108,"_post_count":0,"footnotes":""},"categories":[127],"tags":[192],"class_list":["post-29792","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-queue"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-3481377-1770x986-1.jpg",1770,986,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 eine Queue mit einer verketteten Liste (linked list)? Tutorial mit Grafiken + Java-Code-Beispielen","public_identification_id":"35c8730273cb4e0dab2f5bea35204fab","private_identification_id":"550f284f629246b9a50b9444372ea09a","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29792","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=29792"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29792\/revisions"}],"predecessor-version":[{"id":30183,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/29792\/revisions\/30183"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/29812"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=29792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=29792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=29792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
      Wie du die LinkedListQueue<\/code>-Klasse einsetzen kannst, kannst du dir Demo-Programm QueueDemo<\/a> anschauen.<\/p>\n\n\n\n