SINGLE-LINKED LIST
Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be anything from a short integer value to a complex struct type, also has a pointer to
the next node in the single-linked list. That pointer will be NULL if the end of the single-linked list is encountered.
The single-linked list travels only one way; from the beginning to the end.
There is no way to go back to a previous node, unlike what can happen in double-linked lists which we will examine later.
As an example, i chose a single-linked list which is sorted increasingly and each value, which is of type int, is unique. That is, each value is greater that the previous and lower than its next.
For example: 3 -> 6 -> 10 -> 100 -> NULL.
To begin with, lets write the file slistdefs.h which will include the struct to be used as well as the prototypes of the functions for the slist. Note that slist is a short for single-linked list.
Now, lets make the other files for each of the functions:
The code is ready to copy and paste so as you can immediately run test and modify the functions so as to cover your needs.
You can add messages when for example a value does not exist when deleting; you might want to inform user that no deletion was made. You can add prints in many other places too. Add assertions to check that each value is unique.
You can add more functions to practise a bit on single-linked list, or change entirely the concept of the code i present.
You can write a function int getLength( struct slist *head ) that returns the number of nodes in the list.
Write functions to return nodes with the lower and greater value, and for more challenging ones function to copy a list to another or a function to reverse the list. Try to write recursive versions of some of the functions as well.
Except to see more data types and code for them, like double-linked list and binary search tree.
Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be anything from a short integer value to a complex struct type, also has a pointer to
the next node in the single-linked list. That pointer will be NULL if the end of the single-linked list is encountered.
The single-linked list travels only one way; from the beginning to the end.
There is no way to go back to a previous node, unlike what can happen in double-linked lists which we will examine later.
As an example, i chose a single-linked list which is sorted increasingly and each value, which is of type int, is unique. That is, each value is greater that the previous and lower than its next.
For example: 3 -> 6 -> 10 -> 100 -> NULL.
To begin with, lets write the file slistdefs.h which will include the struct to be used as well as the prototypes of the functions for the slist. Note that slist is a short for single-linked list.
Code:
/**
*
*
* FILE: slistdefs.h
*
*
* Description:
*
* Function defines the structure to be used for the single-linked list,
* as well as the prototypes for the functions to be used for the
* single-linked list.
*
*
*/
#ifndef _slistdefs_h
#define _slistdefs_h
#include <stdio.h>
#include <stdlib.h>
/**
*------------------------------------------------------------
*
* Node for the single-linked list has two members:
*
* 1) a integer value which is unique in the single-linked list.
*
* 2) a pointer to the next node in the list which has larger value,
* since nodes are inserted increasingly in the single-linked list
* and each value is unique.
*
*------------------------------------------------------------
*/
struct slist{
[i]int[/i] value;
[i]struct slist[/i] *next;
};
/**
*
*
* Synopsis:
*
* #include <stdio.h>
* #include <stdlib.h>
*
* void insertValue( struct slist **head, int value )
*
*
* Description:
*
* Function insertValue adds a new struct slist node in the
* single-linked list with the value specified as parameter.
* The struct slist node is inserted increasingly according to the
* values of the struct slist nodes.
*
*
* Parameters:
*
* head: pointer to the head of the single-linked list.
*
* value: value of the new struct slist node to be inserted.
*
*
* Assertions:
*
* none.
*
*
* Returns:
*
* Nothing.
*
*
*/
[i]void[/i] [b]insertValue[/b]( struct slist **head, int value );
/**
*
*
* Synopsis:
*
* #include <stdio.h>
*
* struct slist **searchValue( struct slist **head, int value )
*
*
* Description:
*
* Function searchValue, traverses the single-linked list and searches
* for a struct slist node with the value given as parameter.
*
*
* Parameters:
*
* head: pointer to the head of the single-linked list.
*
* value: value to be searched for in the single-linked list.
*
*
* Assertions:
*
* none.
*
*
* Returns:
*
* Function searchValue, returns NULL if no struct slist node
* is in the single-linked list with that value.
*
* Otherwise, it returns the address of the pointer that points to the
* struct slist node with that value. That is the head of the list if the
* first struct slist node contains that value, or the struct slist next pointer
* of the previous struct slist node from the one that has that value.
*
*
*/
[i]struct slist[/i] **[b]searchValue[/b]( struct slist **head, int value );
/**
*
*
* Synopsis:
*
* #include <stdio.h>
* #include <stdlib.h>
*
* void deleteValue( struct slist **head, int value )
*
*
* Description:
*
* Function deleteValue searches the single-linked list for
* a struct slist node with the value given as parameter and deletes
* it from the single-linked list.
*
*
* Parameters:
*
* head: pointer to the head of the single-linked list.
*
* value: value of the struct slist node to be deleted.
*
*
* Assertions:
*
* none.
*
*
* Returns:
*
* Nothing.
*
*
*/
[i]void[/i] [b]deleteValue[/b]( struct slist **head, int value );
/**
*
*
* Synopsis:
*
* #include <stdio.h>
*
* void printValues( struct slist *head )
*
*
* Description:
*
* Function printValues prints on stdout the values of the
* struct slist nodes of the single-linked list.
*
*
* Parameters:
*
* head: pointer to the first node in the single-linked list, or NULL
* if list is empty.
* Gets the value of the head pointer.
*
*
* Assertions:
*
* none.
*
*
* Returns:
*
* Nothing.
*
*
*/
[i]void[/i] [b]printValues[/b]( struct slist *head );
/**
*
*
* Synopsis:
*
* #include <stdio.h>
* #include <stdlib.h>
*
* void freeValues( struct slist **head )
*
*
* Description:
*
* Function freeValues frees all the struct slist nodes
* of the single-linked list.
*
*
* Parameters:
*
* head: pointer to the head of the single-linked list.
*
*
* Assertions:
*
* none.
*
*
* Returns:
*
* Nothing.
*
*
*/
void [b]freeValues[/b]( struct slist **head );
#endif
Now, lets make the other files for each of the functions:
Code:
/**
*
*
* FILE: deleteValue.c
*
*
* Description:
*
* File contains deleteValue function as declared in slistdefs.h file.
*
*
*/
#include "slistdefs.h"
/**
*------------------------------------------------------------
*
* Insert a struct slist node in the single-linked list.
*
*------------------------------------------------------------
*/
[i]void[/i] [b]deleteValue[/b]( struct slist **head, int value ){
struct slist **deleteNode = searchValue( head, value );
/** node to be deleted exists */
if ( deleteNode != NULL ){
/** keep node to be deleted to free later */
struct slist *freeNode = *deleteNode;
/**
*
* deleteNode points to the pointer that points to the
* node to be deleted.
* This pointer must no longer point to that node, but the node
* after that, or NULL if no node exits. In either case, the next
* pointer of the node to be deleted contains the answer...
*
*/
*deleteNode = ( *deleteNode )->next;
free( freeNode );
}
} // void deleteValue( struct slist **head, int value )
Code:
/**
*
*
* FILE: insertValue.c
*
*
* Description:
*
* File contains insertValue function as declared in slistdefs.h file.
*
*
*/
#include "slistdefs.h"
/**
*------------------------------------------------------------
*
* Insert a struct slist node in the single-linked list.
*
*------------------------------------------------------------
*/
[i]void[/i] [b]insertValue[/b]( struct slist **head, int value ){
/** pointer to the new struct slist node */
struct slist *add;
/**
*
* struct slist **p : *p is the pointer that points to the node
* that has value larger than the value of the new node to be inserted.
* That pointer must be made to point to the new node, and the next
* pointer of the new node must be made to point to whatever *p points
* at.Note, that *p might be the head of the single-linked list if the list is
* empty,or the next pointer of the last node, if the new one has the
* largest value.
*
*/
struct slist **p;
if ( ( add = ( struct slist * )malloc( sizeof( struct slist ) ) ) == NULL ){
( void )fprintf( stderr, "\nerror allocating memory%c", '\0' );
exit( EXIT_FAILURE );
}
for ( p = head ; *p != NULL && ( *p )->value <= value ; p = &( ( *p )->next ) ){
if ( ( *p )->value == value ){
/** do nothing; value already in list */
return ;
}
}
add->value = value;
/** add points to the node with > value ; NULL if in the end or start */
add->next = *p;
/** head, or next pointer of previous node points to the new node */
*p = add;
} // void insertValue( struct slist **head, int value )
Code:
/**
*
*
* FILE: searchValue.c
*
*
* Description:
*
* File contains searchValue function as declared in slistdefs.h file.
*
*
*/
#include "slistdefs.h"
/**
*------------------------------------------------------------
*
* Insert a struct slist node in the single-linked list.
*
*------------------------------------------------------------
*/
[i]struct slist[/i] **[b]searchValue[/b]( struct slist **head, int value ){
for ( ; *head != NULL && ( *head )->value <= value ; head = &( ( *head )->next ) ){
if ( ( *head )->value == value ){
/** value found in slist */
return ( head );
}
}
/** value not found in slist */
return ( NULL );
} // struct slist **searchValue( struct slist **head, int value )
Code:
/**
*
*
* FILE: printValues.c
*
*
* Description:
*
* File contains printValues function as declared in slistdefs.h file.
*
*
*/
#include "slistdefs.h"
/**
*------------------------------------------------------------
*
* Print values from the struct slist nodes in the single-linked list.
*
*------------------------------------------------------------
*/
[i]void[/i] [b]printValues[/b]( struct slist *head ){
for ( ; head != NULL ; head = head->next ){
printf( "\nValue:\t%d\n", head->value );
}
} // void printValues( struct slist *head )
Code:
/**
*
*
* FILE: freeValues.c
*
*
* Description:
*
* File contains freeValues function as declared in slistdefs.h file.
*
*
*/
#include "slistdefs.h"
/**
*------------------------------------------------------------
*
* Free all the struct slist nodes in the single-linked list.
*
*------------------------------------------------------------
*/
[i]void[/i] [b]freeValues[/b]( struct slist **head ){
/**
*
* previousNode: points to the node to be freed.
*
* nextNode: points to the next node from the one to be freed. Keep the
* single-linked list
* in this way.
*
*/
struct slist *previousNode, *nextNode;
/**
*
* previousNode points to the node to be freed.
* Before it gets freed, however, nextNode must be made to point to the
* next node from the one
* that previousNode points at. Note that in each step, previousNode
* must be made to point to nextNode
* so as nextNode will always point to the struct slist node that is the
* next from the the
* one that previousNode points at.
*
*/
for ( previousNode = nextNode= *head ; previousNode != NULL ; previousNode = nextNode ){
nextNode = previousNode->next;
free( previousNode );
}
/**
*
* Safely, make the head of the single-linked list NULL.
* If this is not made, any attempt to insert, delete, search or print
* will fail.
*
*/
*head = NULL;
} // void freeValues( struct slist **head )
The code is ready to copy and paste so as you can immediately run test and modify the functions so as to cover your needs.
You can add messages when for example a value does not exist when deleting; you might want to inform user that no deletion was made. You can add prints in many other places too. Add assertions to check that each value is unique.
You can add more functions to practise a bit on single-linked list, or change entirely the concept of the code i present.
You can write a function int getLength( struct slist *head ) that returns the number of nodes in the list.
Write functions to return nodes with the lower and greater value, and for more challenging ones function to copy a list to another or a function to reverse the list. Try to write recursive versions of some of the functions as well.
Except to see more data types and code for them, like double-linked list and binary search tree.