Data Structures -- Linked List - Find the nth last element in linked list.

varalu

Oct 26 2007, 10:01 AM

Given a linked list, find the 5th last element with Time complexity O(n) and minimal space complexity.

Note: If you know the answer and if you feel it is simple also please post the answers so that others will come to know about the answers.

What is a linked list?? /* this is for your further reference and reading */

QUOTE

In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order. A linked list is a self-referential datatype because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked list exist: singly-linked lists, doubly-linked lists, and circularly-linked lists.

There are various kinds of linked lists available and can be implemented in many languages and in different ways.

Applications of Linked Lists

QUOTE

Linked lists are used as a building block for many other data structures, such as stacks, queues and their variations.

The "data" field of a node can be another linked list. By this device, one can construct many linked data structures with lists; this practice originated in the Lisp programming language, where linked lists are a primary (though by no means the only) data structure, and is now a common feature of the functional programming style.

Sometimes, linked lists are used to implement associative arrays, and are in this context called association lists. There is very little good to be said about this use of linked lists; they are easily outperformed by other data structures such as self-balancing binary search trees even on small data sets (see the discussion in associative array). However, sometimes a linked list is dynamically created out of a subset of nodes in such a tree, and used to more efficiently traverse that set.

even bad solutions are welcome...

pointybirds

Oct 26 2007, 12:45 PM

Hmm, presuming a singly linked list where you can't start at the end and work your way back, you could use a circular buffer with 5 elements (e.g. an array that can store the contents of the LL nodes) and traverse the list until you reach the end ... then, the "next" element in your circular buffer is the fifth last.

E.g.:

for (i=0; (e = next element) != null; i++%5) {
buf[i] = e
}
fifth_last = buf[i]

Something like that I guess. You'd also need to initialise your array to null and check for this at the end in case your LL < 5 elements.

varalu

Oct 26 2007, 01:34 PM

yours is a nice solution... Better in usage of memory also. This circular buffer thing is very good.
What is i am giving you a constraint of
1. "NO EXTRA MEMORY"
2. No additional Data structures.

Give a solution with the above constraints.

Small Hint:
Do not make it complex...think very simple. --> for a simple solution.

sanjay0828

Oct 26 2007, 07:00 PM

Ok.. here is a very simple solution

Have two pointers.

Initially, let both the pointers point to the first node of the linked list

Now move one of the pointers to the 5th node of the linked list.
This can be done in O(1) complexity i.e. constant time.

Example:-
1-->2-->3-->4-->5-->6-->7-->8-->9-->10->11-->12

Here, one pointer points to 5 while the other pointer points to 1

Now keep moving each pointer i.e. current node to next node, until the first pointer reaches the end of the linked list i.e. 12
The second pointer will now be pointing to the 5th last element i.e. 8

jlhaslip

Oct 26 2007, 07:29 PM

$item= $array[count($array)-5];

untested

may need to perform this in steps though

$num = count($array);
$n = $num - 5;
$item = $array[ $n ];

varalu

Oct 27 2007, 09:09 AM

@sanjay0828
Good one... the expected solution.

Again... i want a simpler solution. What will be the basic answer that comes to your mind if i give this problem.??
Very basic..

..

If no answer i will be posting it in my next post.

iGuest

Nov 4 2007, 01:06 AM

Use two variable (sum4 and sum5) to store the sum of last 4 nodes and last 5 nodes respectively. At the end of the loop, the 5th node data = sum5 - sum4.

-Grant

totrap

Nov 23 2007, 06:08 AM

while(ptr->next->next->next->next->next!=NULL)
ptr=ptr->next;

//after loop, ptr points to the fifth last element in the list;

songs2enjoy

Aug 31 2008, 10:01 AM

reverse the list and find the 5th element from the start,

Not simple though just an idea.

Varalu,

Can u plz post what's the simple idea ?

Thanks

ADD REPLY / Got an Opinion!	a humble request :-)	RAPID SEARCH!	Free Hosting	[X]
Express your Opinions, Thoughts or Contribute more info. to help others. Ask your Doubts & Queries to get answers, So that "Together We can help others!"	Register FREE for AD-FREE forum, Create your own topics, Ask Questions, track topics, setup subscriptions & notifications and Get a Free Website w/ Email and FTP.		500MB Space No Ads, CPanel, FTP, PHP, MySQL, EMails - 100% FREE