Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Le liste: inserimento ordinato
• Procedura completa per l’inserimento ordinato in lista
void insertNode(ListNodePtr *sPtr, int value){
ListNodePtr newPtr, prevPtr, currPtr;
newPtr = malloc(sizeof(ListNode) );
if(newPtr != NULL){
newPtr->data = value;
newPtr->nextPtr = NULL;
prevPtr = NULL;
currPtr = *sPtr;
while(currPtr!=NULL && value>currPtr->data){
prevPtr = currPtr;
currPtr=currPtr->nextPtr;
}
if(prevPtr == NULL){
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
}
else{
prevPtr->nextPtr = newPtr;
newPtr->nextPtr = currPtr;
}
}
else printf("%d not inserted. No memory is available.\n", value);
}
 2000 Prentice Hall, Inc. All rights reserved.
Parametri formali:
- Puntatore al puntatore che
punta alla testa della lista
- Dato da inserire in lista
Chiamata di procedura:
int item = 10;
ListNodePtr startPtr = NULL;
insertNode(&startPtr, item);
NOTA:
La procedura modifica la lista
e quindi questa va passata per
riferimento (doppio puntatore)
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in posizione intermedia (1/5)
• void insertNode(ListNodePtr *sPtr, int value){ … }
– Allocazione dinamica del nuovo nodo per il nuovo dato
*sPtr
newPtr = malloc(sizeof(ListNode));
newPtr
8
2
prevPtr
6
value
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Inserimento ordinato in lista:
inserimento in posizione intermedia (2/5)
• if(newPtr != NULL){ … }
– Inizializzazione del nuovo nodo e dei puntatori per la scansione della lista
*sPtr
newPtr
8
2
newPtr->data = value;
newPtr->nextPtr = NULL;
8
6
value
10
prevPtr = NULL;
currPtr = *sPtr;
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Inserimento ordinato in lista:
inserimento in posizione intermedia (3/5)
• while(currPtr != NULL && value > currPtr->data){… }
– Ricerca della posizione di inserimento: iterazione n.1 [8 > 2 è vero]
*sPtr
2
8
newPtr
6
10
14
(2)
(1)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in posizione intermedia (4/5)
• while(currPtr != NULL && value > currPtr->data){… }
– Ricerca della posizione di inserimento: iterazione n.2 [8 > 6 è vero]
*sPtr
8
newPtr
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in posizione intermedia (5/5)
• while(currPtr != NULL && value > currPtr->data){… }
– Uscita dal ciclo e inserimento del nodo: posizione trovata [8 > 10 è falso]
*sPtr
prevPtr->nextPtr = newPtr; (1)
newPtr->nextPtr = currPtr; (2)
8
newPtr
(2)
(1)
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in testa (1/3)
• void insertNode(ListNodePtr *sPtr, int value){ … }
– Allocazione dinamica del nuovo nodo per il nuovo dato
newPtr
newPtr = malloc(sizeof(ListNode));
*sPtr
1
2
prevPtr
6
value
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Inserimento ordinato in lista:
inserimento in testa (2/3)
• if(newPtr != NULL){ … }
– Inizializzazione del nuovo nodo e dei puntatori per la scansione della lista
newPtr
newPtr->data = value;
newPtr->nextPtr = NULL;
1
*sPtr
1
2
6
value
10
prevPtr = NULL;
currPtr = *sPtr;
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Inserimento ordinato in lista:
inserimento in testa (3/3)
• while(currPtr != NULL && value > currPtr->data){… }
– Inserimento nella prima posizione: nessuna iterazione [1 > 2 è già falso]
newPtr
newPtr->nextPtr = *sPtr; (1)
*sPtr = newPtr; (2)
1
*sPtr
(2)
(1)
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in coda (1/7)
• void insertNode(ListNodePtr *sPtr, int value){ … }
– Allocazione dinamica del nuovo nodo per il nuovo dato
*sPtr
newPtr = malloc(sizeof(ListNode));
newPtr
20
2
prevPtr
6
value
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Inserimento ordinato in lista:
inserimento in coda (2/7)
• if(newPtr != NULL){ … }
– Inizializzazione del nuovo nodo e dei puntatori per la scansione della lista
*sPtr
newPtr
20
2
newPtr->data = value;
newPtr->nextPtr = NULL;
20
6
value
10
prevPtr = NULL;
currPtr = *sPtr;
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Inserimento ordinato in lista:
inserimento in coda (3/7)
• while(currPtr != NULL && value > currPtr->data){… }
– Ricerca della posizione di inserimento: iterazione n.1 [20 > 2 è vero]
*sPtr
2
20
newPtr
6
10
14
(2)
(1)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in coda (4/7)
• while(currPtr != NULL && value > currPtr->data){… }
– Ricerca della posizione di inserimento: iterazione n.2 [20 > 6 è vero]
*sPtr
20
newPtr
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in coda (5/7)
• while(currPtr != NULL && value > currPtr->data){… }
– Ricerca della posizione di inserimento: iterazione n.3 [20 > 10 è vero]
*sPtr
2
20
newPtr
6
14
10
(1)
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Inserimento ordinato in lista:
inserimento in coda (6/7)
• while(currPtr != NULL && value > currPtr->data){… }
– Ricerca della posizione di inserimento: iterazione n.4 [20 > 14 è vero]
*sPtr
2
20
newPtr
6
10
14
(1)
(2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
Inserimento ordinato in lista:
inserimento in coda (7/7)
• while(currPtr != NULL && value > currPtr->data){… }
– Uscita dal ciclo e inserimento del nodo: posizione trovata [ currPtr!=NULL è falso]
(2)
*sPtr
20
prevPtr->nextPtr = newPtr; (1)
newPtr->nextPtr = currPtr; (2)
newPtr
(1)
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Le liste: rimozione di un nodo
• Procedura completa per la cancellazione di un elemento
int deleteNode(ListNodePtr *sPtr, int value){
ListNodePtr prevPtr, currPtr, tempPtr;
if(value == (*sPtr)->data){
tempPtr = *sPtr;
*sPtr = (*sPtr)->nextPtr;
free(tempPtr);
return value;
}
else{
prevPtr=*sPtr;
currPtr=(*sPtr)->nextPtr;
while(currPtr!=NULL && value != currPtr->data){
prevPtr=currPtr;
currPtr=currPtr->nextPtr;
}
if(currPtr! = NULL){
tempPtr=currPtr;
prevPtr->nextPtr=currPtr->nextPtr;
free(tempPtr);
return value;
}
}
return -1;
}
 2000 Prentice Hall, Inc. All rights reserved.
Parametri formali:
- Puntatore al puntatore che
punta alla testa della lista
- Dato da eliminare dalla lista
Valore di ritorno:
- Se trova il dato da eliminare
ritorna il dato stesso
- Altrimenti ritorna -1
Chiamata di procedura:
int item = 10;
ListNodePtr startPtr = NULL;
deleteNode(&startPtr, item);
NOTA:
La procedura modifica la lista
e quindi questa va passata per
riferimento (doppio puntatore)
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in posizione intermedia (1/5)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Dichiarazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
10
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Eliminazione di un elemento dalla lista:
elemento in posizione intermedia (2/5)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Inizializzazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
10
2
6
10
14
(2)
(1)
prevPtr = *sPtr; (1)
currPtr = (*sPtr)->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in posizione intermedia (3/5)
• while(currPtr != NULL && value != currPtr->data){… }
– Ricerca del nodo da eliminare: iterazione n.1 [10 != 6 è vero]
*sPtr
tempPtr
value
10
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in posizione intermedia (4/5)
• while(currPtr != NULL && value != currPtr->data){… }
– Uscita dal ciclo e rimozione del nodo: posizione trovata [10 != 10 è falso]
*sPtr
tempPtr
value
tempPtr = currPtr; (1)
10
(1)
2
6
14
10
(2)
prevPtr->nextPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in posizione intermedia (5/5)
• Eliminazione fisica del nodo
– Rilascio dell’area di memoria che era stata allocata dinamicamente per il nodo
*sPtr
tempPtr
value
10
2
free(tempPtr);
return value;
14
6
RITORNA 10
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in testa (1/3)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Dichiarazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
2
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Eliminazione di un elemento dalla lista:
elemento in testa (2/3)
• if(value == (*sPtr)->data){ … }
– Eliminazione diretta dell’elemento in prima posizione
*sPtr
tempPtr
value
2
tempPtr = *sPtr; (1)
*sPtr = (*sPtr)->nextPtr; (2)
(1)
(2)
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Eliminazione di un elemento dalla lista:
elemento in testa (3/3)
• Eliminazione fisica del nodo
– Rilascio dell’area di memoria che era stata allocata dinamicamente per il nodo
*sPtr
tempPtr
value
2
6
10
free(tempPtr);
return value;
14
RITORNA 2
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in coda (1/6)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Dichiarazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
14
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Eliminazione di un elemento dalla lista:
elemento in coda (2/6)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Inizializzazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
14
2
6
10
14
(2)
(1)
prevPtr = *sPtr; (1)
currPtr = (*sPtr)->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in coda (3/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Ricerca del nodo da eliminare: iterazione n.1 [14 != 6 è vero]
*sPtr
tempPtr
value
14
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in coda (4/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Ricerca del nodo da eliminare: iterazione n.2 [14 != 10 è vero]
*sPtr
tempPtr
value
14
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in coda (5/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Uscita dal ciclo e rimozione del nodo: posizione trovata [14 != 14 è falso]
*sPtr
tempPtr
value
tempPtr = currPtr; (1)
14
(1)
(2)
2
6
10
14
prevPtr->nextPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento in coda (6/6)
• Eliminazione fisica del nodo
– Rilascio dell’area di memoria che era stata allocata dinamicamente per il nodo
*sPtr
tempPtr
value
14
2
6
free(tempPtr);
return value;
10
RITORNA 14
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Le liste
• Inserimento ordinato in lista
– Inserimento in posizione intermedia
– Inserimento in testa
– Inserimento in coda
• Rimozione di un nodo dalla lista
–
–
–
–
Rimozione di un nodo in posizione intermedia
Rimozione del nodo in testa
Rimozione del nodo in coda
Tentata rimozione di un nodo inesistente
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento inesistente (1/6)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Dichiarazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
12
2
prevPtr
6
10
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
14
Eliminazione di un elemento dalla lista:
elemento inesistente (2/6)
• int deleteNode(ListNodePtr *sPtr, int value){ … }
– Inizializzazione dei puntatori per la scansione della lista
*sPtr
tempPtr
value
12
2
6
10
14
(2)
(1)
prevPtr = *sPtr; (1)
currPtr = (*sPtr)->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento inesistente (3/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Ricerca del nodo da eliminare: iterazione n.1 [12 != 6 è vero]
*sPtr
tempPtr
value
12
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento inesistente (4/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Ricerca del nodo da eliminare: iterazione n.2 [12 != 10 è vero]
*sPtr
tempPtr
value
12
2
6
10
(1)
14
(2)
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
Eliminazione di un elemento dalla lista:
elemento inesistente (5/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Ricerca del nodo da eliminare: iterazione n.3 [14 != 10 è vero]
*sPtr
tempPtr
value
12
2
6
10
14
(1)
(2)
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.
prevPtr = currPtr; (1)
currPtr = currPtr->nextPtr; (2)
Eliminazione di un elemento dalla lista:
elemento inesistente (6/6)
• while(currPtr != NULL && value != currPtr->data){… }
– Uscita dal ciclo: posizione non trovata [currPtr != NULL è falso]
*sPtr
tempPtr
value
14
2
return -1;
6
10
14
RITORNA -1
prevPtr
currPtr
 2000 Prentice Hall, Inc. All rights reserved.