Transcript List - FmGroup

Linked Lists
Outline
•
•
•
•
Why linked lists?
Linked lists basics
Implementation
Basic primitives
- Searching
- Inserting
- Deleting
Why linked lists?
• The default implementation for storing a set of objects is
an array
- int v[10];
denotes the allocation of 10 int variables
• Arrays are efficient for many purposes (e.g., fast access
to elements), but have several limitations
Limitations of arrays (1)
• Their size must be fixed in advance
- At compile time (statically allocated)
int mydata[100];
- At run time (dynamically allocated)
int *mydata;
mydata = (int*)malloc(sizeof(int)*100);
• In theory it is possible, for a dynamically allocated array
to resize it using realloc but it tends to be quite
inefficient
- E.g., reallocate a large array to add 1 element
Limitations of arrays (2)
• Because of first limitation, arrays are often
over-sized
• To deal with dynamically changing sets of data,
programmers usually allocate arrays which seem "large
enough“.
• Problems:
- Low utilization of arrays (you allocate a size X but use at most a
fraction of it) and the space is wasted
- If the program ever needs to process more than X data, the code
breaks
Limitation of arrays (3)
• Inserting elements to keep a given order is
inefficient
• Example:
- If elements of the array represent an order of arrival (a[0] is
last arrived) inserting a new element implies moving all
elements one position ahead
Array vs. linked lists
• Linked lists solve limitations of arrays by paying
in terms of efficiency of access of elements
• Arrays:
- allocate memory for all its elements stored in contiguous memory
locations (appears as one block of memory)
• Linked lists:
- allocate space for each element separately in its own block of
memory called a "linked list element" or "node".
- The list gets is overall structure by using pointers to connect all its
nodes together like the links in a chain.
Array vs. linked lists
• Array
• List
– int v[4];
v
– ????
2
2
5
3
-1
v[0]
v[1]
v[2]
v[3]
?
5
-1
3
Linked lists
• Each list node contains two fields:
- a "data" field to store whatever element type the list holds
- and a "next" field which is a pointer used to link one node to the
next node.
• Each node is allocated with malloc() and it continues
to exist until it is explicitly deallocated with free()
Arrays vs. linked lists
Access time
Utilization
Modification of
element order
Arrays
Lists
+
(independent of
array size – random
access)
(proportional to list size –
sequential access)
(over allocation typical)
+
(allocate what you need)
(requires movement
of elements)
+
(insert where needed by
moving pointers)
Lists (cont.)
• Variants:
- Double linked lists
• The element possesses a pointer also to the previous element
- Circular lists
• The last element in the list is linked to the head
Lists (cont.)
• Variants:
- Lists with sentinel
• Head or tail or both exist as fictitious elements to manage
special cases at the boundary
- Ordered Lists
• Starting from the head the elements (i.e., the keys)
have an order (increasing or decreasing)
Array vs. linked lists
• Array
• List
– int v[4];
– List* Head;
Head
v
2
5
3
-1
v[0]
v[1]
v[2]
v[3]
2
5
-1
3
Lists - (cont.)
• Primitives
- Insert (at the head of the list)
- Search
- Delete
- InsertSorted
• NOTE: The ordering of a list is not immediate
- It requires double pointers or auxiliary lists
Lists: Basic operations
• Different from vector based data structures,
operation on a list requires pointer manipulation
• Element creation:
- Using malloc()
• Initialization of a list
- A pointer to list initialized to NULL
• Insertion/deletion of an element
- Movement of pointers
Lists - list.h
typedef struct e{
int key;
List* next;
} List;
List* Insert(List*,int); /* modifies the head */
List* Search(List*, int);
void Display(List*);
List* Delete(List*,int, int*); /* modifies the head */
List* InsertSorted(List*,int); /* modifies the head*/
Lists - list.c (1)
#include <stdio.h>
List* Insert( List* head, int val)
{
List* p;
p = newE();
p->key = val; /* più vari campi */
p->next = head;
head = p;
return head;
}
Lists - list.c (2)
List* Search( List* head, int val)
{
List* p;
p = head;
while(p != NULL)
{
if( p->key == val)
return(p);
else
p = p->next;
}
return(NULL);
}
Lists - list.c (3)
void Display(List* head)
{
List* p;
p = head;
}
while( p != NULL)
{
printf(“%5d\n”,p->val);
p = p->next;
}
Lists - list.c (4)
•The previous examples are in fact two
applications of a generic “visit” function that does
something on ALL list elements
void Visit (List* head)
{
List* p;
}
p = head;
while( p != NULL)
{
/* do something on p->key */
p = p->next;
}
Example of usage
int val;
List* head, p;
…
val = 1;
p = Search (head, val);
if (p == NULL)
printf(“Value not found!\n”);
else
printf(“Value found!\n”);
Lists: Deleting an element
• Deleting an element q (after element p)
p
q
Before
p->next
p
q->next
q
After
p->next = q->next;
free(q);
Lists - list.c (3)
List* Delete( List* head, int val, int* status)
{
List *p, *q;
}
p = q = head;
if (head != NULL){
if (p->key == val) {
/* found */
head = p->next;
Delete from head
free(p);
*status = SUCCESS;
return head;
} else {
Search where
while(q->next != NULL) {
p = q;
q = q->next;
if (q->key == val) {
p->next = q->next;
Delete it
free(q);
*status = SUCCESS;
return head;}}}}
*status = FAILURE;
return head;
is it
Lists: Inserting an element
• Insertion of node q after node p
q
5
Before
p
6
3
p->next
p->next
After
q->next = p->next;
p->next = q;
5
q
q->next
p
3
6
Lists - list.c (4)
List* InsertSorted(List* head, int val)
{
List *p, *q=head;
/* head insertion */
if( (q == NULL) || (q->key > val))
{
p = newE();
p->key = val;
p->next = head;
head = p;
return head;
}
Lists - list.c (4)
/* search where to insert q*/
is != NULL, so q->next is defined
while( q->next != NULL) {
if( q->next->key > val)
{
p = newE();
p->key = val;
p->next = q->next;
q->next = p;
return head;
}
q = q->next;
}
Lists - list.c (4)
/* tail insertion: q->next is null here*/
p = newE();
p->key = val;
p->next = NULL;
q->next = p;
return head;
}
Stacks and Queues
Stack
• Use a LIFO (Last In First Out) policy
- The last element inserted is the first that will be
deleted
- Eg.: a stack of books
• Implementation in terms of lists
• Primitives:
- Push
- Pop
- Top
- Empty
Stack and queues
• Dynamic Push
- Insertion in head
List* head=NULL; //init.
head = Push (head, val); //call
List* Push (List*,int val)
{
List* p;
p = newE();
p->next = head;
p->key = val;
head = p;
}
• Dynamic Pop
- Deletion from head
List* Pop(List* head, int* val)
{
List* p;
if (head==NULL) {
printf(“Stack
Underflow\n”);
} else {
*val = head->key;
p = head;
head = p->next;
free(p);
return head;
}
}
Queues
• Implements a FIFO (First In First Out) policy
- First inserted item is the first to be extracted (deleted)
- E.g., a queue of persons to be served
Queues and lists
• Dynamic Enqueue
- Insert in tail
• Dynamic Dequeue
- Extract from the head
• Given the huge number of accesses to the tail of the list,
it is convenient to use an explicit pointer tail for the
queues
Linear queues with lists
• Dynamic Enqueue
• Dynamic Dequeue
List* head=NULL, tail; //init.
Function call:
pTail = enqueue (&head, pTail, val);
List* enqueue(List** head,
List* pTail,int val)
{
List* p;
p = newE();
p->key = val;
if (pTail==NULL) { //first elem
*head = p;
p->next = NULL;
} else {
pTail->next = p;
}
pTail = p;
return pTail;
}
head = dequeue (head, &pTail, &val);
List* dequeue(List* head,
List** pTail,int* val)
{
List* p;
if (head==NULL) {
printf(“Queue underflow\n”);
} else {
*val = head->key;
p = head;
if (head == *pTail) {
/* one-element queue */
*pTail=NULL; head=NULL;
} else {
head = head->next;}
free (p);
}
return head;
}
Circular queues
• Dynamic Enqueue
- Insert in tail
• Dynamic Dequeue
- Extract from the head
• Usage of pointer pTail for insertion and deletion: last
element points to first one
pTail->next
pTail
Queues and lists - (cont.)
• Dynamic Enqueue
• Dynamic Dequeue
Function call:
pTail = enqueue(pTail, val);
Function call:
pTail = dequeue(pTail, val);
List* enqueue(List* pTail, int val)
{
List* pNew;
pNew = newE();
List* dequeue(List* pTail, int* val,
int* status)
{
List* pOld;
if (pTail=!=NULL) {
*status = SUCCESS;
if (pTail == pTail->next){
*val = pTail->key;
free(pTail);
pTail = NULL;}
else{
pOld = pTail->next;
*val = pOld->key;
pTail->next = pOld->next;
free(pOld);}}
return pTail;
}
p->key = val;
/* ……. */
if (pTail==NULL) {
pTail = pNew;
pTail->next = pTail;
} else {
pNew->next = pTail->next;
pTail->next = pNew;
pTail = pNew;
}
return pTail;
}