{"id":17228,"date":"2022-07-05T11:43:00","date_gmt":"2022-07-05T09:43:00","guid":{"rendered":"https:\/\/www.valcon.it\/python\/?p=17228"},"modified":"2025-08-15T10:57:47","modified_gmt":"2025-08-15T08:57:47","slug":"classe-linked-list","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/python\/classe-linked-list\/","title":{"rendered":"Classe lista concatenata"},"content":{"rendered":"\n<p>La <em>lista concatenata<\/em> ha l&#8217;obiettivo di ottimizzare le operazioni di inserimento e di rimozione degli elementi<\/p>\n\n\n\n<ul>\n<li>Le informazioni sono salvate in <em>nodi<\/em><\/li>\n\n\n\n<li>Ogni nodo contiene un puntatore al prossimo nodo nella lista<\/li>\n\n\n\n<li>Alla lista si accede conoscendo il puntatore alla testa (al primo a sinistra)<\/li>\n<\/ul>\n\n\n\n<p>Realizza i metodi tradizionali per le strutture dati<\/p>\n\n\n\n<ul>\n<li><strong>append_right<\/strong>(x), aggiunge x a destra (in coda)<\/li>\n\n\n\n<li><strong>append_left<\/strong>(x), aggiunge x a sinistra (in testa)<\/li>\n\n\n\n<li>x &lt;&#8211; <strong>pop_right<\/strong>(), restituisce l&#8217;elemento in coda e lo elimina<\/li>\n\n\n\n<li>x &lt;&#8211; <strong>pop_left<\/strong>(), restituisce l&#8217;elemento in testa e lo elimina<\/li>\n\n\n\n<li>x &lt;&#8211; <strong>remove<\/strong>(x), elimina l&#8217;elemento x<\/li>\n\n\n\n<li><strong>is_empty<\/strong>(), la lista \u00e8 vuota?<\/li>\n\n\n\n<li><strong>size<\/strong>(), quanti elementi contiene?<\/li>\n\n\n\n<li><strong>count<\/strong>(x), quante volte \u00e8 presente x<\/li>\n\n\n\n<li><strong>index<\/strong>(x), a quale posizione \u00e8 presente x?<\/li>\n\n\n\n<li>&#8230;<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Classe nodo<\/h2>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nclass Node:\n    def __init__(self, info):\n        self._info=info\n        self._next=None\n\n    def set_info(self, info): \n        self._info=info\n    def get_info(self): \n        return self._info\n    def set_next(self, next): \n        self._next=next\n    def get_next(self): \n        return self._next\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Classe lista concatenata<\/h2>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nclass HL_List:\n    def __init__(self):\n        self._head=None\n\n    def is_empty(self):\n        return (self._head is None)\n\n    def size(self):\n        num=0\n        nodo=self._head\n        while(nodo is not None):\n            nodo=nodo.get_next()\n            num += 1\n        return num\n\n    def exists(self, info):\n        nodo=self._head\n        while(nodo is not None) and (nodo.get_info() != info):\n            nodo=nodo.get_next()\n        return (nodo is not None)\n\n    def count(self, info):\n        num=0\n        nodo=self._head\n        while(nodo is not None):\n            if(nodo.get_info() == info):\n               num += 1\n            nodo=nodo.get_next()\n        return num\n\n    def index(self, info):\n        pos=0\n        nodo=self._head\n        while(nodo is not None) and (nodo.get_info() != info):\n            pos += 1\n            nodo=nodo.get_next()\n        if (nodo is None):\n            raise ValueError(&quot;Il nodo %s non esiste&quot; % (info))\n        else:\n            return pos\n\n    def append_left(self, info):\n        nodo=Node(info)\n        nodo.set_next(self._head)\n        self._head=nodo\n\n    def append_right(self, info):\n        nnodo=Node(info)\n        nnodo.set_next(None)\n\n        if(self.is_empty()):\n            self._head=nnodo\n        else:\n            nodo=self._head\n            next=nodo.get_next()\n            while(next is not None):\n                nodo=next\n                next=nodo.get_next()\n            nodo.set_next(nnodo)\n\n    def pop_left(self):\n        if(self._head is None):\n            raise ValueError(&quot;Il nodo %s non esiste&quot; %(info))\n        elif(nodo == self._head):\n            self._head=nodo.get_next()\n            return nodo.get_info()\n\n    def pop_right(self):\n        if(self.is_empty()):\n            raise ValueError(&quot;Il nodo %s non esiste&quot; % (info))\n        else:\n            prec=None\n            nodo=self._head\n            while(nodo.get_next() is not None):\n                prec=nodo\n                nodo=nodo.get_next()\n            info=nodo.get_info()\n            if(nodo == self._head):\n                self._head=None\n            else:\n                prec.set_next(None)\n            return info\n\n     def remove(self, info): \n         prec=None \n         nodo=nodo=self._head \n         while(nodo is not None) and (nodo.get_info() != info): \n             prec=nodo \n             nodo=nodo.get_next() \n         if(nodo is None): \n             raise ValueError(&quot;Il nodo %s non esiste&quot; %(info)) \n         elif(nodo == self._head): \n             self._head=nodo.get_next() \n         else: \n             prec.set_next(nodo.get_next())\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Stack?<\/h2>\n\n\n\n<p>I metodi<\/p>\n\n\n\n<ul>\n<li><strong>append_left<\/strong>(x), aggiunge x a sinistra (in testa)<\/li>\n\n\n\n<li>x &lt;&#8211; <strong>pop_left<\/strong>(), restituisce l&#8217;elemento a sinistra (in testa) e lo elimina<\/li>\n\n\n\n<li><strong>is_empty<\/strong>(), la lista \u00e8 vuota?<\/li>\n<\/ul>\n\n\n\n<p>permettono di realizzare, <em>in modo efficiente<\/em>, uno stack<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nstack=HL_List()\n\nfor x in range(5):\n    stack.append_left(x)\n\nwhile(not stack.is_empty()):\n    print(stack.pop_left(), end=&quot; &quot;)\n<\/pre><\/div>\n\n\n<p>Dopo l&#8217;input la lista \u00e8 la seguente<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; gutter: false; title: ; notranslate\" title=\"\">\nTesta\n  |\n  4 -&gt; 3 -&gt; 2 -&gt; 1 -&gt; 0 -&gt;\n<\/pre><\/div>\n\n\n<p>L&#8217;output \u00e8<\/p>\n\n\n\n<p><code>4 3 2 1 0<\/code><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Coda?<\/h2>\n\n\n\n<p>I metodi<\/p>\n\n\n\n<ul>\n<li><strong>append_left<\/strong>(x)<\/li>\n\n\n\n<li>x &lt;&#8211; <strong>pop_right<\/strong>()<\/li>\n\n\n\n<li><strong>is_empty<\/strong>()<\/li>\n<\/ul>\n\n\n\n<p>oppure<\/p>\n\n\n\n<ul>\n<li><strong>append_right<\/strong>(x)<\/li>\n\n\n\n<li>x &lt;&#8211; <strong>pop_left<\/strong>()<\/li>\n\n\n\n<li><strong>is_empty<\/strong>()<\/li>\n<\/ul>\n\n\n\n<p>permettono di realizzare una coda (le operazioni sul lato destro NON sono efficienti)<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ncoda = HL_List()\n\nfor x in range(5):\n    coda.append_left(x)\n\nwhile(not coda.is_empty()):\n    print(coda.pop_right())\n<\/pre><\/div>\n\n\n<p>Dopo l&#8217;input la lista \u00e8 la seguente<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; gutter: false; title: ; notranslate\" title=\"\">\nTesta\n  |\n  4 -&gt; 3 -&gt; 2 -&gt; 1 -&gt; 0 -&gt;\n<\/pre><\/div>\n\n\n<p>L&#8217;output \u00e8<\/p>\n\n\n\n<p><code>0 1 2 3 4<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>La lista concatenata ha l&#8217;obiettivo di ottimizzare le operazioni di inserimento e di rimozione degli elementi Realizza i metodi tradizionali per le strutture dati Classe nodo Classe lista concatenata Stack? I metodi permettono di realizzare, in modo efficiente, uno stack Dopo l&#8217;input la lista \u00e8 la seguente L&#8217;output \u00e8 4 3 2 1 0 Coda? &#8230; <a title=\"Classe lista concatenata\" class=\"read-more\" href=\"https:\/\/www.valcon.it\/python\/classe-linked-list\/\" aria-label=\"Leggi di pi\u00f9 su Classe lista concatenata\">Leggi tutto<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[85],"tags":[],"_links":{"self":[{"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/posts\/17228"}],"collection":[{"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/comments?post=17228"}],"version-history":[{"count":17,"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/posts\/17228\/revisions"}],"predecessor-version":[{"id":29381,"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/posts\/17228\/revisions\/29381"}],"wp:attachment":[{"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/media?parent=17228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/categories?post=17228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.valcon.it\/python\/wp-json\/wp\/v2\/tags?post=17228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}