Explaining C linked lists

This repository aims to collect the most useful tips and tricks when dealing with linked lists.

[ ! ] WARNING

At the moment the code is italian commented.

Table of Contents

---

1. Structs used
2. Recurring algorithm patterns
   1. Iterative creation of a list
   2. Recursive creation of a list
   3. Iterative deleting node
   4. Recursive insert node after
3. Functions
   1. viewlist
   2. viewlistC
   3. createListseq
   4. createListrec
   5. removeVal

---

Structs used

Two main node structure. node aims to contain integer values , nodeC char values. They're pretty similar: First field contains the (int/char) value, the second one a pointer to the next (same structure) node.

Recurring algorithm patterns

---

When dealing with creation of a list, insering and deleting a node, there are recurring functions patterns:

Iterative creation of a list

    node *tail=NULL;
    while ( /*CONDITION TO STOP NODE CREATION*/ )
    {
        if (head == NULL)
        {
            head = malloc(sizeof(node));
            tail = head;
            head->value = /*VALUE*/ ;
            head->nextNode = NULL;
        }
        else
        {
            node *temp = malloc(sizeof(node));
            tail->nextNode = temp;
            tail = temp;
            temp->value = /*VALUE*/ ;
            temp->nextNode = NULL;
        }
        //...OTHER INSTRUCTION FOR CONDITION
    }
    return head;

---

Recursive creation of a list

node *recursive(node *head, /*VARIABLE FOR ITERATION*/ )
{
    if ( /*CONDITION TO STOP NODE CREATION*/ )
    {
        return NULL;
    }
    if (head == NULL)
    {
        head = malloc(sizeof(node));
        head->value = /*VALUE*/ ;
        head->nextNode = recursive(head->nextNode,
        /*MODIFIED VARIABLE FOR ITERATION*/);
        return head;
    }
    else
    {
        node *temp = malloc(sizeof(node));
        temp->value = /*VALUE*/;
        temp->nextNode = recursive(head->nextNode,
        /*MODIFIED VARIABLE FOR ITERATION*/);
        return temp;
    }
}

---

Iterative deleting node

    node *temp = head;
    node *previous = NULL;
    node *newHead = head;
    while (temp != NULL)
    {
        if (/*NODE CONDITION TO GET DELETED*/)
        {
            if (previous != NULL) 
            {
                previous->nextNode = temp->nextNode;
                node *toFREE=temp;
                temp = temp->nextNode;
                free(toFREE);
            }
            else 
            {
                node *toFREE=temp;
                temp = temp->nextNode;
                newHead = temp;
                free(toFREE);
            }
        }
        else
        {
            previous = temp;
            temp = temp->nextNode;
        }
    }
    return newHead;

---

Recursive insert node after

   
node *insertion(node *head)
{
    if(head==NULL)
    {
        return NULL;
    }
    else
    {
        if(/*INSERT CONDITION*/)
        {
            node *toINSERT = malloc(sizeof(node));
            toINSERT->value= /*VALUE*/;
            toINSERT->nextNode=head->nextNode;
            head->nextNode=toINSERT;
        }
        return insertion(head->nextNode);
    }
}

---

Functions

---

All functions are written in lib.c file. Below are explained.

viewlist (node *head)

• description:
  Recursively print all linked nodes form a given head pointer.
• param:
  node *head: pointer to the first node of the linked list.
• return:
  void
• see:
  prints only node type of nodes.

Space complexity	Time complexity
O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. Max activation record invoked are given by the number of nodes in the linked list.	O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. The number of iterations is equal to the time complexity of the function, since this number is dependent by the maximum number of records invoked, those values are the same.

Execution

viewlistC (nodeC *head)

• description:
  Recursively print all linked nodes form a given head pointer.
• param:
  nodeC *head: pointer to the first node of the linked list.
• return:
  void
• see:
  prints only nodeC type of nodes.

Space complexity	Time complexity
O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. Max activation record invoked are given by the number of nodes in the linked list.	O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. The number of iterations is equal to the time complexity of the function, since this number is dependent by the maximum number of records invoked, those values are the same.

Execution:
see viewlist.

createLISTseq (node *head, int pos)

• description:
  Sequentially create a list with random value between 0 and GENMAX.
• param:
  node *head: pointer to the first node of the linked list.
  int pos: number of nodes to generate.
• return:
  node *
• see:
  -

Space complexity	Time complexity
O ( 1 ) The fuction is called once.	O ( pos ) pos + 1 is the maximum number of iterations (due to number of comparison in the while loop), with high values the +1 term will not affect the curve described by the function, so its negligible.

Execution:

createLISTrec (node *head, int pos)

• description:
  Recursively create a list with random value between 0 and GENMAX.
• param:
  node *head: pointer to the first node of the linked list.
  int pos: number of nodes to generate.
• return:
  node *
• see:
  -

Space complexity	Time complexity
O ( pos ) Max activation record invoked are given by the number of nodes in the linked list.	O ( pos ) pos + 1 is the maximum number of comparison made, at least once when the function is called. At high values of pos, +1 will be negligible.

Execution:

createLISTseqUSER(node *head)

• description:
  Sequentially create a list using value inserted by user.
• param:
  node *head: pointer to the first node of the linked list.
• return:
  node *
• see:
  -

Space complexity	Time complexity
O ( 1 ) The fuction is called once.	O ( mod(val) ) where mod() is a function that returns the number of modification to the value in input. Actually it would be O(mod(val-1)), beacause the first assignment is indipendent by the while loop.

Execution:
See createLISTseq

createLISTrecUSER(node *head)

• description:
  Recursively create a list using value inserted by user.
• param:
  node *head: pointer to the first node of the linked list.
• return:
  node *
• see:
  -

Space complexity	Time complexity
O ( mod( val ) ) where mod() is a function that returns the number of modification to the value in input. Activation records are invoked till val value is 0.	O ( mod( val ) ) where mod() is a function that returns the number of modification to the value in input. This number is dependent by the maximum number of records invoked which is dependent by user input.

Execution:
See createLISTrec

createLISTseqFILE(nodeC *head,char path[])

• description:
  Sequentially create a list by characters in a file.
• param:
  nodeC *head: pointer to the first node of the linked list.
  char path[]: pointer to the char array containing the path of the file.
• return:
  nodeC *
• see:
  -

Space complexity	Time complexity
O ( 1 ) The fuction is called once.	O ( charnumber(fp) ) where charnumber() is a function that returns the number of ASCII characters in the file pointer fp.

Execution:
See createLISTseq

createLISTrecFILE(nodeC *head,FILE *fp)

• description:
  Recursively create a list by characters in a file.
• param:
  nodeC *head: pointer to the first node of the linked list.
  FILE *fp: pointer to the file stream.
• return:
  nodeC *
• see:
  -

Space complexity	Time complexity
O ( charnumber(fp) ) where charnumber() is a function that returns the number of ASCII characters in the file pointer fp. Max activation record invoked are given by the final number of nodes in the linked list +1.	O ( charnumber(fp) ) where charnumber() is a function that returns the number of ASCII characters in the file pointer fp.

Execution:
See createLISTrec

findVAL(node *head,int val)

• description:
  Recursively count number of nodes containing val in a given linked list.
• param:
  node *head: pointer to the first node of the linked list.
  int val: value to find.
• return:
  int
• see:
  -

Space complexity	Time complexity
O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. Max activation record invoked are given by the number of nodes in the linked list.	O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list.

Execution:

removeVAL (node *head,int val)

• description:
  Remove all nodes containing the value val from the linked list pointed by head
• param:
  node *head: pointer to the first node of the linked list.
  int val: value to delete.
• return:
  node *
• see:
  -

Space complexity	Time complexity
O ( 1 ) The fuction is called once.	O ( len( list )) where len() is a function returning the node number of the list and list is the object representing the linked list.

Execution:

findCHAR(nodeC *head, char c)

• description:
  Recursively count number of nodes containing c character in a given linked list.
• param:
  nodeC *head: pointer to the first node of the linked list.
  char c: character to find
• return:
  int
• see:
  -

Space complexity	Time complexity
O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. Max activation record invoked are given by the number of nodes in the linked list.	O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list.

Execution:
See findval

selectiveUPPER(nodeC *head, char c)

• description:
  Recursively transform all c characters into capital letters in a given linked list.
• param:
  nodeC *head: pointer to the first node of the linked list.
  char c: character to up.
• return:
  nodeC *
• see:
  -

Space complexity	Time complexity
O ( len( list ) ) where len() is a function returning the node number of the list and list is the object representing the linked list. Max activation record invoked are given by the number of nodes in the linked list.	[Time complexity]

Execution:
See findval