{"id":30436,"date":"2022-06-07T22:05:31","date_gmt":"2022-06-07T20:05:31","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=30436"},"modified":"2024-11-27T15:09:33","modified_gmt":"2024-11-27T14:09:33","slug":"linkedlist-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/linkedlist-java\/","title":{"rendered":"Java LinkedList als Deque (mit Beispiel)"},"content":{"rendered":"\n<p>In diesem Artikel erf\u00e4hrst du alles \u00fcber die Java-Klasse <code>LinkedList<\/code> in ihrer Rolle als Deque:<\/p>\n\n\n\n<ul class=\"hc-checked-list wp-block-list\"><li>Was sind die Eigenschaften von <code>LinkedList<\/code>?<\/li><li>Wann sollte man sie als Deque einsetzen?<\/li><li>Wie setzt man sie als Deque ein (Java-Beispiel)?<\/li><li>Welche Zeitkomplexit\u00e4ten haben die <code>LinkedList<\/code>-Operationen?<\/li><\/ul>\n\n\n\n<p>Wir befinden uns hier in der Klassenhierarchie:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-800x500.png\" alt=\"LinkedList in der Klassenhierarchie (UML-Klassendiagramm)\" class=\"wp-image-30533\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-944x590.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy-1200x750.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/java-LinkedList-class-hierarchy.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption>LinkedList in der Klassenhierarchie<\/figcaption><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"linkedlist-eigenschaften-als-deque\">LinkedList Eigenschaften als Deque<\/h2>\n\n\n\n<p>Die Klasse <code>java.util.LinkedList<\/code> implementiert eine klassische doppelt verkettete Liste.<\/p>\n\n\n\n<p>Sie existiert im JDK seit Version 1.2, also deutlich l\u00e4nger als das <a href=\"\/de\/algorithmen\/java-deque\/\">Deque-Interface<\/a>, das sie implementiert. Die Deque-spezifischen Methoden wurden mit Einf\u00fchrung von <code>Deque<\/code> in Java 6 hinzugef\u00fcgt.<\/p>\n\n\n\n<p>Die Eigenschaften im Detail:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes less-line-height\"><table class=\"has-fixed-layout\"><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Unterliegende Datenstruktur<\/th><th class=\"has-text-align-center\" data-align=\"center\">Thread-safe?<\/th><th class=\"has-text-align-center\" data-align=\"center\">Blocking\/<br>Non-blocking<\/th><th class=\"has-text-align-center\" data-align=\"center\">Bounded\/<br>Unbounded<\/th><th class=\"has-text-align-center\" data-align=\"center\">Iterator Type<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">Verkettete Liste<\/td><td class=\"has-text-align-center\" data-align=\"center\">Nein<\/td><td class=\"has-text-align-center\" data-align=\"center\">Non-blocking<\/td><td class=\"has-text-align-center\" data-align=\"center\">Unbounded<\/td><td class=\"has-text-align-center\" data-align=\"center\">Fail-fast\u00b9<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"hc-footnote\">\u00b9 Fail-fast: Der Iterator wirft eine <code>ConcurrentModificationException<\/code>, wenn w\u00e4hrend der Iteration Elemente in das Deque eingef\u00fcgt oder aus diesem entnommen werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"einsatzempfehlung-als-deque\">Einsatzempfehlung als Deque<\/h2>\n\n\n\n<p>Ich rate grunds\u00e4tzlich von der Verwendung der <code>LinkedList<\/code> als Deque ab. Die Gr\u00fcnde findest du im Artikel <a href=\"\/de\/algorithmen\/array-vs-linked-list\/\">Unterschied zwischen Array und Linked List<\/a>. Zusammengefasst:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Ein Array ben\u00f6tigt deutlich weniger Speicher als eine verkettete Liste.<\/li><li>Der Zugriff auf die Elemente eines Arrays ist schneller als auf die einer verketteten Liste.<\/li><li>Verkettete Listen sind f\u00fcr den Garbage Collector \"schwer verdaulich\".<\/li><\/ul>\n\n\n\n<p>Wenn du eine Liste ben\u00f6tigst, ist <code>ArrayList<\/code> meist die bessere Wahl.<\/p>\n\n\n\n<p>Wenn du eine nicht threadsicheres Deque (oder eine nicht threadsichere Queue) ben\u00f6tigst, dann verwende ein <a href=\"\/de\/algorithmen\/arraydeque-java\/\">ArrayDeque<\/a>.<\/p>\n\n\n\n<p>Das sind nat\u00fcrlich nur allgemeine Empfehlungen. Solltest du Gr\u00fcnde haben, die f\u00fcr den Einsatz einer <code>LinkedList<\/code> sprechen (wenn du z. B. haupts\u00e4chlich Elemente in der Mitte entnimmst und einf\u00fcgst \u2013 das allerdings nicht in der Rolle eines Deques), dann w\u00fcrde ich dir raten die Performance der <code>LinkedList<\/code> f\u00fcr deinen speziellen Anwendungsfall mit alternativen Datenstrukturen zu vergleichen. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"linkedlist-deque-beispiel\">LinkedList Deque Beispiel<\/h2>\n\n\n\n<p>Im folgenden Beispiel siehst du, wie man eine <code>LinkedList<\/code> in Java verwenden kann. Der Beispielcode zeigt, wie man eine LinkedList erstellt, wie man sie mit zuf\u00e4lligen Elemente bef\u00fcllt, wie man das Kopf- und Endelement ausgibt und wie man die Elemente letztlich wieder aus der <code>LinkedList<\/code> entnimmt.<\/p>\n\n\n\n<p>Falls du das <a href=\"\/de\/algorithmen\/arraydeque-java\/\">ArrayDeque-Tutorial<\/a> gelesen hast, d\u00fcrfte dir das Demo bekannt vorkommen. Da sowohl <code>ArrayDeque<\/code> als auch <code>LinkedList<\/code> non-blocking und nicht thread-safe sind, kann ich f\u00fcr beide Implementierungen nur die Deque-Grundfunktionen demonstrieren.<\/p>\n\n\n\n<p>Den Code findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/java-collections-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/demos\/deque\/LinkedListDemo.java\" target=\"_blank\" rel=\"noopener\">LinkedListDemo<\/a> im GitHub-Repo. <\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">LinkedListDemo<\/span> <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n    Deque&lt;Integer&gt; deque = <span class=\"hljs-keyword\">new<\/span> LinkedList&lt;&gt;();\n\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; <span class=\"hljs-number\">8<\/span>; i++) {\n      <span class=\"hljs-keyword\">int<\/span> element = ThreadLocalRandom.current().nextInt(<span class=\"hljs-number\">10<\/span>, <span class=\"hljs-number\">100<\/span>);\n      <span class=\"hljs-keyword\">if<\/span> (ThreadLocalRandom.current().nextBoolean()) {\n        deque.offerFirst(element);\n        System.out.println(<span class=\"hljs-string\">\"deque.offerFirst(\"<\/span> + element + <span class=\"hljs-string\">\") --&gt; deque = \"<\/span> + deque);\n      } <span class=\"hljs-keyword\">else<\/span> {\n        deque.offerLast(element);\n        System.out.println(<span class=\"hljs-string\">\"deque.offerLast(\"<\/span> + element + <span class=\"hljs-string\">\")  --&gt; deque = \"<\/span> + deque);\n      }\n    }\n\n    System.out.println();\n    System.out.println(<span class=\"hljs-string\">\"deque.isEmpty()   = \"<\/span> + deque.isEmpty());\n    System.out.println(<span class=\"hljs-string\">\"deque.peekFirst() = \"<\/span> + deque.peekFirst());\n    System.out.println(<span class=\"hljs-string\">\"deque.peekLast()  = \"<\/span> + deque.peekLast());\n    System.out.println();\n\n    <span class=\"hljs-keyword\">while<\/span> (!deque.isEmpty()) {\n      <span class=\"hljs-keyword\">if<\/span> (ThreadLocalRandom.current().nextBoolean()) {\n        System.out.println(<span class=\"hljs-string\">\"deque.pollFirst() = \"<\/span> + deque.pollFirst() \n            + <span class=\"hljs-string\">\" --&gt; deque = \"<\/span> + deque);\n      } <span class=\"hljs-keyword\">else<\/span> {\n        System.out.println(<span class=\"hljs-string\">\"deque.pollLast()  = \"<\/span> + deque.pollLast() \n            + <span class=\"hljs-string\">\" --&gt; deque = \"<\/span> + deque);\n      }\n    }\n\n    System.out.println();\n    System.out.println(<span class=\"hljs-string\">\"deque.isEmpty()   = \"<\/span> + deque.isEmpty());\n    System.out.println(<span class=\"hljs-string\">\"deque.peekFirst() = \"<\/span> + deque.peekFirst());\n    System.out.println(<span class=\"hljs-string\">\"deque.peekLast()  = \"<\/span> + deque.peekLast());\n  }\n}\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Hier eine beispielhafte Ausgabe:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">deque.offerLast(80)  --&gt; deque = &#091;80]\ndeque.offerLast(61)  --&gt; deque = &#091;80, 61]\ndeque.offerLast(63)  --&gt; deque = &#091;80, 61, 63]\ndeque.offerFirst(30) --&gt; deque = &#091;30, 80, 61, 63]\ndeque.offerLast(11)  --&gt; deque = &#091;30, 80, 61, 63, 11]\ndeque.offerLast(33)  --&gt; deque = &#091;30, 80, 61, 63, 11, 33]\ndeque.offerLast(30)  --&gt; deque = &#091;30, 80, 61, 63, 11, 33, 30]\ndeque.offerFirst(90) --&gt; deque = &#091;90, 30, 80, 61, 63, 11, 33, 30]\n\ndeque.isEmpty()   = false\ndeque.peekFirst() = 90\ndeque.peekLast()  = 30\n\ndeque.pollFirst() = 90 --&gt; deque = &#091;30, 80, 61, 63, 11, 33, 30]\ndeque.pollFirst() = 30 --&gt; deque = &#091;80, 61, 63, 11, 33, 30]\ndeque.pollFirst() = 80 --&gt; deque = &#091;61, 63, 11, 33, 30]\ndeque.pollFirst() = 61 --&gt; deque = &#091;63, 11, 33, 30]\ndeque.pollLast()  = 30 --&gt; deque = &#091;63, 11, 33]\ndeque.pollLast()  = 33 --&gt; deque = &#091;63, 11]\ndeque.pollLast()  = 11 --&gt; deque = &#091;63]\ndeque.pollFirst() = 63 --&gt; deque = &#091;]\n\ndeque.isEmpty()   = true\ndeque.peekFirst() = null\ndeque.peekLast()  = null\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Wenn du dir die Ausgabe Zeile f\u00fcr Zeile anschaust, wirst du die Funktionsweise der <code>LinkedList<\/code> gut nachvollziehen k\u00f6nnen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"linkedlist-zeitkomplexitaet\">LinkedList Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p><em>(Eine Einf\u00fchrung in das Thema Zeitkomplexit\u00e4t findest du im Artikel \"<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt<\/a>\".)<\/em><\/p>\n\n\n\n<p>Bei einer verketteten Liste spielt es f\u00fcr das Einf\u00fcgen und Entfernen von Elementen keine Rolle, wie lang die Liste bereits ist. Der Aufwand f\u00fcr beide Operationen ist somit konstant.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t f\u00fcr die Enqueue- und Dequeue-Operationen betr\u00e4gt somit: <em>O(1)<\/em><\/p>\n\n\n\n<p>Anders sieht es in der Regel f\u00fcr die Bestimmung der Gr\u00f6\u00dfe aus. Um die Elemente der verketteten Liste zu z\u00e4hlen, muss die Liste einmal komplett von vorne bis hinten durchlaufen werden.<\/p>\n\n\n\n<p>Gl\u00fccklicherweise ist das bei der Java <code>LinkedList<\/code> nicht der Fall. Diese speichert ihre Gr\u00f6\u00dfe in einem zus\u00e4tzlichen Feld und aktualisiert dieses Feld bei jeder Einf\u00fcge- und L\u00f6schoperation.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t f\u00fcr <code>LinkedList.size()<\/code> betr\u00e4gt also auch: <em>O(1)<\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung-und-ausblick\">Zusammenfassung und Ausblick<\/h2>\n\n\n\n<p>In diesem Artikel hast du alles \u00fcber die Deque-Implementierung <code>LinkedList<\/code> erfahren.<\/p>\n\n\n\n<p>Im n\u00e4chsten Teil dieser Serie kommen wir zur ersten threadsicheren Deque-Implementierung: dem <a href=\"\/de\/algorithmen\/concurrentlinkeddeque-java\/\">ConcurrentLinkedDeque<\/a>.<\/p>\n\n\n\n<p>Wenn du noch Fragen hast, stelle sie gerne \u00fcber die Kommentar-Funktion. M\u00f6chtest du \u00fcber neue Tutorials und Artikel informiert werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders.eu-Newsletter anzumelden.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Wie benutzt man die Java LinkedList als Deque? Wie funktioniert sie? Was sind ihre Eigenschaften? Wann sollte man sie als Deque einsetzen?<\/p>\n","protected":false},"author":1,"featured_media":30530,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie benutzt man die Java LinkedList als Deque? Wie funktioniert sie? Was sind ihre Eigenschaften? Wann sollte man sie als Deque einsetzen?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":6499,"_post_count":0,"footnotes":""},"categories":[127],"tags":[195],"class_list":["post-30436","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-deque"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/chain-498708-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 benutzt man die Java LinkedList als Deque? Wie funktioniert sie? Was sind ihre Eigenschaften? Wann sollte man sie als Deque einsetzen?","public_identification_id":"1cbf2dbebfc84f3a9a6e3bdf7b7e344b","private_identification_id":"1d3ba10db9c44076924fb9ca226abc8e","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/30436","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=30436"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/30436\/revisions"}],"predecessor-version":[{"id":31083,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/30436\/revisions\/31083"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/30530"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=30436"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=30436"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=30436"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}