reverse_a_linked_list.cpp File Reference

Implementation of Reversing a single linked list More...

#include <cassert>
#include <iostream>
#include <new>

Include dependency graph for reverse_a_linked_list.cpp:

Go to the source code of this file.

Classes
class	data_structures::linked_list::Node
class	data_structures::linked_list::list

Namespaces
namespace	data_structures
	for IO operations
namespace	linked_list
	Functions for singly linked list algorithm.

Functions
Node *	data_structures::linked_list::copy_all_nodes (const Node *const node)
	creates a deep copy of a list starting at the input node
static void	test ()
	Self-test implementations.
void	test_copy_constructor ()
void	test_assignment_operator ()
int	main ()
	Main function.

Detailed Description

Implementation of Reversing a single linked list

The linked list is a data structure used for holding a sequence of values, which can be added, displayed, reversed, or removed.

Algorithm

Values can be added by iterating to the end of a list (by following the pointers) starting from the first link. Whichever link points to null is considered the last link and is pointed to the new value.

Linked List can be reversed by using 3 pointers: current, previous, and next_node; we keep iterating until the last node. Meanwhile, before changing to the next of current, we store it in the next_node pointer, now we store the prev pointer in the current of next, this is where the actual reversal happens. And then we move the prev and current pointers one step forward. Then the head node is made to point to the last node (prev pointer) after completion of an iteration.

A graphic explanation and view of what's happening behind the scenes

Definition in file reverse_a_linked_list.cpp.

Function Documentation

copy_all_nodes()

Node * data_structures::linked_list::copy_all_nodes

(

const Node *const

node

)

creates a deep copy of a list starting at the input node

Parameters

[in]

node

pointer to the first node/head of the list to be copied

Returns

pointer to the first node/head of the copied list or nullptr

Definition at line 53 of file reverse_a_linked_list.cpp.

                                             {
    if (node) {
        // NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
        Node* res = new Node();
        res->val = node->val;
        res->next = copy_all_nodes(node->next);
        return res;
    }
    return nullptr;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 301 of file reverse_a_linked_list.cpp.

           {
    test();  // run self-test implementations
    test_copy_constructor();
    test_assignment_operator();
    return 0;
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 228 of file reverse_a_linked_list.cpp.

                   {
    data_structures::linked_list::list L;
    // 1st test
    L.insert(11);
    L.insert(12);
    L.insert(15);
    L.insert(10);
    L.insert(-12);
    L.insert(-20);
    L.insert(18);
    assert(L.top() == 11);
    assert(L.last() == 18);
    L.reverseList();
    // Reversal Testing
    assert(L.top() == 18);
    assert(L.traverse(1) == -20);
    assert(L.traverse(2) == -12);
    assert(L.traverse(3) == 10);
    assert(L.traverse(4) == 15);
    assert(L.traverse(5) == 12);
    assert(L.last() == 11);
    std::cout << "All tests have successfully passed!" << std::endl;
}

test_assignment_operator()

void test_assignment_operator

(

)

Definition at line 274 of file reverse_a_linked_list.cpp.

                                {
    data_structures::linked_list::list L;
    data_structures::linked_list::list otherList;
    L.insert(10);
    L.insert(20);
    L.insert(30);
    otherList = L;
 
    otherList.insert(40);
    L.insert(400);
 
    assert(L.top() == 10);
    assert(otherList.top() == 10);
    assert(L.traverse(1) == 20);
    assert(otherList.traverse(1) == 20);
 
    assert(L.traverse(2) == 30);
    assert(otherList.traverse(2) == 30);
 
    assert(L.last() == 400);
    assert(otherList.last() == 40);
}

test_copy_constructor()

void test_copy_constructor

(

)

Definition at line 252 of file reverse_a_linked_list.cpp.

                             {
    data_structures::linked_list::list L;
    L.insert(10);
    L.insert(20);
    L.insert(30);
    data_structures::linked_list::list otherList(L);
    otherList.insert(40);
 
    L.insert(400);
 
    assert(L.top() == 10);
    assert(otherList.top() == 10);
    assert(L.traverse(1) == 20);
    assert(otherList.traverse(1) == 20);
 
    assert(L.traverse(2) == 30);
    assert(otherList.traverse(2) == 30);
 
    assert(L.last() == 400);
    assert(otherList.last() == 40);
}