struct person { char name[21];int mark;};
typedef struct person PERSON;
PERSON student[100];
The order of items stored in a list using an array is determined by the sequential positioning of the items in memory, ie consecutive items in the list are stored in consecutive memory locations.
The use of a static array implies that the list will have a fixed maximum size determined by the variable declaration. This means that the maximum size must be determined in advance and the program written to allow for this even though it may frequently use only a small portion of the array. Alternatively space for a dynamic array can be calculated and allocated at runtime using malloc() before storing the items if the number of records is already known.
A more important problem is met when one attempts to add an item to the list whilst preserving the order of the items. for example, to add the name BOB to the following list, it is necessary to copy each array element from student [3] onwards up one position in order to insert the new record. This problem was met when studying the Insertion Sort algorithm. A similar problem exists when deleting records from the list.
Each data element or 'node' contains an address pointer. Consecutive items are not necessarily stored in order or in consecutive memory locations. Both the top 2 diagrams below represent the same data structure. Neither is 'more efficient'.
The bottom 2 diagrams above show a node for Bob (mark 62) being inserted into the linked list in alphabetical order.
Each node contains the address of the node that follows it in the list. thus the nodes can be stored in memory in random order. The last node in the list contains a special address that indicates that there are no further nodes. The actual value used depends on the particular system and is usually denoted by the symbol ^ or the word 'nil' or 'NULL'.
The advantage of a linked list over an array becomes apparent when an
item is added to the list. Since the physical location of each node does
not determine its logical position in the list, there is clearly no need
to move any data. All that is required is to alter one or more of the address
pointers.
Note that although the items stored in a linked list are in order, it is only possible to perform a sequential search of the list. This is because, for example, the only way of determining the location of the third node in the list is to examine the address field of the first node, and so on. Thus a search must start with the first node and proceed sequentialy from one node to the next.
If dynamic memory allocation is used the space occupied by the deleted
node must be freed to enable the memory occupied to be reuseable by other
objects.
A doubly linked list contains both a forward pointer and a backward pointer; ie it contains the address of the preceding and the following nodes.
A doubly linked list occupies slightly more storage space, and it is more complex to add or delete nodes since twice as many address pointers have to be manipulated. However, it can be traversed in either direction enabling both the node preceding and the node following a given node to be located.
Thus a structure to store data on a student's name and mark could be declared using:
struct cell {
char name[21];
int mark;
struct cell *next;
};
typedef struct cell ITEM;
To create dynamic variables requires the use of a pointer variable to indicate
the position of the first structured object. Two further pointer variables
are required to insert and delete other structured objects in the list.
These are declared as follows:
ITEM *p,*q,*first;To create the first structured object function malloc() is used.
k = sizeof(ITEM); first = (ITEM*)malloc(k); first->next = NULL;Function malloc() requires an integer parameter, in this case k, for the number of bytes required, in this case the size of structure item. Function sizeof() is used to determine the size of the structure. In previous versions of C function malloc() returns a pointer to type char while in ANSI C function malloc() returns a pointer to type void. This requires the use of a casting operator, in this case (ITEM*), to assign it to a pointer to the correct type of data, in this case an ITEM pointer. The pointer member next of structure variable first is assigned the value 0 ( note NULL is constant defined in stdio.h with value 0 )
It is often convenient to have a dummy node as the first item in the list to avoid having to process the first node separately from the remainder. This dummy node contains no data.
insert(ITEM *p,ITEM *q){
q->next=p->next;
p->next=q;
}
When insert() is called, *p is assigned the address of the node before the insert position and *q is similarly pointed at the node to be inserted.
delete(ITEM *p){
ITEM *q;
q=p->next;
p->next=q->next;
free(q); /* free memory previously used by deleted node */
}
When delete() is called, *p is assigned the address of the node
before the delete position and *q is declared as an ITEM pointer.
The next pointer of the node before the one to be deleted is pointed
at the node after the one to be deleted.
The memory occupied by the node to be deleted is freed for reuse. If
the programmer forgets this the resulting bug is called a "memory leak"
which is likely to crash the application.
.
void display(void){ /* display all nodes in SLL */
ITEM *temp;
printf("\n%-20s%5s\n","name","mark"); /* print headings */
printf("\n%-20s%5s\n","----","----");
temp=first; /* *first must be declared globally as it isn't a parameter */
while (temp->next!=(ITEM*) NULL){ /* loops until last node displayed */
temp=temp->next; /* first item doesn't contain data, last does */
printf("%-20s%5d\n",temp->name,temp->mark);
}
}
A similar function is used to traverse a SLL in order to find the address
of a data item. Finding nodes before this target point for insertion
while maintaining a sort order or required for a deletion is left as an
exercise for the reader.
ITEM *find(char *searchkey){ /* find node in SLL with name same as searchkey */
ITEM *temp;
temp=first; /* *first must be declared globally as it isn't a parameter*/
while (temp->next!=(ITEM*) NULL){ /* loops until last node displayed */
temp=temp->next; /* first item doesn't contain data, last does */
if(strcmp(temp->name,searchkey)==0) return temp;
/* return address of node found with same name */
}
return (ITEM*) NULL; /* item with name equal to search key is not in SLL*/
}
Thus a structure to store data on a student's name and mark could be declared using:
struct node {
char name[21];
int mark;
struct node *next, *prev; /* pointers to next and previous nodes */
};
typedef struct node ITEM;
Coding this is left as an exercise for the reader. To assist in
this the procedure illustrated below might be used.
