3
\$\begingroup\$

Problem statement :

Implement the following

void split_odd_and_even(LL_LinkedList_t * pList,        //![IN] : This is the input Linked List given to you.
                        LL_Node_t      ** pOddList,     //![OUT]: This is the Head node of the Odd List to be returned 
                        LL_Node_t      ** pEvenList );  //![OUT]: This is the Head node of the Even List to be returned

Conditions :

  1. you cannot create new links/ additional links
  2. the order of the links should remain the same e.g if original list is 1->2->3->4->5 the odd list should be 1->3->5 and even 2->4

Code Review (Expectation): following apply for only implementation of split_odd_and_even Anything outside the function is quick prototyping.

  1. Missing Corner Cases
  2. Pointers for readability for code
  3. Logical Errors (excluding test case code , prototyping code and dead code)

Source Code:

Linklist.h

#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_

typedef unsigned int uint32_t;

typedef struct node_t
{
    uint32_t node_data;
    struct node_t   * pNextNode;
} LL_Node_t;

typedef struct
{
    LL_Node_t * head;
    LL_Node_t * tail;
    uint32_t count;
}LL_LinkedList_t;

void LL_Insert(LL_LinkedList_t * pList, uint32_t data);
void LL_Insert_Tail(LL_LinkedList_t * pList, uint32_t data);
void LL_Remove_Head(LL_LinkedList_t * pList);
void LL_Print_Node(LL_Node_t * pNode);
LL_Node_t * Find_tail_manual(LL_LinkedList_t * pList);
void split_odd_and_even(LL_LinkedList_t * pList,  LL_Node_t ** pOdd_List,LL_Node_t ** pEvenList );
void LL_RemoveNode(LL_LinkedList_t* pList, LL_Node_t * prev, LL_Node_t* current);
#endif

LinkList.c

/********************************************************************************
File:        linked_list.c
Project:
*******************************************************************************/
#include "Linklist.h"
#include <stdio.h>
#include <stdlib.h>

void LL_Init(LL_LinkedList_t * pList)
{
    pList->head = NULL;
    pList->tail = NULL;
    pList->count = 0;
}

void LL_Insert_Tail(LL_LinkedList_t * pList, uint32_t data)
{
   LL_Node_t * tmp = (LL_Node_t *)malloc(sizeof(LL_Node_t));
    tmp->pNextNode = NULL;
    tmp->node_data = data;

   if(pList->count == 0)
   {
       pList->head = tmp;
       pList->tail = tmp;
   }else
   {
       pList->tail->pNextNode = tmp;
       pList->tail = tmp;
   }
   pList->count++;
}

void LL_Insert_Head(LL_LinkedList_t * pList, uint32_t data)
{
    LL_Node_t * tmp = pList->head;

    pList->head = (LL_Node_t *) malloc(sizeof(LL_Node_t));
    pList->tail = tmp;
    pList->count++;
}


void LL_Remove_Head(LL_LinkedList_t * pList)
{
    pList->head = pList->head->pNextNode;
    pList->count--;
}

void LL_Print_Node(LL_Node_t * pNode)
{
    printf("Node Addr: %p \n\t Node Data: %u \n\t pNextNode:%p \n\n",pNode, pNode->node_data, pNode->pNextNode);
}

LL_Node_t * Find_tail_manual(LL_LinkedList_t * pList)
{
    LL_Node_t * curr_node = pList->head;

    while (curr_node->pNextNode != NULL)
    {
        curr_node = curr_node->pNextNode;
    }

    return curr_node;
}

void LL_RemoveNode(LL_LinkedList_t * pList, LL_Node_t * prev, LL_Node_t* current)
{
    if(prev == NULL) //! This means you are trying to remove the head
    {
        pList->head = current->pNextNode;
        return;
    }
    //when node is in middle of the list
    prev->pNextNode = current->pNextNode;

}

void split_odd_and_even(LL_LinkedList_t * pList,  LL_Node_t ** pOddList,LL_Node_t ** pEvenList )
{
    LL_Node_t * current = pList->head;
    LL_Node_t * prev = NULL;
    LL_Node_t * tmp = NULL;
    LL_Node_t * removed_node;

    //! Pretend tail pointer is not available
    LL_Node_t * tail = Find_tail_manual(pList);

    //! Save off the tail
    tmp  = tail;

    // printf("tmp %p tmp %u \n", tmp, tmp->node_data);
    while(current != tmp)
    {
        // printf("current data : %d \n",current->node_data );
        if(current->node_data % 2 == 0)
        {

            //! Current node is removed
            LL_RemoveNode(pList, prev, current);
            removed_node = current;
            // printf("removed data %u\n", current->node_data);

            pList->tail->pNextNode = removed_node;
            pList->tail = removed_node;

            //!
            prev = current;
            current = removed_node->pNextNode;
            removed_node->pNextNode = NULL;
        }
        else
        {
            prev = current;
            current = current->pNextNode;
        }
        // printf("current data end: %d \n",current->node_data );
    }

    //! handling for the last node
    if (current->node_data % 2 == 0)
    {
        //! Current node is removed
        LL_RemoveNode(pList, prev, current);
        removed_node = current;

        //! send the removed node to back of the list
        *pEvenList = current->pNextNode;
        pList->tail->pNextNode = removed_node;
        pList->tail = removed_node;

        //! Close the lists
        current->pNextNode = NULL;
        prev->pNextNode = NULL;

    }else
    {
        *pEvenList = current->pNextNode;
        current->pNextNode = NULL;
    }
    *pOddList = pList->head;
}

void main()
{
    uint32_t i = 0;
    LL_LinkedList_t linklist1;
    LL_Node_t * odd_head;
    LL_Node_t * even_head;

    //! Test Case for Insertion
    LL_Init(&linklist1);
    printf("Init Done!\n");
    for(i=0; i<11; i++)
    {
        LL_Insert_Tail(&linklist1, i);
    }

    //! Prints for visual checking the links (bcus DDD doesnt work on windows >:( ) 
    LL_Node_t * tmp = linklist1.head;
    do
    {
        LL_Print_Node(tmp);
        tmp = tmp->pNextNode;
    }while (tmp != NULL);
    // Find_tail_manual(&linklist1);

    //! Function to split the linklist into odd and even test
    split_odd_and_even(&linklist1, &odd_head, &even_head);
    tmp = odd_head;

    //! More visual checking
    printf("printing_odd_list \n");
    do
    {
        LL_Print_Node(tmp);
        tmp = tmp->pNextNode;
        // printf("tmp->pNextNode\n");
    }while (tmp != NULL);

    tmp = even_head;

    //! Even More visual checking
    // printf("printing_even_list \n");
    do
    {
        // printf("tmp->pNextNode :%p \n",tmp );
        LL_Print_Node(tmp);
        tmp = tmp->pNextNode;
    }while (tmp != NULL);
}

github repo link

\$\endgroup\$
  • 3
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Dec 23 '17 at 0:03
  • 1
    \$\begingroup\$ LL_Insert_Head() appears to be incomplete and not work. LL_Remove_Head() appears to leak memory, and crashes if the list is empty LL_RemoveNode() also leaks memory and does not properly update count. \$\endgroup\$ – Snowbody Jan 10 '18 at 19:24
  • \$\begingroup\$ Gr8 point but the Insert head is only implmented for the test to function and be able to pass in a pointer. But this gave me a hint to a corner case for the implementation which i missed out on what if the input list to split_odd_and_even is a null pointer or has only one element. \$\endgroup\$ – Dexobox Jan 10 '18 at 19:34
4
\$\begingroup\$

This isn't a complete review, it's just a few thoughts from glancing over the code...

Unnecessary casting on malloc

You don't need to cast the returned value from malloc. Adding unnecessary casts, adds noise to the code as well as creating potential problems with future refactoring.

Clean up your comments

Code for review should be presented in as close to its complete state as possible. With this in mind, commented out print statements that have helped you with your debugging should be removed. They add nothing but noise to the code and impair readability.

Naming & Grouping

Most of your operations that function on the linked list have LL_ prefixes which groups the methods together. Two of them don't Find_tail_manual and split_odd_and_even. If these methods are part of the same conceptual block of functionality, they should have the same prefix to complete the grouping. If they aren't, then in the header they should be declared below all of the LL_ methods, not in the middle of them (with LL_RemoveNode below them).

You also want to try to be consistent with your naming for functions. Pick a style and stick to it. Are you starting methods with capital letters Find_tail_manual, or lower case split_odd_and_even, are you using capitalisation to separate words LL_RemoveNode or underscores LL_Remove_Head. When you mix and match styles, it makes the code harder to read and predict if you're changing it.

tmp or tail

In split_odd_and_even, you're creating a tail variable, which you then assign to tmp.

LL_Node_t * tmp = NULL;
LL_Node_t * removed_node;

//! Pretend tail pointer is not available
LL_Node_t * tail = Find_tail_manual(pList);

//! Save off the tail
tmp  = tail;

tail is never used again and tmp is only ever used as an equality check to detect that you've reached the end of the list. Generally, it's better to name things so that they can be recognised, so tmp isn't a great name. Particularly in this case, where you already have a variable that contains the value and has a better name tail. Lose tmp and just do:

LL_Node_t * tail = Find_tail_manual(pList);

while(current != tail)

Then we have the comment...

//! Pretend tail pointer is not available

If you're going to add comments, consider using them to explain 'why' you're doing something in preference of 'what' you're doing. Why are you pretending the pointer isn't there... Doing it manually involves some processing, so there's presumably a reason for it, don't leave the next person to look at the code the task of decoding why you've done it that way, remember they don't have the context that you have when you're recently written the code.

\$\endgroup\$
2
\$\begingroup\$
  1. Missing Corner Cases

    No check for allocation failure.

    Pedantic: no overflow check with pList->count++;

    Many memory leaks - malloc(), yet no corresponding free().

  2. Pointers for readability for code

    Respect presentation width. If posting needed horizontal scroll bars, it is too wide. Use an auto formatter to adjust. Do not maintain formatting manually.

    Assign at declaration. Declare when needed. Rather than the 3 lines, how about 1?:

    //  LL_Node_t * tmp = NULL;
    //  ...
    //  //! Save off the tail
    //  tmp  = tail;
    
    LL_Node_t * tmp = tail; //! Save off the tail
    

    Excessive blank line - not needed.

    {
    
        //! Current node is removed
    

    Why the 1 space indent? A sign of manual formatting. See above point.

    LL_Node_t * tmp = (LL_Node_t *)malloc(sizeof(LL_Node_t));
    tmp->pNextNode = NULL;
    tmp->node_data = data;
    

    Readability includes review. Is the below correct size type? We could look to the header file to find out or .....

    pList->head = (LL_Node_t *) malloc(sizeof(LL_Node_t));
    

    ... use the simple to code, review and update

    pList->head = malloc(sizeof *(pList->head));
    

    Instead of a blank line and //!, how about just a blank line?

  3. Logical Errors

    .

  4. Other problems

    printf("Node Addr: %p ... pNode, yet pointer passed is not void*. This is undefined behavior (UB), but usually works. Compliant alternative printf("Node Addr: %p ... (void *) pNode.

    LL_RemoveNode() does not decrement count;

    No value in printing " \n" versus simply "\n". White-space before '\n' tends to create issues - best avoided.

    void main() may be invalid on various systems-- use a standard int main(void).

    Identifiers ending with _t are reserved by some compilers. Use _T or in this case, just #include <stdint.h> instead of typedef unsigned int uint32_t;


Overall I found split_odd_and_even() excessively cumbersome and so offer a simplification:

void split_odd_and_even(LL_LinkedList_t * pList, LL_Node_t ** pOddList,
    LL_Node_t ** pEvenList) {
  LL_Node_t OddEven_Head[2] = { {.pNextNode = NULL}, {.pNextNode = NULL}};
  LL_Node_t *OddEven[2] = {&OddEven_Head[0], &OddEven_Head[1]};
  LL_Node_t * current = pList->head;

  unsigned oe = 0;
  while (current) {
    OddEven[oe]->pNextNode = current;
    OddEven[oe] = current;
    oe = !oe;
    current = current->pNextNode;
  }
  OddEven[0]->pNextNode = NULL;
  OddEven[1]->pNextNode = NULL;

  *pEvenList = OddEven_Head[0].pNextNode;
  *pOddList = OddEven_Head[1].pNextNode;
  pList->head = pList->tail = NULL;
  pList->count = 0;
}
\$\endgroup\$
  • \$\begingroup\$ Curious why you would say whitespace before '\n' creates issues? \$\endgroup\$ – Dexobox Jan 10 '18 at 19:28
  • \$\begingroup\$ @Dexobox Re: "White-space before '\n' tends to create issues" as it is unexpected and not readily noticeable -like "qwerty\t\n". Example: Consider a line orientated text file that establishes a definition like "abc=def \n" vs "ijk=xyz\n". In the first case, it is not readily identifiable that abc is assigned a 4 character array versus a 3 character one. In the realm of competing styles, best to use the one with least surprises. \$\endgroup\$ – chux Jan 10 '18 at 19:49
1
\$\begingroup\$

Use the standard uint32_t or at least test the size of unsigned int.

    typedef unsigned int uint32_t;  /* NO    */
    #include <stdint.h>             /* YES   */
    /* somewhere in the code... */
    assert(sizeof(unsigned int)==4) /* MAYBE */
\$\endgroup\$
  • \$\begingroup\$ This code is running on a project with non standard compiler and does not have standard libraries like <stdint.h> \$\endgroup\$ – Dexobox Jan 10 '18 at 19:17
  • \$\begingroup\$ @Dexobox Ah. In case stdint.h is missing from the compiler I prefer implementing it myself. The using code is none the wiser, it is clear for most other reviewers of the code what is going on, and in case stdint becomes available for other versions or targets your own file gets shadowed due to inclusion order rules. \$\endgroup\$ – Andreas Jan 11 '18 at 10:18
  • \$\begingroup\$ no i think you fail to understand that the code around the api split_odd_and_even() is ancillary as the definition of uint32_t is defined and controlled by the project settings where the api will eventually reside. The library includes is out of scope for the review either way as mentioned in the problem statement and is simply used for quick prototyping. \$\endgroup\$ – Dexobox Jan 11 '18 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.