Linked Lists

[KimJack]

Hello All,

I have absolutely no experience with linked lists. I have an array of Animals that I am trying to reference from a linked list located in another class. Can anyone point me in the right direction for starting this program?

Any assistance would be appreciated.

Thanks

[Ezzaral]

You aren't very clear in what it is that you are wanting to do. What is the point of using a linked list in one class to access an array of objects in another?

You'll need to post a bit more information.

[KimJack]

Well, it really is pointless, isn't it? But I thought it would be more efficient for adding and removing "Animals" in the middle of a linked list vice an array. I am just wondering can a linked list reference an array in another class? If so, any suggestions on the initial steps.

Any assistance or suggestions would be appreciated.

[Ezzaral]

What you are wanting to do isn't making any sense to me, so I can't answer the question very well. A linked list does not reference an array. It functions by maintaining links to the next (and sometimes previous) entry object in the list. So I'm not really sure what it is that you are wanting to acheive.

[~s.o.s~]

> I am just wondering can a linked list reference an array in another class?
Yes, a linked list can contain references to an array of any reference type.

List<Integer[]> l = new LinkedList<Integer[]>();
l.add(new Integer[] {1,2,3});

It would have been easier had it been done without generics but if you are using Java 1.5 and above, generics is the way to go. Read up on generics and the Javadocs of java.util package for more details.

[javaAddict]

What do you mean referencing an array from another class? What are you trying to do?

[KimJack]

I have an array of "Animals". I would like to be able to add to and delete from the array. This, however, is not efficient. So, I would like to use a linked list. I thought that I could simply reference the array with a linked list and use the functions of the linked list to add and delete items more efficiently.

Each animal in the array has strings:

Animal("name", "description")

So I am simply trying to figure out how use a linked list to add and delete since it is more efficient than adding and deleting from an array.

Any assitance would be appreciated.

[javaAddict]

Create an Animal class:

public class Animal {
  private String description;
  private String name;
  //appropriate constructor and get, set methods. Perhaps a toString() method
}

Then create another class in which you declare you LinkedList. The list might be private, and the class will have methods to add, get, remove Animal objects.
Personally I prefer the Vector class
ex:

//inside the second class:
private Vector v=new Vector();
//plus some other methods, constructor

public void add(Animal a) {
  v.add(a);
}

[~s.o.s~]

> Personally I prefer the Vector class

This is a wrong choice on two counts. First, Vector implementation internally uses arrays so it's no different from using an array in the first place. The only thing different is that you would now have an array which you can grow / shrink on demand. Secondly, Vector is synchronized so you suffer a performance penalty of having a concurrency check even when you don't need it. Vector is anyways a bad choice even if you need to ensure correct access. Hand crafted concurrency using ArrayLists is far better than using Vectors. Google it up and you would find a lot of interesting things.

> I have an array of "Animals". I would like to be able to add to and delete from the array.
> This, however, is not efficient.

So why use arrays in the first place? Why not just go with LinkedList class from the util package if all you want to do is a lot of insertion/deletion?

[javaAddict]

Well, if you think it's better he should use ArrayLists then.

[Ezzaral]

ArrayList still has nothing to do with a linked list, both are array-backed, so it doesn't really matter.

[~s.o.s~]

> ArrayList still has nothing to do with a linked list, both are array-backed, so it doesn't really
> matter.

A linked list is not array-backed but composed of a chain of nodes, each pointing to the next in the chain or null, in case of the tail element.

[Ezzaral]

> ArrayList still has nothing to do with a linked list, both are array-backed, so it doesn't really
> matter.

A linked list is not array-backed but composed of a chain of nodes, each pointing to the next in the chain or null, in case of the tail element.

Yes, that was my point. He mentioned using Vector and then ArrayList - neither of which have any relation to a linked list. Perhaps my use of "both" wasn't really qualified there very well. I was referring to the previous suggestion of Vector.

[javaAddict]

I don't think it makes any difference. They both work for what he needs them.

[KimJack]

Can anyone recommend any websites or books about linked lists?

Thanks for all your input.

[Ezzaral]

It's still unclear why you are hung up on the linked list thing. You mentioned that you wanted to make it easier to insert in the middle, but is that the only thing you require?

Though we got a bit off track with the linked list discussion, javaAddict's suggestion of ArrayList is perfectly valid if you just need a container that's easier for you to manage. It is backed by an array, but the ArrayList API manages all the manipulations internally and you just have to call the methods to add/remove/get any component you wish. Is this homework that will not allow you to use standard API collections? If it isn't, then consider just using an ArrayList for the collection.

[KimJack]

Yes, it is for an assignment. I am not asking for answers only a point in the right direction.

[~s.o.s~]

The Sussex data structure notes along with the explanation given here should suffice for the time being. Do look into the source code of the LinkedList class to get a better understanding of how things work under the hood.