Hi everyone,
        I have few Data structure questions.

1) Given an singly linked list and poisition "n", we have to remove the nth item from end.
2) Remove the duplicates in an array.

The algorithm should be efficient and we can use any data structure for achieving this.

Regards
Pradeep P

It is not how much we do,
but how much love we put in the doing.

-Mother Theresa

__________________
It is not how much we do,
but how much love we put in the doing.

-Mother Theresa

Well, Pradeep, since this is a programming forum, you start with a program. When you say "given an singly linked list", what do you mean by "given"? Show us the program, or at least a part of the program that allows us to deduce the data structure that you have in mind, and maybe someone can help.


How can we possibly comment on how to remove an item from a data structure without knowing some details?

Your question implies that you start with a data structure containing some "things". What are the "things". How did the "things" get into the data structure.


Dave

Well, "singly-linked list" in and of itself defines a well-known data structure who's properties and behaviors should be understood by most (if not all) developers.

The key here is to define an efficient *algorithm* that can be applied to the problem, regardless of the implementation language. That is, you should be able to define a list of steps that can be expressed in C, C++, Java, PHP, Python, whatever.

When dealing with container algorithms, the "things" the container holds should bear little or no effect on the algorithms used to manipulate the containers. After all, could you imagine the headache it would cause if someone couldn't write a generic container structure (such as a linked list, binary tree, etc..)? That is, if every time someone needed a container structure, they had to rewrite it from scratch specific to the object being contained?

C++ templates provide an excellent example for writing generic containers. Java states that all types are derived from Object, so a generic container would simply hold Objects.



My problem in answering this question is that it sounds wayyyy too much like a homework assignment, and it's against my morals to answer someone's homework questions. Also, most schools have "academic integrity" agreements which are essentially contracts between a student and the school that limits where a student can get help or answers to their programming assignments.


That said, let's take a look at your problems:

The first problem is challenging because a singly-linked list only allows you to traverse the list from Front to Back. So, while traversing the node, you don't have any idea how far from the end of the list you are -- you only know how far from the beginning you are.

It might make sense, then, to store pointers or references to each node in the linked list in some numerically-indexed container, such as a vector or array. One woudl traverse the entire list, storing the pointer or reference in the numerically indexed parallel structure. When the entier list is traversed, you know how many items are in it. And, since you have a numerically-indexed container, you can very efficiently access any element in the list by accessing the pointer/reference in the numerically-indexed container.


The second problem is challenging because you'll need to keep track of the items you've already seen in the list as you traverse it. As you traverse the list, if the item being stored exists in this secondary container, you know you've seen it before and can safely delete the current list node. If the item does NOT exist in the lookup structure, you know you have NOT seen it before, so you add it to the secondary structure.

The key here is to pick a data structure that makes lookups of "things" very efficient. A hash table or dictionary comes to mind, where the key is the "thing" you're storing.


I can't in good conscience give you more details than this... you should have enough information now to implement the above, or if not, at least be able to look through your data structures book or talk to your teacher about these ideas.


Take care,

Nik
http://www.bigaction.org/

My impression was that the assignment was to implement an algorithm in C. My questions were "what algorithm do you have in mind"; "what C-program advice do you request"; stuff like that.

If this is a DataBase homework problem, you should use your DataBase exposure to select an algorithm. If you don't have enough programming experience to know how to implement it, maybe we can help you if you ask questions.

Dave

Linked list solution:

Traverse from the front of the list to end looking for the item with the index "n". When you find that item, save a reference to that "n"th indexed item, and set "n-1" indexed item to point to "n+1" indexed item.
   The primary data structure you use to implement this is irrelevant. Singly linked lists are poor performers by nature since their complexity is O(n) meaning to find the nth item you have to traverse through n nodes.

Make sense? else email: [email protected]

hi .. I m writing for the first time..
here r some solutions ;;
  1> singly list -- finding last but nth element..
        a. maintain 2 pointers initialised at root.
        b. forward first to nth element
        c. now forward both till first reaches end..
        d. now second is poinint at last but nth element
        e. remove it.

  2. array duplicaion removal
 a. sort the array using standard method..complexity O(n log n)
 b. remove same consecutives.. complexity O(n)
 c. overall complexity .. o(n log n)



se-E u again

Given an singly linked list and poisition "n", we have to remove the nth item from end
Answer: In either of implementation, the complexity will be O(n).
Steps of the first questions are as:
1) Take a temporary pointer.
2) When you cross the (n)th element, store the address of the nth position in the temporary pointer or reference such that traversal pointer must be having (n+1)th address.3) Now after above step, always update the value of the temp by the new address or next address in the singly linked list.
4) After reaching at the end, temp pointer will be in the (n+1)th position from the end.
5) Now just replace the value from the (n-1)(from the end) address to get the new linked list.
-----------------------------------------------------------------
I hope I answered your question well in a very economical way.
Second answer will be O(nlogn) because of one standard sort.
2. Second step will be mere replacing the duplicate entries and that will be of order n hardly.

Most of the solutions presented by above fellows missed a curical point in the initial statement. i am repeating.

   "nth element from end"
 now if you look the solutions , most people prefered to traverse from head of the link list to nth element but how do you know the size of link list and how can you be sure that it is nth element which is to be deleted unless you travel from end. So therefore, these above solutions will generate a bug in the solutions.

  Similarly the answer to this problem can be tricky depending upon the way link list been implemented. But if we consider the implementation standards by Java or STL then it can be implemented by O(1). Here is how
  1.Make a member of Class which keep track the no of nodes .
  2. Calculate the Target node by
         Target Node = Size - N
  3. Remove the Node N (Order of O(1) )

   For reference please have a look at Introduction to Algorithms (Corman,MIT Press).

Hi,

Answer to linked list question.

1) have two pointers, lets say we want to delete 5th node from last (of course assuming that the list has so many nodes)

 move the first one by 5 and keep second at head.
 Now start moving both of them by 1
 When your second reaches end, your first one is pointing 5th node from last. Delete it !!! :-)

2)If your array is such that it has 2n+1 elements where n elements are duplicated, just do a xor of all the elements like
  for(i=0;i<2n+1;i++)
      result^=arr[i];
  at the end of the loop you will have the non-duplicate number in the result. Now compare each element and remove it.

If you have multiple non-duplicates, you need to sort and then compare adjacent elements to remove.

I even cann't write a simpla linked list. This problem is too advanced for me.

Thanks.

Linux is the best OS in the world.