Solved

finding element within singly linked list

Posted on 2013-07-01
12
1,003 Views
Last Modified: 2013-07-07
I am working on a question and need some help getting this going.


Write a function that would return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. Assume the list size cannot be known without traversing the list.

My assumption:
I will need a class for the code...and then not sure about the test cases....unless unit tests would be the same thing..if so then another class.

I know I want the 5th element from end.

I do not know the end.

I start a count of some sort that looks ahead in the list until it finds the end...and somehow the other count is looking back to the 5th element...not sure how that works ...but sord of can picture this.

Then I am not sure what all you would test...I guess maybe you would test that there is an a value in the list, that the value is hte 5th element, perhaps that there are even 5 elements...not sure what else to test for here.....

Please help
0
Comment
Question by:Robb Hill
  • 7
  • 4
12 Comments
 
LVL 44

Expert Comment

by:AndyAinscow
Comment Utility
Is this list a standard collection (List) or one you have coded yourself ?

There is a LastIndexOf function - is that what you require ?
0
 
LVL 11

Author Comment

by:Robb Hill
Comment Utility
pseudocode would be something like this


Have two pointers p1 and p2 point to head of the list.
Advance p2 five times
Now in a while loop keep advancing p1 and p2.
When p2 hits the end of the list p1 will be at the fifth element

Here is some robust code...that needs to be tweeked...or potentially rewritten to up to date standards....please advise
 static class Program
  {
    private static int index = 0;
    private static ListNode fifthNode = null;
    static int totalNode = 0;
    static void Main()
    {
        ListNode node7 = new ListNode(7, null);
        ListNode node6 = new ListNode(6, node7);
        ListNode node5 = new ListNode(5, node6);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode root = new ListNode(1, node2);

        GetFifthNode(root);//The result;
    }

    private static void CountTotalNode(ListNode curNode)
    {
        if (curNode.NextNode == null)
        {
            return;
        }
        else
        {
            totalNode += 1;
            CountTotalNode(curNode.NextNode);
        }
    }
    private static void GetFifthNode(ListNode curNode)
    {
        if (index == totalNode-5)
        {
            fifthNode = curNode.NextNode;
            return;
        }
        else
        {
            index += 1;
            GetFifthNode(curNode.NextNode);
        }
    }
}

public class ListNode
{
    int _nodeValue;
    ListNode _nextNode;

    public ListNode()
    {
    }
    public ListNode(int nodeValue, ListNode nextNode)
    {
        this._nodeValue = nodeValue;
        this._nextNode = nextNode;
    }
    public int NodeValue
    {
        get
        {
            return this._nodeValue;
        }
        set
        {
            this._nodeValue = value;
        }
    }

    public ListNode NextNode
    {
        get
        {
            return this._nextNode;
        }
        set
        {
            this._nextNode = value;
        }
    }

}

Open in new window

0
 
LVL 62

Assisted Solution

by:Fernando Soto
Fernando Soto earned 200 total points
Comment Utility
Hi robbhill;

Something like this should work. I would not use a recursive function for this because depending on how many objects you having in the list it could cause a stack overflow.

private static void GetFifthNode(ListNode curNode)
{
    ListNode n1 = null;   // Will point to the 5th node from the end
    ListNode n2 = null;   // Will point to the end node
    int nodeCount = 1;    // Make sure that there are at least 5 nodes otherwise can't get 5th node from the end

    // Make n2 to be the 5 th node from the begining
    for(int i = 1; i <= 5; i++ )
    {
        if (n2 == null)
        {
            n2 = curNode;
            continue;
        }
        if( n2.NextNode != null )
        {
            n2 = n2.NextNode;
            nodeCount++;
            continue;
        }
        break;
    }

    // Check to see if we have 5 or more nodes if not exit
    if( nodeCount < 5 )
    {
        Console.WriteLine("Not enough nodes to get 5th from the end.");
        return;
    }

    // If n2 next node is null assign curNode to n1 because at this point we have 5 nodes
    // and curNode would be 5 nodes from the end
    if (n2.NextNode == null) n1 = curNode;

    // Increment both pointer at the same time until n2.NextNode is null
    while( n2.NextNode != null )
    {
        n1 = n1 == null ? curNode : n1.NextNode;
        n2 = n2.NextNode;
    }

    Console.WriteLine("The 5th node from the end has a value of {0}", n1.NodeValue);

}

Open in new window

0
 
LVL 11

Author Comment

by:Robb Hill
Comment Utility
ok....your helping me alot here.....this node stuff is not something I have done much of except with xml a while back ...this seems different...so if I want to do some test cases...how would you go about that........in the meantime I am trying to string something up to test this...

do you have an easy way to test..when this is just in a class.  I am using vs 2013.
0
 
LVL 62

Expert Comment

by:Fernando Soto
Comment Utility
Hi;

First I want to say that Microsoft does have a class which implements a doubly linked list which is much better then implementing your own.

LinkedList<T> Class

To answer your question this function should be a part of your ListNode class. Also I would make it more genetic so that you can ask for any node that is X nodes from the end. To test create a LinkedList and then X node from the end and make sure that the results is what you are asking for.

.
0
 
LVL 11

Author Comment

by:Robb Hill
Comment Utility
I need to stay in the singly linked list.  


ok so would you just add this method into my code...as is?


...im still not sure on the test...as in ...I am looking at visual studio....I have a solution, with a project ..with this one class in it....

where would I put this test..so I can compile it and see some results.......I know how to use nunit..but this is a test case...not sure how to implement that....or rather picture in my head
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
LVL 62

Expert Comment

by:Fernando Soto
Comment Utility
To your question, "ok so would you just add this method into my code...as is?", well if you only need to find the 5th node from the end, always, then yes, otherwise make it more generic by changing everywhere it checks for 5 to check for the distance you want to find.

I have not run NUnit test a whole lot and it's been a while, so I would not be of much help there. What I would do is in the main function of the console application I would create an instance of the ListNode LinkedList with different sizes and run the code to find the node from the end of the list, currently in your code called GetFifthNode(...). By the way it may be better to have that function to return the node you are looking for then to return void.

.
0
 
LVL 11

Author Comment

by:Robb Hill
Comment Utility
Here is the code...but I still cannot run it....the encapsulation seems like it needs to be refined.....how would you wire this up to run.

Please help

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SinglyLinkedList
{
    static class Program
  {
    private static int index = 0;
    private static ListNode fifthNode = null;
    static int totalNode = 0;
    static void Main()
    {
        ListNode node7 = new ListNode(7, null);
        ListNode node6 = new ListNode(6, node7);
        ListNode node5 = new ListNode(5, node6);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode root = new ListNode(1, node2);

        GetFifthNode(root);//The result;
    }

    private static void CountTotalNode(ListNode curNode)
    {
        if (curNode.NextNode == null)
        {
            return;
        }
        else
        {
            totalNode += 1;
            CountTotalNode(curNode.NextNode);
        }
    }
    private static void GetFifthNode(ListNode curNode)
    {
        if (index == totalNode-5)
        {
            fifthNode = curNode.NextNode;
            return;
        }
        else
        {
            index += 1;
            GetFifthNode(curNode.NextNode);
        }
    }
}

public class ListNode
{
    int _nodeValue;
    ListNode _nextNode;

    public ListNode()
    {
    }
    public ListNode(int nodeValue, ListNode nextNode)
    {
        this._nodeValue = nodeValue;
        this._nextNode = nextNode;
    }
    public int NodeValue
    {
        get
        {
            return this._nodeValue;
        }
        set
        {
            this._nodeValue = value;
        }
    }

    public ListNode NextNode
    {
        get
        {
            return this._nextNode;
        }
        set
        {
            this._nextNode = value;
        }
    }

    private static void GetFifthNode(ListNode curNode)
    {
        ListNode n1 = null;   // Will point to the 5th node from the end
        ListNode n2 = null;   // Will point to the end node
        int nodeCount = 1;    // Make sure that there are at least 5 nodes otherwise can't get 5th node from the end

        // Make n2 to be the 5 th node from the begining
        for (int i = 1; i <= 5; i++)
        {
            if (n2 == null)
            {
                n2 = curNode;
                continue;
            }
            if (n2.NextNode != null)
            {
                n2 = n2.NextNode;
                nodeCount++;
                continue;
            }
            break;
        }

        // Check to see if we have 5 or more nodes if not exit
        if (nodeCount < 5)
        {
            Console.WriteLine("Not enough nodes to get 5th from the end.");
            return;
        }

        // If n2 next node is null assign curNode to n1 because at this point we have 5 nodes
        // and curNode would be 5 nodes from the end
        if (n2.NextNode == null) n1 = curNode;

        // Increment both pointer at the same time until n2.NextNode is null
        while (n2.NextNode != null)
        {
            n1 = n1 == null ? curNode : n1.NextNode;
            n2 = n2.NextNode;
        }

        Console.WriteLine("The 5th node from the end has a value of {0}", n1.NodeValue);

    }

}




















































































}

Open in new window

0
 
LVL 11

Author Comment

by:Robb Hill
Comment Utility
This code now has two get fifth node methods...i am not sure what to do with this......
0
 
LVL 11

Accepted Solution

by:
Robb Hill earned 0 total points
Comment Utility
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SinglyLinkedListExersize
{
    /*
 * Write a function that would return the 5th element from the
 * tail (or end) of a singly linked list of integers, in one pass,
 * and then provide a set of test cases against that function
 * (please do not use any list manipulation functions that you
 * do not implement yourself).
 */
    class App
    {
       
        static void Main(string[] args)
        {
            int[] arr = new int[] { 0, 1, 2, 3, 4, 5, 6 };
            int lastLocation = 0;

            while (true)
            {
                try
                {
                    Console.Out.WriteLine(arr[lastLocation]);

                    lastLocation = lastLocation + 5;
                }
                catch (Exception e)
                {
                    Console.Out.WriteLine(e.Message);
                    break;
                }
            }

            lastLocation--;

            for (int i = 0; i < 5; i++)
            {
                try
                {
                    // This sysout statement ensure that same element is not hit
                    // twice
                    Console.Out.WriteLine(arr[lastLocation]);
                    if (lastLocation < 4)
                    {
                        Console.Out.WriteLine("Array Length less than 5");
                        break;
                    }

                    //       System.out.println("Last element of array: "
                    //       + arr[lastLocation]);
                    Console.Out.WriteLine("5th Last element of array: "
                    + arr[lastLocation - 4]);
                    break;
                }
                catch (Exception e)
                {
                    Console.Out.WriteLine(lastLocation--);
                }
            }
        }
    }
}
0
 
LVL 62

Expert Comment

by:Fernando Soto
Comment Utility
Hi robbhill;

From you last post I can see that this seems to be a class assignment. It seems that the solution I posted was not worth full credit.

By the way when I stated that you should place the function GetFifthNode(...) in the ListNode class I did not mean to keep the other version in the code. Also when you moved it to the ListNode class you need to remove the static keyword from the functions signature.

One more thing your main function never seems to create an instance of the LinkedList and never finds the 5th node from the end.

.
0
 
LVL 11

Author Closing Comment

by:Robb Hill
Comment Utility
Thanks for the assistance Fernando..I gave you credit for helping..I posted the entire solution.
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Recently while returning home from work my wife (another .NET developer) was murmuring something. On further poking she said that she has been assigned a task where she has to serialize and deserialize objects and she is afraid of serialization. Wha…
This article describes relatively difficult and non-obvious issues that are likely to arise when creating COM class in Visual Studio and deploying it by professional MSI-authoring tools. It is assumed that the reader is already familiar with the cla…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
This video discusses moving either the default database or any database to a new volume.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now