trjhtr

I want to improve this code using STL or with better logic. I have not written code for delete function or for copy constructor or move constructor. My aim to learn to exchange even and odd elements.

#include <iostream>
#include <utility>
#include <cassert>

class LinkedList

 struct Node
 
 int data;
 Node * next = nullptr;
 Node(int value) : data(std::move(value)), next(nullptr) 
 ;
 Node *head;

public:
 LinkedList() : head(nullptr) 
 ~LinkedList()
 
 Node *tmp = nullptr;
 while (head)
 
 tmp = head;
 head = head->next;
 delete tmp;
 
 head = nullptr;
 

 void insert(int);
 void exchangeEvenOdd();
 void printList() const;

private:
 static void advance(Node*& node)
 
 assert (node != nullptr);
 node = node->next;
 

 Node* getLastNode()
 
 Node *node = head;
 while (node->next != nullptr)
 node = node->next;

 return node;
 

 bool isOdd(int num)
 
 if (num % 2 != 0)
 return true;
 else
 return false;
 
;

void LinkedList::insert(int value)

 Node *node = new Node(std::move(value));
 Node *tmp = head;
 if (tmp == nullptr)
 
 head = node;
 
 else
 
 tmp = getLastNode();
 tmp->next = node;
 


void LinkedList::exchangeEvenOdd()

 Node *node = nullptr;
 Node *lastNodeToTest = getLastNode();
 Node *tail = lastNodeToTest;

 while (isOdd(head->data) == true)
 
 node = head;
 advance(head);
 tail->next = node;
 advance(tail);
 

 Node *tmp = head;
 Node *curr = head;

 while (tmp->next != lastNodeToTest)
 
 if (isOdd(curr->next->data) == true)
 
 node = curr->next;
 curr->next = node->next;
 tail->next = node;
 advance(tail);
 
 else
 
 //advance "curr" and "tmp" only when next node to it is even
 advance(curr);
 advance(tmp);
 
 

 if (isOdd(curr->next->data) == true && tmp->next == lastNodeToTest)
 
 node = lastNodeToTest;
 curr->next = lastNodeToTest->next;
 tail->next = lastNodeToTest;
 advance(tail);
 
 tail->next = nullptr;
 lastNodeToTest = nullptr;
 node = nullptr;


void LinkedList::printList() const

 if (head == nullptr)
 
 std::cout << "Empty List n";
 return;
 

 Node *node = head;

 while (node != nullptr)
 
 std::cout << node->data << " ";
 advance(node);
 

 std::cout << "n";


int main()

 LinkedList ll1;
 ll1.insert(1);
 ll1.insert(2);
 ll1.insert(3);
 ll1.insert(4);
 ll1.insert(5);
 ll1.insert(6);
 ll1.insert(7);
 std::cout << "Original List : ";
 ll1.printList();

 ll1.exchangeEvenOdd();
 std::cout << "New List : ";
 ll1.printList();

There are two different things in your code: an implementation of a single-linked list, and an algorithm to make even numbers appear before odd numbers in a list.

Optimally, those two concerns should be separated. It is easier to do one thing well, so your list should focus on providing data management services (inserting, deleting, data access, memory safety, etc.) and your algorithm should use those services to accomplish its task of reordering elements. If you do so, your list's interface will be more concise and your algorithm more general.

The algorithm you're writing is actually a partitioning algorithm, that is one that puts elements satisfying a predicate before elements that don't. It's used in sorting algorithms for example. You can find the following implementation in the reference:

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)

 first = std::find_if_not(first, last, p);
 if (first == last) return first;

 for(ForwardIt i = std::next(first); i != last; ++i)
 if(p(*i))
 std::iter_swap(i, first);
 ++first;
 
 
 return first;
 

You can see from this example implementation that you only need a way to iterate over the elements in your list one after the other, and a way to extract the value at a current position, to make your list interface powerful enough.

The hard but correct way to provide this interface is to provide an iterator class, and two iterator instances, begin and end. Then your list is fully compatible with most STL algorithms (some of them require more powerful iterators than those a single-linked list can expose) and you don't even need to implement the partition algorithm.

The quick and dirty way is to implement the algorithm directly on top of your list's nodes, given that they provide the two necessary functionalities via data and next.

P.S: your exchangeEvenOdd function should return the partition point. It's a valuable information that you have to compute anyway. By the way, the name could be more evocative.