16 replies to this topic

[iGuest]

running sample program using stack implementing link list
Data Structures -- Linked List

Hi to all!...Gud day!...
I'm new to this site, but I find it
Interesting to find out the
Opinion of others, specially regarding
Programming...

I really needed someone to
Help me with this,...
I've got to have a sample
Running program of "STACK IMPLEMENTING LINK LIST",
Even just a simple one!
I'm badly in need of that!!...
Pls...

Hope I can find solutions
To my probs through this site!!...

I'll be waiting for some reply through here
Or you can email me @ leane_crazycute18 at yahoo.Com
Thank you and God bless!

-question by leane

[vivek.m]

varalu, on Oct 27 2007, 09:09 AM, said:

@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.

the most basic and the only answer that came to my mind (actually, my frnd's mind. I am too laazy to use mine)  is to find length and then to find the (l-n)th element with o(n2) complexity.


i am interested in your answer.. it's more than a month since you posted your question. 

[varalu]

vivek.m, on Nov 24 2008, 08:27 PM, said:

the most basic and the only answer that came to my mind (actually, my frnd's mind. I am too laazy to use mine)  is to find length and then to find the (l-n)th element with o(n2) complexity.
i am interested in your answer.. it's more than a month since you posted your question. 

Ok.. here is my answer...

This is similar to finding the middle element in the link list with slight variation..

1. Have two pointer initially ( first and second )
2. move the second pointer alone 5 nodes.
3. Now move both the pointers one node at a time until the second reaches the end.
when the second reaches the end , the first node will be the 5th last element..

node * first ,*second;

first = second = root;

// moves the second ptr 5 nodes..
int i =0;
while ( (i < 5) && (second != NULL) )
{
	second = second-> next;
	i++;
}

while( second->next != NULL )
{
	   first = first->next;
	   second = second->next;
}

return (first) ; // first ptr is the 5th node from the last..

The above solution is same as the one Sanjay gave. This algorithm can be even generalized to find the kth node from the last similarly....

But the answer that i expected is below..

Just scan the list twice.
You can get the kth element from the last.

This algorithm is known as hare and tortoise algorithm.

[vivek.m]

Quote

But the answer that i expected is below..
Just scan the list twice.
You can get the kth element from the last.

This algorithm is known as hare and tortoise algorithm.

That's same as what I said... In first scan, find the length and in second scan, find the required element. This seems to be only tortoise-tortoise scan.
The other answer (your and sanjay's answer) is more efficient with worst case operations half of what is required in first answer. complexity will be o(n) in both cases. (my bad. i had to edit. i mentioned complexity o(n^2) incorrectly.)

Thanks for the problem.

Edited by vivek.m, 25 November 2008 - 02:13 PM.

[iGuest]

main class problem..Data Structures -- Linked List

hello..It's my first time here to visit..I want to ask for help in making a main class of my linked list in queue..Here's what is asking for:

  If the input satisfies partial ordering, then the algorithm will terminate when theQueue is empty– If a loop exists, it will also terminate but will not output the elements in theLoop. Instead, it will just inform the user that a loop is present:

 

here's the code:

interface Queue{   /* Insert an item */   void enqueue(Object item) throws QueueException;   /* Delete an item */   Object dequeue() throws QueueException;}Class QueueException extends RuntimeException{   public QueueException(String err){     super(err);   }}

 

another file:

class LinkedQueue implements Queue{   Node front, rear;   /* Create an empty queue */   LinkedQueue(){   }   /* Create a queue with node and initially */   LinkedQueue(Node and){     front = and;     rear = and;   }   /* Inserts an item onto the queue */   public void enqueue(Object item){     Node and = new Node(item, null);     if (front == null) {       front = and;       rear = and;     }     else{       rear.Link = and;       rear = and;     }   }   /* Deletes an item from the queue */   public Object dequeue() throws QueueException{     Object x;     if (front == null) throw new QueueException             ("Retrieving from an empty queue.");       x = front.Info;     front = front.Link;     return x;   }   /* Main method to test the queue */   public static void main(String args[]){     LinkedQueue q = new LinkedQueue();     for (int I=11; I>0; I--){       q.Enqueue(new Integer(I));       System.Out.Println(I +" inserted");     }     for (int I=12; I>0; I--)       System.Out.Println(q.Dequeue() + " retrieved");   }}

thank you...God Bless 

-reply by cathelyn

[iGuest]

import java.Util.LinkedList;public class LinkedListDelete {  public static void main(String args[]) {   LinkedList<String> ll = new LinkedList<String>();   ll.Add("B");   ll.Add("C");   ll.Add("D");   ll.Add("E");   ll.Add("F");   ll.AddLast("Z");   ll.AddFirst("A");   ll.Add(1, "A2");   System.Out.Println("Original contents of ll: " + ll);   ll.Remove("F");   ll.Remove(2);   System.Out.Println("Contents of ll after deletion: " + ll);   ll.RemoveFirst();   ll.RemoveLast();   System.Out.Println("ll after deleting first and last: " + ll);   String val = ll.Get(2);   ll.Set(2, val + " Changed");   System.Out.Println("ll after change: " + ll);  }}