Linked Lists (Code)
inc | September 23, 2008 | 12:20 pmHere is some code that may help with creating a linked list, and also adding and removing elements from it. The code below is for a double linked list, for a single linked list all you have to update is the next pointer as the previous pointer will not be needed (as that is the difference between the two types of list). I shall be using the following data structures throughout the following code examples.
/*-- Stock Master Record ---------------------------------------------------*/
typedef struct
{ char key[7];
char partDesc[20];
short suppCode;
long freeStk;
short minStk;
char moveDate[7];
float price;
}STOCK_REC;
/*-- Double Linked List ---------------------------------------------------*/
typedef struct STOCK_LIST
{ STOCK_REC rec;
struct STOCK_LIST *prev; /*-- Pointer to the previous element --*/
struct STOCK_LIST *next; /*-- Pointer to the next element --*/
}STOCK_LIST;
Creation of a linked list:
Declare two global pointers that will be used to keep track of the start and end of the linked list (with a single linked list you should only need to to keep a record of the start of the list):
STOCK_LIST *RecFirst = NULL; /*-- Pointer to start of the link list. --*/ STOCK_LIST *RecFinish = NULL; /*-- Pointer to finish of the link list --*/
Declare a pointer to a list element, this is used to allocate memory for each element in the list.
STOCK_LIST *recElement;
Now follows the actual code that allocates memory for a list element and than adds this element to the end of the list (updating the list pointers as it goes). This is not full code but will do as it says and maybe used in a complete program.
/*-- Allocate memory for the next element in the list --*/
if ((recElement = (STOCK_LIST *)malloc(sizeof(STOCK_LIST))) != NULL)
{ /*-- Populate stock list elements data --*/
strcpy(recElement->rec.key, "123456");
strcpy(recElement->rec.partDesc, "A PART");
strcpy(recElement->rec.moveDate, "220670");
recElement->rec.suppCode = 'A';
recElement->rec.freeStk = 100;
recElement->rec.minStk = 50;
recElement->rec.price = 5.99;
recElement->next = NULL;
/*-- If start of list is empty, set this element as the start --*/
if (RecFirst == NULL)
{ /*-- This element is the start of the list --*/
RecFirst = recElement;
/*-- No element precedes this element --*/
RecFirst->prev = NULL;
}else
{ /*-- This element is now the final element --*/
RecFinish->next = recElement;
/*-- The element prior to this one is the previous final element --*/
recElement->prev = RecFinish;
}
/*-- Keep the end of list pointer up-to-date --*/
RecFinish = recElement;
}else
{ printf("Error Creating Linked List - Memory allocation error!\n");
exit(EXIT_FAILURE);
}
To start with the above may seem quite complicated but when you actually use the code and get used to shifting pointers you will become at ease and fully understand linked list creation. As with all things in life practice makes prefect (I’m far from that).
Inserting an element into a linked list:
If the list is in order then you will want the element inserted into the correct place within the list, to do this you must search the list and locate the element where you want the insertion to follow.
static STOCK_LIST *searchList (char *partNum)
{ STOCK_LIST *recList,
*prevRec;
int res;
for (recList=RecFirst, prevRec=NULL; recList!=NULL; recList=recList->next)
{ res = strcmp(recList->index.key,partNum);
if (res == 0)
return recList;
else if (res > 0)
return prevRec;
/*-- Keep track of the previous record --*/
prevRec = recList;
}
if (prevRec != NULL && prevRec != recFirst)
{ /*-- Element is to be inserted at the end of the list --*/
return prevRec;
}else
{ /*-- Element is to be inserted at the start of the list --*/
return NULL;
}
}
Now the recList pointer will either point to no where or the element where the insertion is to follow. If the pointer is NULL the element will be inserted at the start of the list. Here is some code that will hopefully show this in action.
/*-- Search the list for the given part number ----------------*/
/*-- Return the previous record if the part num is not found --*/
recList = searchList(partNum);
/*-- Allocate memory for new stock record element --*/
if ((newRec = (STOCK_LIST *) malloc (sizeof(STOCK_LIST))) != NULL)
{ /*-- Populate stock list elements data --*/
strcpy(recElement->rec.key, "123457");
strcpy(recElement->rec.partDesc, "B PART");
strcpy(recElement->rec.moveDate, "220670");
recElement->rec.suppCode = 'A';
recElement->rec.freeStk = 100;
recElement->rec.minStk = 50;
recElement->rec.price = 5.99;
recElement->next = NULL;
/*-- Insert element in correct position of the list --*/
if (recList == NULL) /*-- Start of List --*/
{ newRec->next = RecFirst;
newRec->prev = NULL;
RecFirst->prev = newRec;
RecFirst = newRec;
}else if (recList == recFinish) /*-- End of list --*/
{ RecFinish->next = newRec;
newRec->prev = RecFinish;
newRec->next = NULL;
RecFinish = newRec;
}else /*-- Middle of list --*/
{ newRec->next = recList->next;
newRec->prev = recList;
recList->next = newRec;
newRec->next->prev = newRec;
}
}else
{ printf("Error Adding to List - Memory allocation error!\n");
exit(EXIT_FAILURE);
}
Notice the lack of code to handle if the element already exists within the list, this is quite straight forward to add so I will leave for you to complete.
Deleting an element from a linked list:
Again we must search the list for the correct element to remove, we use the same function as used above. Note again I have not included any code to deal with the element not being in the list.
/*-- Search the list for the given part number ----------------*/
/*-- Return the previous record if the part num is not found --*/
recList = searchList(partNum);
/*-- The record was found in the linked list --*/
if(!strcmp(recList->index.key, partNum))
{ zapRec = recList;
if (recList == recFirst) /*-- Remove first element --*/
{ recFirst = recList->next;
recFirst->prev = NULL;
}else if (recList == recFinish) /*-- Remove last element --*/
{ recFinish = recList->prev;
recFinish->next = NULL;
}else /*-- Remove middle element --*/
{ recList->prev->next = recList->next;
recList->next->prev = recList->prev;
}
/*-- Free deleted elements memory --*/
free(zapRec);
}
- Comments
- No Comments »
- Categories
- Code, Linux
Comments rss
Trackback
