Skip to main content

Linked List Quiz - Part I

A short while back, Azhagu quizzed me on linked list based problems; singly linked list.

I am recording those problems, solutions and my experience as a two part series. In the first part, I am introducing the linked list class, which I wrote for packaging the implementation of the solutions. This class pertains to the context of the problem(s) and cannot be used as a general purpose linked list. A std::list might more pertinent in the context of the general purpose implementation of a list.

Here are some of the problems that Azhagu asked me to solve:-
  1. Reverse the list recursively
  2. Reverse the list iteratively
  3. Find if the list is cyclic
  4. Find the node that causes the cycle (and break the cycle)
  5. Reverse every K nodes in the list
I will be solving reversing the list (both iteratively and recursively) and finding if the list is cyclic problems in this episode.

#pragma once

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class LinkedList
{
public: class Node
        {
        private: T item;
        private: Node* next;

        public: Node(const T& item)
                {
                     this->item = item;
                     this->next = nullptr;
                }

        public: Node(const T& item, Node* next)
                {
                     this->item = item;
                     this->next = next;
                }

        public: T& Item()
                {
                     return this->item;
                }

        public: const T& Item() const
                {
                     return this->item;
                }

        public: LinkedList<T>::Node*& Next()
                {
                     return this->next;
                }
        };

private: LinkedList<T>::Node* root;
private: LinkedList<T>::Node* end;

public: LinkedList()
        {
           root = end = nullptr;
        }

public: ~LinkedList()
        {
            // If a cycle exists, break it; else the delete loop
            // below will never end, and lead to undefined behavior/crash.
            if (IsCyclic())
            {
               auto cyclicNode = FindCyclicNode();
               cyclicNode->Next() = nullptr;
            }

            // Delete all nodes
            auto current = root;
            while (current != nullptr)
            {
               auto temp = current->Next();
               delete current;
               current = temp;
            }
        }

public: Node* operator[](int index) const
        {
            return GetNthNode(index);
        }

public: LinkedList<T>::Node* GetNthNode(int index) const // index is zero-based.
        {
            auto node = root;
            while (index >= 0 && node != nullptr)
            {
               node = node->Next();
               --index;
            }

            return node;
        }

public: Node* Append(T item)
        {
           Node* node = new Node(item);
           if (root == nullptr)
           {
              root = end = node;
           }
           else
           {
              end->Next() = node;
              end = node;
           }

           return node;
        }

public: LinkedList<T>::Node* Root() const
        {
           return this->root;
        }

public: void Print(std::ostream& ostr = std::cout,
           const std::string& separator = " -> ",
           const std::string& terminator = "\r\n")
        {
           Node* currentNode = root;

           while (currentNode != nullptr)
           {
              const bool lastNode = currentNode->Next() == nullptr;
              const std::string linkText = (lastNode ? "" : separator);
              ostr << currentNode->Item() << linkText.c_str();

              currentNode = currentNode->Next();
           }

           ostr << terminator.c_str();
        }

public: void ReverseIteratively();
public: void ReverseRecusively();
public: bool IsCyclic() const;

private: Node* UnitReverse(Node* current, Node* next);
}

The above list class allows creating cycles in the list (see Node::Next() method). The Node::Next method returns a reference to the next item pointer in the list, which allows pointing it to a previous Node in the list. The linked list class will be improved based on the problem being solved.

Since reversing the list recursively came to me naturally, I'll go with it first. It was natural since the unit work of reversal involving current and next pointers is repeated until there are no more nodes in the list.

void LinkedList::ReverseRecursively()
{
   root = UnitReverse(root, nullptr);
}

Node* LinkedList::UnitReverse(Node* current, Node* next)
{
   if (current == nullptr)
   {
      return nullptr;
   }

   if (next == nullptr)
   {
      // First time call.
      next = current->Next();
      current->Next() = nullptr;
      end = current;
   }

   Node* nextNext = next->Next();
   next->Next() = current;

   if (nextNext == nullptr)
   {
      // Reached end of list!
      return next;
   }

   return UnitReverse(next, nextNext);
}

Iterative version of reversal. Cute, eh!

void LinkedList::ReverseIteratively()
{
   Node* current = this->root;
   Node* prev = nullptr;
   Node* next = nullptr;

   while (current != nullptr)
   {
     next = current->Next();
     current->Next() = prev;

     if (next == nullptr)
     {
        break;
     }

     prev = current;
     current = next;
   }

   this->end = this->root;
   this->root = current;   
}

A cycle in a list is where the next pointer of the current node points to one of the previous nodes in the list; like the one below.

1 -> 2 -> 3 -> 4 -> 5 ->
             ^-----------------|

Above, the list doesn't end at 5, instead cycles back to 3. And as everybody knows, a traversal of the nodes in the list would never end. If one was using a traditional list implementation, it would not have allowed creating cycle(s) deliberately. However, the data from which the list is created may bear cycles or back references, in which case the data is assumed to corrupt. For instance, an employee reporting to manager, and the manager reporting back to the employee. But our list implementation above, for the purposes of illustration of the problem at hand, allows creating cycles. And we will see a solution later to resolve them too.

Finding if there is a cycle in the list was tough for me. I sort of need a hammer and some hints from Azhagu. But implementing it was fun, as always!

bool IsCyclic() const
{   
   auto jmpBy1Ptr = root;
   auto jmpBy2Ptr = root;

   while (jmpBy1Ptr != nullptr
      && jmpBy2Ptr != nullptr
      && jmpBy2Ptr->Next() != nullptr)
   {
      jmpBy1Ptr = jmpBy1Ptr->Next();
      jmpBy2Ptr = jmpBy2Ptr->Next()->Next();

      if (jmpBy1Ptr == jmpBy2Ptr)
      {
         cout << "Stop node is " << jmpBy1Ptr->Item() << std::endl;
         return true;
      }
   }

   return false;
}

Here is some code to test the above methods:-

void main()
{
   LinkedList<int> ll;
   LinkedList<int>::Node* lastNode = nullptr;

   for (int i = 1; i <= 10; ++i)
   {
      lastNode = ll.Append(i);
   }

   cout << "Initial Sequence...." << std::endl;
   ll.Print();

   cout << "Reverse (iteratively)..." << std::endl;
   ll.ReverseIteratively();
   ll.Print();

   cout << "Reverse (recursively).....Back to original sequence!" << std::endl;
   ll.ReverseRecursively();
   ll.Print();

   // This should return false, as the list has no cycles yet.
   cout << "IsCyclic: " << ll.IsCyclic() << std::endl;

   // Get the 4th node from root (element 4)
   auto node = ll.Root()->Next()->Next()->Next();
   
   // Point the last node to the 4th node (a previous node in the list).
   // This creates a cycle or loop.
   lastNode->Next() = node;

   // This should return true now!
   cout << "IsCyclic: " << ll.IsCyclic() << std::endl;
}

We'll see the rest of the problems in the next episode. Let me know your comments on the solution, implementation, and bugs if any!

Comments

Unknown said…
Thanks a lot for sharing. Nice post. Game Developer.

Popular posts from this blog

Implementing COM OutOfProc Servers in C# .NET !!!

Had to implement our COM OOP Server project in .NET, and I found this solution from the internet after a great deal of search, but unfortunately the whole idea was ruled out, and we wrapped it as a .NET assembly. This is worth knowing. Step 1: Implement IClassFactory in a class in .NET. Use the following definition for IClassFactory. namespace COM { static class Guids { public const string IClassFactory = "00000001-0000-0000-C000-000000000046"; public const string IUnknown = "00000000-0000-0000-C000-000000000046"; } /// /// IClassFactory declaration /// [ComImport(), InterfaceType(ComInterfaceType.InterfaceIsIUnknown), Guid(COM.Guids.IClassFactory)] internal interface IClassFactory { [PreserveSig] int CreateInstance(IntPtr pUnkOuter, ref Guid riid, out IntPtr ppvObject); [PreserveSig] int LockServer(bool fLock); } } Step 2: [DllImport("ole32.dll")] private static extern int CoR

Extension Methods - A Polished C++ Feature !!!

Extension Method is an excellent feature in C# 3.0. It is a mechanism by which new methods can be exposed from an existing type (interface or class) without directly adding the method to the type. Why do we need extension methods anyway ? Ok, that is the big story of lamba and LINQ. But from a conceptual standpoint, the extension methods establish a mechanism to extend the public interface of a type. The compiler is smart enough to make the method a part of the public interface of the type. Yeah, that is what it does, and the intellisense is very cool in making us believe that. It is cleaner and easier (for the library developers and for us programmers even) to add extra functionality (methods) not provided in the type. That is the intent. And we know that was exercised extravagantly in LINQ. The IEnumerable was extended with a whole lot set of methods to aid the LINQ design. Remember the Where, Select etc methods on IEnumerable. An example code snippet is worth a thousand

sizeof vs Marshal.SizeOf !!!

There are two facilities in C# to determine the size of a type - sizeof operator and Marshal.SizeOf method. Let me discuss what they offer and how they differ. Pardon me if I happen to ramble a bit. Before we settle the difference between sizeof and Marshal.SizeOf , let us discuss why would we want to compute the size of a variable or type. Other than academic, one typical reason to know the size of a type (in a production code) would be allocate memory for an array of items; typically done while using malloc . Unlike in C++ (or unmanaged world), computing the size of a type definitely has no such use in C# (managed world). Within the managed application, size does not matter; since there are types provided by the CLR for creating\managing fixed size and variable size (typed) arrays. And as per MSDN, the size cannot be computed accurately. Does that mean we don't need to compute the size of a type at all when working in the CLR world? Obviously no, else I would