Split linked list into odd and even

Question 1

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 :

you cannot create new links/ additional links
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.

Missing Corner Cases
Pointers for readability for code
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

Question 2

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 .

Question 3

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.

Question 4

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.

Question 5

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.

Question 6

Missing Corner Cases

No check for allocation failure.

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

Many memory leaks - malloc(), yet no corresponding free().
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?
Logical Errors

.
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;
}

Question 7

Curious why you would say whitespace before '\n' creates issues?

Question 8

@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.

Question 9

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 */

Question 10

This code is running on a project with non standard compiler and does not have standard libraries like <stdint.h>

Question 11

@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.

Question 12

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.

forsvarir forsvarir 11.8k7 gold badges39 silver badges72 bronze badges · Answer 1 · 2017-12-22 22:40:42Z

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.

chux chux 36.4k2 gold badges43 silver badges96 bronze badges · Answer 2 · 2017-12-23 21:02:12Z

Missing Corner Cases

No check for allocation failure.

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

Many memory leaks - malloc(), yet no corresponding free().
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?
Logical Errors

.
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;
}

Curious why you would say whitespace before '\n' creates issues?
@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.

Andreas Andreas 2062 silver badges4 bronze badges · Answer 3 · 2017-12-23 12:48:45Z

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 */

Share

answered Dec 23, 2017 at 12:48

Andreas's user avatar

Andreas Andreas

2062 silver badges4 bronze badges

\$\endgroup\$

3

\$\begingroup\$ This code is running on a project with non standard compiler and does not have standard libraries like <stdint.h> \$\endgroup\$

Dexobox
– Dexobox

2018年01月10日 19:17:50 +00:00
Commented Jan 10, 2018 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
– Andreas

2018年01月11日 10:18:22 +00:00
Commented Jan 11, 2018 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
– Dexobox

2018年01月11日 18:35:30 +00:00
Commented Jan 11, 2018 at 18:35

Add a comment |

Stack Exchange Network

Split linked list into odd and even

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Hot Network Questions

Split linked list into odd and even

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Related

Hot Network Questions