macOS Double Linked List in Java

[jsmwoolf]

In my Calculator app, I plan on adding a GCF and LCM function. However, it appears that I need a double linked list in order to do this(where one is for the numbers and the other is for any number that can divide from it). I'm not asking for you guys to write me a GCF and/or LCM function. I'm only asking on how to set up a double linked list up as I don't exactly know how to.

In C, one would have to create as structure and then declare a pointer within a structure in order for it to create addresses without predefining. You would then define three more structure pointers outside of the structure. In a double linked list, you would then declare yet three more structure pointers to deal with the second list. It somewhat works the same way in C++, only that you would only use a class instead of a structure.

Based on the research that I did, you would have to use the LinkedList and List class in Java. However, you also need a node which baffles me because I don't exactly know what that is and how to set one up appropriately. I basically need to store double values(as in number, obviously).

 

[subsonix]

AFAIK you don't need to create a node when using Java container classes, all that is implementation details that is hidden for your convenience. Instead you have methods for adding and lookup items and so on in the container. You have to look at the documentation for the class you intend to use to find out what methods are available to that particular class.

Edit, for example:

http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html#addFirst(E)

Where E is the type you have declared your list to hold.

 

[jsmwoolf]

No node? Okay, would setting up a double linked list look something like this?

List<List<double>> numberList = new LinkedList<List<double>();

I don't exactly know what goes in the <E> part, but I'm dealing with double values.

I never worked with LinkedLists in Java, especially double LinkedLists, so I don't understand much about working with LinkedLists in Java.

 

[subsonix]

No node? Okay, would setting up a double linked list look something like this?

List<List<double>> numberList = new LinkedList<List<double>();

I don't exactly know what goes in the <E> part, but I'm dealing with double values.

I never worked with LinkedLists in Java, especially double LinkedLists, so I don't understand much about working with LinkedLists in Java.

I think this is the correct way of doing it if you plan to store doubles in the list:

List<double> numberList = new LinkedList<double>();

But, it was a while since I did any Java development so that may be wrong, lol. However the general idea is that you declare your list to hold doubles, and that's it. Details about nodes and so on is hidden behind the interface.

 

[chown33]

In C, one would have to create as structure and then declare a pointer within a structure in order for it to create addresses without predefining. You would then define three more structure pointers outside of the structure. In a double linked list, you would then declare yet three more structure pointers to deal with the second list.

Huh?

In C:

struct dlinked {
  struct dlinked * next;
  struct dlinked * prev;
  double number;
};

To declare an instance of a dlinked list:

struct dlinked listA;

To declare an instance with null links and 0 for the number:

struct dlinked listB = { NULL, NULL, 0 };

Rough equivalent in Java:

public class DLinked {
  public DLinked next;
  public DLinked prev;
  public double number;
}

Have you tried googling: doubly linked list java

 

[subsonix]

Rough equivalent in Java:

public class DLinked {
  public DLinked next;
  public DLinked prev;
  public double number;
}

However, the Java class library has a large amount of containers like linked lists, much like STL in C++. There's no reason to implement a list of your own if you don't have special requirements that the standard containers cant live up to IMO.

 

[chown33]

However, the Java class library has a large amount of containers like linked lists, much like STL in C++. There's no reason to implement a list of your own if you don't have special requirements that the standard containers cant live up to IMO.

Except the OP seemed to be stumbling on the <type> generics syntax, so the simplest thing that worked seemed like a better initial strategy.

And I'm not sure why one needs doubly-linked lists for GCF or LCM anyway (presumably Greatest Common Factor and Lowest Common Multiple). As I recall, there are iterative calculations that can produce those values.

Doubly-linked lists seems like the intention of a space/time tradeoff (more space, less time), but without knowing the details my first guess is that list-traversal is at least as costly as calculations on doubles. The reason for that guess is there's usually floating-point hardware, but list-traversal is still done the old-fashioned way.

 

[lee1210]

You can definitely use built-in java collections for whatever you need. You will have to use the capital-D Double because Java collections only store Objects, not primitives like lowercase-d double. Java does have fancy autoboxing and autounboxing to make this fairly transparent, but it's something to be aware of generally.

-Lee

 

[jiminaus]

Although it's not required, the most likely implementation of java.util.LinkedList is as a doubly-linked list.

Quote from JDK 6 Docs:

Linked list implementation of the List interface. [...] These operations allow linked lists to be used as a stack, queue, or double-ended queue. [...] All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

 

[talmy]

And I'm not sure why one needs doubly-linked lists for GCF or LCM anyway (presumably Greatest Common Factor and Lowest Common Multiple). As I recall, there are iterative calculations that can produce those values.

Exactly. The OP is wasting his and his computer's time solving this problem with linked lists!

 

[jsmwoolf]

Well, I thought that since linked lists are useful for storing an array of data without a specific limit and since finding the Greatest Common Factor and the Least Common Multiples is never entirely known, I thought that in order to do this I would need to store multiple numbers and then checking whether the number is the highest(GCF) or whether the number is the lowest(LCM).

As I recall, there are iterative calculations that can produce those values.

As I just looked up, iterative calculations is simply repeating a specific command until you get a desired result. But if I ditch the LinkedList solution, then how do I store an unknown amount of numbers and check which one is the right number?

 

[talmy]

As I just looked up, iterative calculations is simply repeating a specific command until you get a desired result. But if I ditch the LinkedList solution, then how do I store an unknown amount of numbers and check which one is the right number?

You don't have to. Look up "Greatest Common Divisor" on Wikipedia for the algorithm. Use Euclid's Algorithm. Get the LCM from the GCD.

 

[chown33]

The point of a calculation is that you don't have to store any numbers.

Here, "iterative calculation" simply means "a calculation with a loop", as distinct from a recursive calculation or some other type of calculation. The loop is to find the GCD (e.g. Euclid's algorithm), from which LCM can then be calculated.

Simple algorithms for LCM and GCF can easily be found on Wikipedia:
http://en.wikipedia.org/wiki/Least_common_multiple

"The following formula reduces the problem of computing the least common multiple to the problem of computing the greatest common divisor (GCD):"
​

http://en.wikipedia.org/wiki/Greatest_common_divisor

or by googling for suitable search terms, such as:
java GCD
java LCM

 

[jsmwoolf]

Euler's Algorithm is simply taking two numbers and subtracting them until the two numbers equal them, according to what it seems. So it appears I overestimated the problem. I never knew you could do that. Well, I learned something new today.

 

[chown33]

Euclid's algorithm. Euler is a completely different person, almost 2 millenia later.

When you're implementing math functions, it's always a good idea to search first, either google or Wikipedia.

 

[jsmwoolf]

Oh, how stupid I am. I can't even put the right name on the post let alone find simpler solutions.

Anyway, thanks for helping me out.

 

[gnasher729]

In my Calculator app, I plan on adding a GCF and LCM function. However, it appears that I need a double linked list in order to do this(where one is for the numbers and the other is for any number that can divide from it). I'm not asking for you guys to write me a GCF and/or LCM function. I'm only asking on how to set up a double linked list up as I don't exactly know how to.

Euclid knew how to calculate the greatest common divisor (GCD) of two integers very easily and very efficiently without using a doubly linked list. Google for "Euclid Algorithm".

Can I repeat an important rule: When you want to solve a problem X, ask how to solve the problem X. Don't go off and find Y that you think will help you and ask how to solve Y. When you ask for solving X, people _may_ tell you to do Y and how to do it, but much more likely they will give you something that is a lot better in the first place.

 

[foidulus]

For the doubly linked list, I think you are trying too hard.

In Java for all classes that implement the List interface you can specify the index you want when you are retrieving or modifying something in the list. So if you are iterating through a list forwards and want to go backwards, all you have to do is start decrementing this index, to go forwards increment it.

The exact type of list that will be most efficient for you will vary depending your usage. For example if you can roughly estimate the capacity of your list when you start and mostly just append to the end of the list, ArrayList will probably be the most efficient, if you frequently change items in the middle, a LinkedList(which as others have said is most likely implemented as a doubly linked list) will probably be more efficient.

However, these are secondary considerations, using the most efficient algorithm is the biggest priority.

And since nobody else pointed it out, why are you using doubles to do GCD and LCM calculations? These algorithms only work with integers, so you would be much better off using ints or longs, as although it is unlikely, you could potentially run into rounding errors with doubles that could yield incorrect results.