Long Linked List

Linked List of length long

Page 1 of 1

13 Replies - 3154 Views - Last Post: 26 July 2008 - 04:43 PM Rate Topic: -----

#1 tjd195  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 21-July 08

Long Linked List

Post icon  Posted 21 July 2008 - 02:15 PM

Does anyone know if it is possible to create a linked list with a long as it's counter?
Is This A Good Question/Topic? 0
  • +

Replies To: Long Linked List

#2 JeroenFM  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 18
  • View blog
  • Posts: 195
  • Joined: 30-June 08

Re: Long Linked List

Posted 21 July 2008 - 03:20 PM

View Posttjd195, on 21 Jul, 2008 - 02:15 PM, said:

Does anyone know if it is possible to create a linked list with a long as it's counter?


Not using the Java Collections framework, the java.util.Collection framework mandates that the return type of size() is int

You can of course make your own implementation of a linked list.

Though I must ask, is a list really the best option if you're going to store more than 2.1 billion items?

This post has been edited by JeroenFM: 22 July 2008 - 02:43 AM

Was This Post Helpful? 0
  • +
  • -

#3 tjd195  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 21-July 08

Re: Long Linked List

Posted 21 July 2008 - 08:25 PM

I think a list would be best because to extend an array to use a long you must over write collection and linked list plus a ton more classes, but if you have another opinion I would love for you to share it. Also I was asking about this because I had already rewritten Linked List and all of it's implemented classes, but had gotten a warning. Thanks.
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Long Linked List

Posted 21 July 2008 - 09:04 PM

View Posttjd195, on 21 Jul, 2008 - 08:25 PM, said:

I think a list would be best because to extend an array to use a long you must over write collection and linked list plus a ton more classes, but if you have another opinion I would love for you to share it. Also I was asking about this because I had already rewritten Linked List and all of it's implemented classes, but had gotten a warning. Thanks.

I don't know what will be the size (memory wise) of the objects you want to insert into your LinkedList but with standard memory settings:

public static void main(String[] arg) {
	LinkedList<Integer> list = new LinkedList<Integer>();
		
	for(int i = 0; i < Integer.MAX_VALUE; i++) {
		list.add(new Integer(i));
		if(i % 10000 == 0)
			System.out.println(i + " inserted out of " + Integer.MAX_VALUE);
	}
}



1600000 inserted out of 2147483647
1610000 inserted out of 2147483647
1620000 inserted out of 2147483647
1630000 inserted out of 2147483647
1640000 inserted out of 2147483647
1650000 inserted out of 2147483647
1660000 inserted out of 2147483647
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space


Was This Post Helpful? 0
  • +
  • -

#5 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Long Linked List

Posted 22 July 2008 - 11:27 AM

To put a finer point on it, if you use data type long, you can have up to 9,223,372,036,854,775,808 items in the list. Say each node in this linked list contains the smallest possible data type in Java: a byte. That's nine quintillion, two hundred twenty-three quadrillion, three hundred seventy-two trillion, thirty-six billion, eight hundred fifty-four million, seven hundred seventy-five thousand, eight hundred and eight bytes, or approximately 9.223 ExaBytes. If you have a computer that can handle this I'd really like to see it. :)

This post has been edited by Programmist: 22 July 2008 - 11:28 AM

Was This Post Helpful? 1
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Long Linked List

Posted 22 July 2008 - 06:15 PM

Programmist really thanks for the numbers... didn't want to spend time to do them
But you are right stating

Quote

If you have a computer that can handle this I'd really like to see it. :)


And I'll buy one (my daily job is in C on 64KB boards) every byte we can save... we save including iniatilization routines code that we convert into data buffer.
Was This Post Helpful? 0
  • +
  • -

#7 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Long Linked List

Posted 23 July 2008 - 01:16 AM

Well, theoretically if he writes a List that can persist it's elements onto disk, then an int counter could really make a problem.
Also, I'm not sure, but I think Java will allocate the space required by an integer even for a byte for memory organization reasons (at least on several architectures it would be reasonable because of hardware limitation).
Finally the answer for the op: it is possible, but you have to implement it. You could make something that implements the List interface and provides special functions for larger than Integer.MAX_VALUE indexes, or simply forget about the List/Collection interface altogether, and write one on your own.
Was This Post Helpful? 0
  • +
  • -

#8 tjd195  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 21-July 08

Re: Long Linked List

Posted 23 July 2008 - 05:33 PM

I understand there are probably no current computers that could hold a full long list, but I think all of us will agree one day, and sooner then later, there will be and as a computer scientist of future days it is my duty, nay my calling to prepare for that day. So instead of having to update all existing code on that day I can have it done and ready and have my name on it.
P.S. I am working on this in order to to have a number with a long worth of digits. Then I can break the numbers into sets of 18 and use class Long for addition and subtraction.

This post has been edited by tjd195: 23 July 2008 - 05:47 PM

Was This Post Helpful? 0
  • +
  • -

#9 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Long Linked List

Posted 23 July 2008 - 06:01 PM

View Posttjd195, on 23 Jul, 2008 - 05:33 PM, said:

I understand there are probably no current computers that could hold a full long list, but I think all of us will agree one day, and sooner then later, there will be and as a computer scientist of future days it is my duty, nay my calling to prepare for that day. So instead of having to update all existing code on that day I can have it done and ready and have my name on it.
P.S. I am working on this in order to to have a number with a long worth of digits. Then I can break the numbers into sets of 18 and use class Long for addition and subtraction.

In that case, while you are at it, use a BigInteger :)
Was This Post Helpful? 1
  • +
  • -

#10 tjd195  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 21-July 08

Re: Long Linked List

Posted 23 July 2008 - 06:55 PM

Thanks pbl, that is a great insight and gives it the next step of grandeur I had not noticed. I have had this idea for so long I am starting to get a little near sighted with it.
Was This Post Helpful? 0
  • +
  • -

#11 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Long Linked List

Posted 24 July 2008 - 01:13 AM

Solving a problem as a computer scientist is one thing, and solving one as an engineer is another one.
If you solve this as a cs, you might create something that sounds good, and works well, but a total overkill, because you did not take current possibilities in consideration, and at the bottom line, it will be less efficient on several levels than the optimal real-life solution.
If you solve it as an engineer, then you will neglect such things as what to do after 10 years, and you can concentrate onto the present situation with reasonable foresight.
I'd say by the time such linked lists will be needed or at least possible that use long or maybe biginteger counters, I'd bet that the Java Collection Framework will be updated as well, and you won't have to modify your code. This thing is part of the API, you don't have to worry about it. (Or if it isn't, you can create a wrapper class in 10 minutes)
Was This Post Helpful? 0
  • +
  • -

#12 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Long Linked List

Posted 24 July 2008 - 04:37 PM

View Post1lacca, on 24 Jul, 2008 - 01:13 AM, said:

Solving a problem as a computer scientist is one thing, and solving one as an engineer is another one.
If you solve this as a cs, you might create something that sounds good, and works well, but a total overkill, because you did not take current possibilities in consideration, and at the bottom line, it will be less efficient on several levels than the optimal real-life solution.
If you solve it as an engineer, then you will neglect such things as what to do after 10 years, and you can concentrate onto the present situation with reasonable foresight.


That remembers me my university years.
I was studying in physics and we had common seminars/presentations with the folks from the mathematic department.

Us in physics, we were presenting how we solved some equations by scrating out "negligible value" elements from on side of the equation or the other. The guys from math were almost having hart attack. For them the result was completly wrong. What is the weight of a Saturn moon in the total weight of the solar system ?

When the presentator was from the math department we though, the physics guys, that these folks were nuts to use 50 additional lines of formula to remove a negligible value from one side of the equation. The final weight will be "almost" the same.
Was This Post Helpful? 0
  • +
  • -

#13 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Long Linked List

Posted 25 July 2008 - 01:52 AM

Exactly my point :D
Was This Post Helpful? 0
  • +
  • -

#14 tjd195  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 21-July 08

Re: Long Linked List

Posted 26 July 2008 - 04:43 PM

1lacca if you stand still on the tracks you get run over by the train. I am considering how to use these know class to create the fastest possible mathematical calculation between any two given vastly large numbers.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1