473,701 Members | 2,385 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Linked List

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.

And please dont think this is my homework.
Can anybody simple tell me how this can be done. I am preparing for an
interview and wanted to know how to go about implementing this.
Or atleast tell me where I can find few examples on traversing Lists.
Even if I can get any good resources which explains lists properly my
job will be done.
Jul 22 '05 #1
32 5728
"source" <su*********@ho tmail.com> wrote in message
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.


Show us your best effort so far. Also try to write a function that finds
the 5th element in a container matching a certain condition (for example,
the element is >10).

Jul 22 '05 #2
"source" <su*********@ho tmail.com> wrote in message
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.


Show us your best effort so far. Also try to write a function that finds
the 5th element in a container matching a certain condition (for example,
the element is >10).

Jul 22 '05 #3
source writes:
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.

And please dont think this is my homework.
Can anybody simple tell me how this can be done. I am preparing for an
interview and wanted to know how to go about implementing this.
Or atleast tell me where I can find few examples on traversing Lists.
Even if I can get any good resources which explains lists properly my
job will be done.


If I understand the question, it can't be done; at least on a bare bones
linked list. You will have to count the elements so you can subtract five
from that. And then traverse the list again, which would be easiest from
the head end. I call that two passes, not one that you asked for. My
default meaning for end is the far end; I call the other end the beginning.

For test cases, test for within range, each valid boundary and one beyond
each valid boundary. Valid because numbering might start with zero or one.
Jul 22 '05 #4
source writes:
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.

And please dont think this is my homework.
Can anybody simple tell me how this can be done. I am preparing for an
interview and wanted to know how to go about implementing this.
Or atleast tell me where I can find few examples on traversing Lists.
Even if I can get any good resources which explains lists properly my
job will be done.


If I understand the question, it can't be done; at least on a bare bones
linked list. You will have to count the elements so you can subtract five
from that. And then traverse the list again, which would be easiest from
the head end. I call that two passes, not one that you asked for. My
default meaning for end is the far end; I call the other end the beginning.

For test cases, test for within range, each valid boundary and one beyond
each valid boundary. Valid because numbering might start with zero or one.
Jul 22 '05 #5
"osmium" <r1********@com cast.net> wrote in message news:c4pnvn$2kb bqu$1@ID-
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.
If I understand the question, it can't be done; at least on a bare bones
linked list. You will have to count the elements so you can subtract five
from that. And then traverse the list again, which would be easiest from
the head end. I call that two passes, not one that you asked for. My
default meaning for end is the far end; I call the other end the beginning.

You can do it in one pass. The first way to implement it could actually be
slower than the 2 pass method, and the second way would probably be faster.

For test cases, test for within range, each valid boundary and one beyond
each valid boundary. Valid because numbering might start with zero or

one.

I'd say the empty list, list of 1 element, list of 5 elements, list of >5
elements.
Jul 22 '05 #6
"osmium" <r1********@com cast.net> wrote in message news:c4pnvn$2kb bqu$1@ID-
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.
If I understand the question, it can't be done; at least on a bare bones
linked list. You will have to count the elements so you can subtract five
from that. And then traverse the list again, which would be easiest from
the head end. I call that two passes, not one that you asked for. My
default meaning for end is the far end; I call the other end the beginning.

You can do it in one pass. The first way to implement it could actually be
slower than the 2 pass method, and the second way would probably be faster.

For test cases, test for within range, each valid boundary and one beyond
each valid boundary. Valid because numbering might start with zero or

one.

I'd say the empty list, list of 1 element, list of 5 elements, list of >5
elements.
Jul 22 '05 #7
On 4 Apr 2004 12:05:51 -0700 in comp.lang.c++, su*********@hot mail.com
(source) wrote,
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.


This sentence no verb.

What I consider the usual approach to that kind of thing is what I call
a "following pointer". That is, you have two iterators, one points to
where you are looking in the list and the other five items behind it.
You advance both of them at the same time. When you get to what you
were looking for (in this case, the end) the "following" iterator points
to what you wanted.

No doubt you can write the C++ code based on that.

Jul 22 '05 #8
On 4 Apr 2004 12:05:51 -0700 in comp.lang.c++, su*********@hot mail.com
(source) wrote,
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.


This sentence no verb.

What I consider the usual approach to that kind of thing is what I call
a "following pointer". That is, you have two iterators, one points to
where you are looking in the list and the other five items behind it.
You advance both of them at the same time. When you get to what you
were looking for (in this case, the end) the "following" iterator points
to what you wanted.

No doubt you can write the C++ code based on that.

Jul 22 '05 #9
source wrote:
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.

And please dont think this is my homework.
Can anybody simple tell me how this can be done. I am preparing for an
interview and wanted to know how to go about implementing this.
Or atleast tell me where I can find few examples on traversing Lists.
Even if I can get any good resources which explains lists properly my
job will be done.


P-code, and without error checking (assumes list is at least 5 long):

node* node = yourfirstnode;
node* node5 = node->next->next->next->next;

for(;;)
{
if(node5->next == 0)
{
return node->val;
}
node = node->next;
node5 = node5->next;
}

- Pete
Jul 22 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
3095
by: C++fan | last post by:
Suppose that I define the following class: class example_class{ public: example_class(); void funtion_1(); void function_2(); protected:
5
859
by: Dream Catcher | last post by:
1. I don't know once the node is located, how to return that node. Should I return pointer to that node or should I return the struct of that node. 2. Also how to do the fn call in main for that LOCATE subroutine that returns a node???? Any help would be appreciated. Thanks
10
15126
by: Kent | last post by:
Hi! I want to store data (of enemys in a game) as a linked list, each node will look something like the following: struct node { double x,y; // x and y position coordinates struct enemy *enemydata; // Holds information about an enemy (in a game) // Its a double linked list node
6
4601
by: Steve Lambert | last post by:
Hi, I've knocked up a number of small routines to create and manipulate a linked list of any structure. If anyone could take a look at this code and give me their opinion and details of any potential pitfalls I'd be extremely grateful. Cheers Steve
12
15094
by: Eugen J. Sobchenko | last post by:
Hi! I'm writing function which swaps two arbitrary elements of double-linked list. References to the next element of list must be unique or NULL (even during swap procedure), the same condition should be kept for references to previous element of list. Here is my solution below: struct node {
12
3947
by: joshd | last post by:
Hello, Im sorry if this question has been asked before, but I did search before posting and couldnt find an answer to my problem. I have two classes each with corresponding linked lists, list1 and list2, each node within list1 has various data and needs to have a pointer to the corresponding node in list2, but I cant figure out how to do this. Could someone explain what I might be missing, or maybe point me in the direction of a good...
51
8626
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort for linked lists, I couldn't find one. I read something about Mcilroy's "Optimistic Merge Sort" and studied some implementation, but they were for arrays. Does anybody know if Mcilroys optimization is applicable to truly linked lists at all?
1
15546
by: theeverdead | last post by:
Ok I have a file in it is a record of a persons first and last name. Format is like: Trevor Johnson Kevin Smith Allan Harris I need to read that file into program and then turn it into a linked list. So on the list I can go Trevor, Kevin, Allan in a straight row but I can also call out there last name when I am on their first name in the list. Sorry if it doesn't make sense trying to explain best I can. So far I have // list.cpp
0
8626
by: Atos | last post by:
SINGLE-LINKED LIST Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be anything from a short integer value to a complex struct type, also has a pointer to the next node in the single-linked list. That pointer will be NULL if the end of the single-linked list is encountered. The single-linked list travels only one...
7
5769
by: QiongZ | last post by:
Hi, I just recently started studying C++ and basically copied an example in the textbook into VS2008, but it doesn't compile. I tried to modify the code by eliminating all the templates then it compiled no problem. But I can't find the what the problem is with templates? Please help. The main is in test-linked-list.cpp. There are two template classes. One is List1, the other one is ListNode. The codes are below: // test-linked-list.cpp :...
0
8733
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8649
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9083
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8975
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8934
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
6569
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4410
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4662
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
3
2035
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.