Data structure for java

Sup /prog/, I need to an indexed data structure that supports these methods:


void addLast(S stuff);     // insertion's like a queue
void removeLast();         // removes last link
void removeIfHas(S stuff); // removes link if has target stuff
S getStuff(int index);     // retrieves stuff given the index

I can do this with a (Doubly/Double) Linked List, but the search/retrieval is O(n). Is a HashTable a better structure?

Thanks

A hash table won't store any of the values in order, so you won't be able to remove the last link, just do it with a normal linked list and call the front the end.

>>2
A hashtable tends to contain one or two arrays of keys and values at least (internally). It's possible to make a hashtable that remembers the order the elements were inserted, but that doesn't mean I think a hashtable is a good choice for what OP needs.

>>1
A hashtable doesn't meet your requirements (no intrinsic integer indexing, and even if you use a TreeMap or something you still can't addLast, removeLast).

Probably what is best is just a simple ArrayList. O(1) addLast, removeLast and getStuff, O(n) removeIfHas.

If O(n) removeIfHas is unacceptable (my guess is you will be fine), you can write a custom data structure that uses a map to index into a linked list which will give you O(1) amortized for all operations- this seems beyond you so I advise the first approach.

>>4
I don't see how such mapping possible, because after removeIfHas(S stuff) all indices) after S needs to be recalculated.

>>5
It would be possible, just really slow.

>>5
It's possible. There's a link on this I wish I could find just now, maybe >>4 has it (if so, please post.)

>>5
What indicies? removeIfHas simply searches in the hashtable for "stuff" - O(1) amortized, and deletes it from the linked list (the hashtable points to the node so this is O(1) also), then deletes the corresponding entry from the hashtable which is again O(1) amortized.

>>8
and now explain how after all these operations
we get
>S getStuff(int index);     // retrieves stuff given the index
which is
a) O(1)
b) correct

>>9
You are correct- I didn't see that addLast worked like a queue, otherwise we can just swap with the last item in the list. I'll think on it but I suspect we can at best achieve O(log n) for one of getStuff(int index) and removeIfHas, and O(1) for the other.
That being said this problem seems very arbitrary and I suspect OP has made a design mistake to get to the point where this set of operations is required in the first place.

>>10

OP here, and I don't know. This is for an algorithms class. The teacher asked for a generic playlist-kind of structure that did what I typed. I assumed that using LinkedList would be a trap, since they are always bitching about O(n).

>>11
Write specifically what the teacher asked for. I suspect you are reading it wrong.

>>12

Ok, translated:

Nowadays lists come with a cool select mechanism.
Given a list, would you like to get a (sub)list with your favorite stuff? Yeah!

- construction of an empty list, with selection (also empty)
- void addLast(S musicorwhatever)
- void removeLast(S musicorwhatever)
- int numOfElements()
- S getStuff(int index)
- void markElementToSelectList(int index)
- SelectList getSelections()
- void clearSelection()

Repeated elements are welcomed in our lists.
If you remove an element on the list, the references to it in the selection are also removed (here enters the void removeIfHas(S stuff)).

So basicly this is a class with two lists. One that will store the available stuff and another that will point to specif elements of the other.

Example:

OPClass test = new OPClass();
test.addLast("Jew");
test.addLast("Had");
test.addLast("Sex");
-> List = [Jew,Had,Sex] | Selection = nothing
test.remove();
-> List = [Jew,Had] | Selection = nothing
test.markElementToSelectList(1);
test.markElementToSelectList(1);
-> List = [Jew,Had] | Selection = [Had,Had]
OPClass newtest = test.getSelections()
test.remove();
test -> List = [Jew] | Selection = nothing
newtest -> List = [Had,Had] | Selection = nothing

- construction of an empty list, with selection (also empty)
NIL
- void addLast(S musicorwhatever)

(append list (list element))
(nconc list (list element))
revappend, list*, cons+nreverse and a bunch others
(O(n))
Or do what's smarter with Linked Lists (O(1)) and append on top:
(cons element list)
- void removeLast(S musicorwhatever)
Remove first - (cdr list)
Remove last - (butlast list)

- int numOfElements()
(length list)
- S getStuff(int index)
(nth index list)
(car (nthcdr index list))
(elt list index) ; this works with any sequence type
(and many others, O(n), where n is the index)
- void markElementToSelectList(int index)

- SelectList getSelections()

- void clearSelection()


Don't know what these are, but maybe what you want here is a tconc list. It's a tconc (tail concatenate) linked list is a structure made of 2 pointers, one is the linked list, and the other is a pointer to the end of the linked list(last element).

The advantage to having a tail pointer is that you can add the last (and first of course) elements at O(1) instead O(n), however this has the disadvantage that it's a distructive structure. Maybe this is what you wanted? I've written a variety of tconc versions myself, but here's one that comes up on google: http://paste.lisp.org/display/85884

If you really want to remove the first and last elements at O(1), use a tconc, if you only want to remove/add the first element at O(1), use a normal linked list. If you have other needs such as constant time lookup, O(logn) searching and so on, other data structures fit the bill. You'll have to think of what you need before exactly before you make a decision.

import java.util.*;
public class OPClass<T> {
    private List<T> list;
    private List<Integer> selection;
   
    public OPClass() {
        list = new ArrayList<T>();
        selection = new ArrayList<Integer>();
    }
    public OPClass(Collection<T> source) {
        list = new ArrayList<T>();
        selection = new ArrayList<Integer>();
        for(T item : source) list.add(item);
    }
    public void addLast(T item) {
        list.add(item);
    }
    public void removeLast() throws IllegalStateException {
        if(list.isEmpty()) throw new IllegalStateException("Cannot remove element from empty list.");
        list.remove(list.size() - 1);
        Iterator<Integer> iter = selection.iterator();
        while(iter.hasNext()) if(iter.next() == list.size()) iter.remove();
    }
    public int numOfElements() {
        return list.size();
    }
    public T getStuff(int index) throws IndexOutOfBoundsException {
        return list.get(index);
    }
    public void markElementToSelect(int index) throws IndexOutOfBoundsException {
        selection.add(index);
    }
    public List<T> getSelections() {
        List<T> clone = new ArrayList<T>();
        for(Integer i : selection) clone.add(list.get(i));
        return clone;
    }
    public void clearSelection() {
        selection.clear();
    }
    public void removeIfHas(T item) {
        //Semantics ambiguous, this implementation only removes the first occurence
        int index = list.indexOf(item);
        if(index == -1) return;
        list.remove(index);
        Iterator<Integer> iter = selection.iterator();
        while(iter.hasNext()) if(iter.next() == index) iter.remove();
        for(int i = 0; i < selection.size(); i++) if(selection.get(i) > index) selection.set(i, selection.get(i) - 1);
    }
}


import java.util.*;

public class OPClass<T> {
    public static void main(String argv[]) {
        Set<Integer> opSet = new LinkedHashSet<Integer>();
        // add last
        Integer iamlast = 1;
        opSet.add(iamlast);
        // remove last
        opSet.remove(iamlast);
        System.out.println("Niggers");
    }
}

LinkedHashSet, tbh

>>17
Did you really need to revive this thread to post the wrong solution?

>>18

Yes. I am drunk, so I can do anything I want, bitch.

>>19
DRINK MY ANUS

>>16
^* African Americans

Why is a custom ArrayList better than a custom LinkedList?

LinkedList MY ANUS

27 Name: Anonymous 2011-02-03 1:19

Don't change these.

Name:		Email:
Entire Thread Thread List

All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -