====== Liste, pile e code ======

Nella lezione del 27/10, abbiamo visto le principali strutture dati basate sul concetto di sequenza:
  * [[wp>List_(computing)|Liste]]
    * Implementazione tramite puntatori ([[wp>Linked_list|linked list]])
    * Implementazione tramite array
  * [[wp>Stack_(data_structure)|Pile]]
  * [[wp>Queue_(data_structure)|Code]]
    * Basate su liste
    * Basate su array (in genere [[wp>Circular_queue|code circolari]])
  * [[wp>Associative_array|Dizionari]]

In aggiunta a quanto detto, ecco i [[http://home.dei.polimi.it/agosta/files/Info3-sequences.tgz|file]] python con le implementazioni (corrette ed espanse) delle strutture dati viste a lezione. Inoltre la versione C++ delle liste (sia linkate che basate su array) si trova sulla pagina del [[http://people.cs.vt.edu/~shaffer/Book/|libro di testo]].
Potete inoltre trovare {{teaching:info3:lists.zip|qui}} un'implementazione delle liste tramite doppio puntatore.


=== Sequences ===

Today, we introduced the sequence data structures:
  * [[wp>List_(computing)|List]]
    * [[wp>Linked_list|Linked list]]
    * Array
  * [[wp>Stack_(data_structure)|Stack]]
  * [[wp>Queue_(data_structure)|Queue]]
    * Based on lists
    * It is possible to have the same structures based on arrays (as [[wp>Circular_queue|Circular Queues]])
  * [[wp>Associative_array|Dictionary]]

Here you can find the [[http://home.dei.polimi.it/agosta/files/Info3-sequences.tgz|files]] with the python implementation of the data structures. A C++ version can be found on the [[http://people.cs.vt.edu/~shaffer/Book/|web page]] of Shaffer's book.
A C implementation of doubly linked lists can be found {{teaching:info3:lists.zip|here}}.

**Simple List Implementation**
<code Python>
#!/usr/bin/python

class ListItem(object):
        '''Elemento della lista'''
        def __init__(self, elem, next=None):
                self.data=elem
                self._next=next

class List(object):
        '''ADT Lista'''
        def __init__(self):
                self.head=ListItem(None)        # testa della lista (elemento dummy)
                self.tail=self.head                             # coda della lista
                self.current=self.head    # posizione corrente (coda della partizione sinistra)
                self.lsize=0                    # dimensione della partizione sinistra
                self.rsize=0                    # dimensione della partizione destra

        def setStart(self):
                '''Spostamento di current nella posizione di testa'''
                self.current=self.head
                self.rsize+=self.lsize
                self.lsize=0

        def setEnd(self):
                '''Spostamento di current nella posizione di coda'''
                self.current=self.tail
                self.lsize+=self.rsize
                self.rsize=0

        def getValue():
                if self.rsize==0 : return None
                else : return self.current._next.data

        def insert(self,elem):
                '''Inserimento di un elemento nella testa della partizione destra'''
                self.current._next=ListItem(elem,self.current._next)
                # aggiorna tail se self.current==self.tail
                if self.tail==self.current : self.tail=self.tail._next
                self.rsize+=1

        def delete(self):
                '''Cancellazione di un elemento alla testa della partizione destra'''
                if not self.current._next : return None
                res = self.current._next.data
                self.current._next=self.current._next._next
                self.rsize-=1
                return res

        def next(self):
                '''Spostamento di current nella posizione successiva'''
                if self.current != self.tail :
                        self.current=self.current._next
                        self.rsize-=1
                        self.lsize+=1

        def prev(self):
                '''Spostamento di current nella posizione precedente'''
                if self.current!=self.head:
                        curr=self.head
                        while curr._next != self.current : curr=curr._next
                        self.current=curr
                        self.lsize-=1
                        self.rsize+=1

        def setPos(self,pos):
                '''Spostamento di current alla posizione pos; self.lsize=pos'''
                if pos<0 or pos>self.rsize+self.lsize : raise IndexError
                self.rsize = self.rsize+self.lsize-pos
                self.lsize = pos
                self.current=self.head
                for i in range(pos):
                        self.next()

        def __str__(self):
                '''Costruzione della versione stampabile della lista'''
                res='['
                if self.head==None : return res+' ]'
                if self.head==self.current : res+=' |'
                curr=self.head._next
                while curr != None :
                        res+=' '+`curr.data`
                        if curr==self.current : res+=' |'
                        curr=curr._next
                return res+' ]'


# Test -- non viene eseguito quando il modulo viene caricato come libreria
if __name__ == '__main__' :
        def doprint(command) :
                '''Funzione di aiuto per la stampa formattata; notate l'uso di eval per eseguire codice contenuto in una stringa passata come parametro!'''
                eval(command)
                print command, ' '*(20-len(command))+'=>\t', a

        a = List()
        doprint('a.insert(1)')
        doprint('a.insert("pippo")')
        doprint('a.insert(2.0)')
        doprint('a.next()')
        doprint('a.insert("pluto")')
        doprint('a.setEnd()')
        doprint('a.delete()')
        doprint('a.prev()')
        doprint('a.insert("2")')
        doprint('a.setStart()')
        doprint('a.delete()')
</code>