Linked List C programming

Linked List

A linked list is a linear collection of self-referential structures, called nodes, connected by pointer links—hence, the term “linked” list.

A linked list is accessed via a pointer to the first node of the list. Subsequent nodes are accessed via the link pointer member stored in each node.

By convention, the link pointer in the last node of a list is set to NULL to mark the end of the list.

A linked list is appropriate when the number of data elements to be represented in the data structure is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary.

Linked lists become full only when the system has insufficient memory to satisfy dynamic storage allocation requests.

Function Insert

Function insert receives the address of the list and a character to be inserted. The list’s address is necessary when a value is to be inserted at the start of the list.

Providing the address enables the list to be modified via a call by reference. Because the list itself is a pointer, passing its address creates a pointer to a pointer.

The following code demonstrates the insert function


    // insert a new value into the list in sorted order
    void insert( ListNodePtr *sPtr, char value ) { 
    ListNodePtr newPtr; // pointer to new node
    ListNodePtr previousPtr; // pointer to previous node in list
    ListNodePtr currentPtr; // pointer to current node in list
    newPtr = malloc( sizeof( ListNode ) ); // create node
    if ( newPtr != NULL ) { // is space available
      newPtr->data = value; // place value in node
      newPtr->nextPtr = NULL; // node does not link to another node
      previousPtr = NULL;
      currentPtr = *sPtr;
    
    // loop to find the correct location in the list       
    while ( currentPtr != NULL && value > currentPtr->data ) {
         previousPtr = currentPtr; // walk to ...               
         currentPtr = currentPtr->nextPtr; // ... next node 
      } // end while                                         
    
    // insert new node at beginning of list
      if ( previousPtr == NULL ) { 
         newPtr->nextPtr = *sPtr;
         *sPtr = newPtr;
      } // end if
      else { // insert new node between previousPtr and currentPtr
         previousPtr->nextPtr = newPtr;
         newPtr->nextPtr = currentPtr;
      } // end else
      } // end if
      else {
      printf( "%c not inserted. No memory available.\n", value );
      } // end else
      } // end function insert

Function Delete

Function delete receives the address of the pointer to the start of the list and a character to be deleted.

Deleting a character from the list :

If the character to be deleted matches the character in the first node of the list, free the memory pointed to by tempPtr, and return the character that was deleted.


    // delete a list element
    char delete( ListNodePtr *sPtr, char value ){ 
    ListNodePtr previousPtr; // pointer to previous node in list
    ListNodePtr currentPtr; // pointer to current node in list
    ListNodePtr tempPtr; // temporary node pointer
    
    // delete first node
    if ( value == ( *sPtr )->data ) { 
      tempPtr = *sPtr; // hold onto node being removed
      *sPtr = ( *sPtr )->nextPtr; // de-thread the node
      free( tempPtr ); // free the de-threaded node
      return value;
    } // end if
    else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->nextPtr;
    
    // loop to find the correct location in the list
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr; // walk to ...  
         currentPtr = currentPtr->nextPtr; // ... next node  
      } // end while
    
    // delete node at currentPtr
      if ( currentPtr != NULL ) { 
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         free( tempPtr );
         return value;
        } // end if
       } // end else
    return '\0';
    } // end function delete

Ads Right