2 big Problems with LinkedList

[Sanny]

I have a LinkedList of Object.

I find it very inefficient to add or retrive object from Linked List.

I have a Object Car as below and Linked list carlist


--------------------->>>>>> Class Car Start
class car extends Object{
private int points;
private String carname;
public car(int points111,int carname111){
points=points111;
carname=carname111;
}

public int getpoints(){
return(points);
}

public String getname(){
return(carname);
}

public void setname(int carname111){
carname=carname111;
}

public void setpoint(int carpoint111){
points=carpoint111;
}
}

--------------------->>>>>> Class Car End

Now I have Linked list carlist

LinkedList carlist = new LinkedList();

To add a Car with name "Ferrari", and points 900 to linkerd list what
I do is.

car dummycar = new car("Ferrari", 900) ;
carlist.add(dummycar);

Now I have Two Problems.

First Problem
-------------------


Each time I have to create a new object dummycar in for loop to add to
CarList.

for (int i=1; i<100000;i++){
String carname1=getname(i);
int carpoint1=getpoint(i);

car dummycar = new car(carname1,carpoint1) ;// Takes lot of time to
create this Object ????

carlist.add(dummycar);
}

If I Create dummycar as a Global Variable and use below code

for (int i=1; i<100000;i++){
String carname1=getname(i);
int carpoint1=getpoint(i);

dummycar.setname(carname1);//DummyCar as Global Variable
dummycar.setpoints(carpoint1);
carlist.add(dummycar);
}

Will the above code work without any Problem???

Second Problem
----------------------

Simmilarly Say I have to change Order of Class based on points. Say to
move 1st element to 555th place


Car dummycar=(car)carlist.get(1);
carlist.add(555,dummycar);// move to 555th place.
carlist.remove(1); // removes 1st object.

Here again I have to initialize a dummycar and then add it to 555th
place. It there any way I can directly say to linked list to swap
values from 1st place to 555th place without creating dummycar
variable?

And incase I have to Change the Value of some value in the Linked List
I have to again create a Dummycar

Car dummycar=(car)carlist.get(999);

String name1=dummycar.getname()

Is there a way to not create a seperate Object and use carlist
directly.

Like below

String name1=((car)carlist.get(999)).getname();

Will the above code work???

How can I make swaping Objects in Linked List much faster instead of
creating Dummy Variables and copying values to them, Is there a way to
do that directly?


Bye
Sanny

 

[Alexander.V.Kasatkin]

Hi Sanny,

All collections in Java Collections library have specific range of
application.

Also each collection has fast and slow operations depending on its
internal implementation.

For LinkedList the fastest operations are:
addFirst(), addLast(), removeFirst(), removeLast() and iterate through
the whole list.

So it is not the best choice to get and set elements from/to random
position.

If a car points are unique, try to use TreeMap (key: car points,
value: car).
If not, try to use sorted ArrayList.

BTW, the collections in java only store references to objects. So it
was a bad idea to use one dummy car object.

BR, Alex

 

[Jeff Higgins]

I have a LinkedList of Object.

But the rest of your post goes on to describe a problem
with a LinkedList of Car supposedly.

I find it very inefficient to add or retrive object from Linked List.

You may be trying to misuse your LinkedList as a random access List.

I have a Object Car as below and Linked list carlist

You have defined a Car class.

--------------------->>>>>> Class Car Start
class car extends Object{
private int points;
private String carname;
public car(int points111,int carname111){
points=points111;
carname=carname111;
}

public int getpoints(){
return(points);
}

public String getname(){
return(carname);
}

public void setname(int carname111){
carname=carname111;
}

public void setpoint(int carpoint111){
points=carpoint111;
}
}

--------------------->>>>>> Class Car End

Now I have Linked list carlist

LinkedList carlist = new LinkedList();

To add a Car with name "Ferrari", and points 900 to linkerd list what
I do is.

car dummycar = new car("Ferrari", 900) ;
carlist.add(dummycar);

Or simply carlist.add(new car("Ferrari", 900) );
if you don't at the moment need a reference to the new car/

From the Javadoc for java.util.LinkedList
the .add(E e) method (Appends the specified element to the end of this
list.)

Now I have Two Problems.

First Problem
-------------------


Each time I have to create a new object dummycar in for loop to add to
CarList.

for (int i=1; i<100000;i++){

String carname1=getname(i);
int carpoint1=getpoint(i);
create this Object ????

carlist.add(dummycar);

Why not just: carlist.add(new Car(getname(i), getpoint(i)));

}

If I Create dummycar as a Global Variable and use below code

for (int i=1; i<100000;i++){
String carname1=getname(i);
int carpoint1=getpoint(i);

dummycar.setname(carname1);//DummyCar as Global Variable
dummycar.setpoints(carpoint1);
carlist.add(dummycar);
}

Will the above code work without any Problem???

Have you tried?
You may find that you have a list containing
a hundred thousand references to the same car.

Second Problem

Huh?

Say to move 1st element to 555th place

carlist.set(555, carlist.pop());
(throws IndexOutOfBoundsException if you don't have a 555 place.)

Car dummycar=(car)carlist.get(1);
carlist.add(555,dummycar);// move to 555th place.
carlist.remove(1); // removes 1st object.

Here again I have to initialize a dummycar and then add it to 555th
place.

Why?

It there any way I can directly say to linked list to swap

values from 1st place to 555th place without creating dummycar
variable?

There is no swap() method.
Have you read the documentation?

And incase I have to Change the Value of some value in the Linked List
Huh?

I have to again create a Dummycar

Car dummycar=(car)carlist.get(999);

String name1=dummycar.getname()

Is there a way to not create a seperate Object and use carlist
directly.

Like below

String name1=((car)carlist.get(999)).getname();

Will the above code work???

Have you tried?

How can I make swaping Objects in Linked List much faster instead of
creating Dummy Variables and copying values to them, Is there a way to
do that directly?

remove(). remove(int index), remove(Object 0), and set(int index, E element)
may help.

Reading the documentation will help.
Also considering why you want to use a LinkedList
in the first place will eliminate a lot of confusion.
If you want to do a lot of swapping around of
members by index maybe an ArrayList would be
a better choice.

 

[Sanny]

Hi Sanny,

All collections in Java Collections library have specific range of
application.

Also each collection has fast and slow operations depending on its
internal implementation.

For LinkedList the fastest operations are:
addFirst(), addLast(), removeFirst(), removeLast() and iterate through
the whole list.
Ok

So it is not the best choice to get and set elements from/to random
position.

If a car points are unique, try to use TreeMap (key: car points,
value: car).
If not, try to use sorted ArrayList.

What is Treemap What are the functions to access elements in treeMap?
Can I uses it just like LinkedList by replacing LinkedList with
TreeMap?

What about the Car Object? How will the Car Object be converted to
TreeMap. Is it more efficient to add/Remove values from TreeMap?

BTW, the collections in java only store references to objects. So it
was a bad idea to use one dummy car object.

I want to swap to Objects in LinkedList from 1st postion to 1000th
position.

For that I am taking 1st Object in dummyObject. Then Inserting
dummyObject at 1000th position and just removing the First Object.

What is the faster way? Will using TreeMap be faster?

Bye
Sanny

 

[Sanny]

Reading the documentation will help.
Also considering why you want to use a LinkedList
in the first place will eliminate a lot of confusion.
If you want to do a lot of swapping around of
members by index maybe an ArrayList would be
a better choice.

I use binarysearch to find the place where first element is to be
sent.

In binarysearch it has to check
---------------------
car dummycar= carlist.get(i)
if (dummycar.getpoints()>1000)
---------------

The above code is called 5/10 times I read somewhere Linkedlist.get()
is faster than ArrayList.get() This is why I chose LinkedList.

After binary search Swaping is to be done only once.

Alexender (Above) told me to use TreeMap Will that be faster if points
are Unique?

Bye
Sanny

 

[Jeff Higgins]

I use binarysearch to find the place where first element is to be
sent.

You have a collection of Cars.
Each car has a String name field
and an integer points field.
Each of these fields are accessible and mutable,
that is you have a getName, getPoints,
setName, and setPoints.

Now, what exactly do you want to do with your collection of Cars?

I want to;
Sort them? By name? By points? Both? Either?
Keep them sorted? When I change a field?
Access them? Quickly? By name? By points? By reference?
Insert/Remove more of them? Quickly?
etc....

In binarysearch it has to check

To read about the differences see these links.
ArrayList extends AbstractList
<http://java.sun.com/javase/6/docs/api/java/util/AbstractList.html>
LinkedList extends AbstractSequentialList
<http://java.sun.com/javase/6/docs/api/java/util/AbstractSequentialList.html>

For more information on the Java Collections Framework in general see:

After binary search Swaping is to be done only once.

Alexender (Above) told me to use TreeMap Will that be faster if points
are Unique?

Alexander may be more patient this morning than me,
sorry for my impatience.
For my part, you haven't answered enough questions yet to say.

 

[Lew]

BTW, the collections in java only store references to objects. So it
was a bad idea to use one dummy car object.

Sanny didn't do that - they assigned the variable to a new object each time:

for (int i=1; i<100000;i++){
String carname1=getname(i);
int carpoint1=getpoint(i);

car dummycar = new car(carname1,carpoint1) ;// Takes lot of time to
create this Object ????

carlist.add(dummycar);
}

(OP: Please use appropriate indentation, spell class names with upper-case
first letters, use camel case.)

The 'new' operation supposedly only takes on the order of a dozen machine
instructions, in that it does no more than bump a heap pointer up some bytes
and return a reference. Furthermore, the algorithm requires that you have an
object reference to put in the list, so it's a mistake to refer to it as a
"dummy". Without that reference, you'd have no list. It is no dummy.

 

[Lew]

To read about the differences see these links.
ArrayList extends AbstractList
<http://java.sun.com/javase/6/docs/api/java/util/AbstractList.html>
LinkedList extends AbstractSequentialList
<http://java.sun.com/javase/6/docs/api/java/util/AbstractSequentialList.html>

For more information on the Java Collections Framework in general see:
<http://java.sun.com/javase/6/docs/technotes/guides/collections/index.html>

In the case of ArrayList and LinkedList the respective Javadocs actually speak
directly to the performance of get():

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
vs.

Operations that index into the list will traverse the list from the beginning or the end,
whichever is closer to the specified index.

The Javadocs for LinkedList also state:

All of the operations perform as could be expected for a doubly-linked list.

which argues strongly for learning what to expect from a doubly-linked list.
<http://en.wikipedia.org/wiki/Linked_list>
et al.

 

[Jeff Higgins]

There is no swap() method.
Have you read the documentation?

Oops! Forgot about the Collections class.
Collections.swap(carlist, 1, 555);

Collections Class
<http://java.sun.com/javase/6/docs/api/java/util/Collections.html>

 

[Hendrik Maryns]

Sanny schreef:

I use binarysearch to find the place where first element is to be
sent.

In binarysearch it has to check
---------------------
car dummycar= carlist.get(i)
if (dummycar.getpoints()>1000)
---------------

The above code is called 5/10 times I read somewhere Linkedlist.get()
is faster than ArrayList.get() This is why I chose LinkedList.

After binary search Swaping is to be done only once.

Alexender (Above) told me to use TreeMap Will that be faster if points
are Unique?

Sounds like you don’t even need a TreeMap (what would be the keys?), but
just a TreeSet (which is a TreeMap in the background, but you shouldn’t
care about that), and either have Car implement Comparable<Car> of write
a suitable Comparator<Car>. Note that I use generics and I’d suggest
you do too, it will get rid of all the unnecessary casts. Look in the
Javadocs for Comparable and Comparator, and google for "java generics".

Also note that

car dummycar= carlist.get(i)

will *not* create a new object, but rather just assign a pointer.

H.
--
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFHwrj8e+7xMGD3itQRAjKzAJ40d7764nZH+GuRuX7lZ7IsueHnvgCdHfGV
WAcFsqMKzSzrSM5okbSeUbo=
=EV5f
-----END PGP SIGNATURE-----

 

[Roedy Green]

I find it very inefficient to add or retrive object from Linked List.

That is the nature of linked lists. You can only insert, delete if you
have a handle to the object at the spot where you want to
insert/delete.