12 Replies - 3500 Views - Last Post: 12 June 2012 - 08:53 PM Rate Topic: -----

#1 smoothedatol412  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 22-May 12

multi dimensional linked list

Posted 10 June 2012 - 12:14 AM

Is it possible to create a "multi dimensional" linked list in Java, like you can do with an array data structure? I am getting a little tried of using arrays.
Is This A Good Question/Topic? 0
  • +

Replies To: multi dimensional linked list

#2 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2553
  • View blog
  • Posts: 10,641
  • Joined: 20-September 08

Re: multi dimensional linked list

Posted 10 June 2012 - 04:00 AM

Certainly. Instead of List<T> you could have List<List<T>> for two dimensions
Was This Post Helpful? 0
  • +
  • -

#3 smoothedatol412  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 22-May 12

Re: multi dimensional linked list

Posted 10 June 2012 - 11:43 PM

and what does [List<T>] mean?
Was This Post Helpful? 0
  • +
  • -

#4 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2553
  • View blog
  • Posts: 10,641
  • Joined: 20-September 08

Re: multi dimensional linked list

Posted 11 June 2012 - 06:30 AM

A List of some type, 'T'
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,586
  • Joined: 27-December 08

Re: multi dimensional linked list

Posted 11 June 2012 - 07:45 AM

A multidimensional LinkedList, as you are describing, probably isn't the most efficient way to model your data. Don't use LinkedLists because you are tired of using arrays; use them because they are the better option for organizing your data. For most tasks, a multidimensional array is probably the better choice.
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7292
  • View blog
  • Posts: 12,102
  • Joined: 19-March 11

Re: multi dimensional linked list

Posted 11 June 2012 - 08:00 AM

The trick is to know what the available data structures are and what they can do for you.


Linked lists are good for sequential processing of data - the only access is from one item to the next, any search or random access is purely a derived process, and therefore slow, so you mostly want to use them when you're interested in treating their contents as a list of stuff.

A Linked List of Linked Lists sounds a little weird to me, but it's possible that you'd be generating lists, each of which needs to be processed by some scheme. I'm having trouble coming up with a use case, but that's when you'd want something like this.

The best I can come up with is this: you have an object which accepts Linked Lists and does something with them, in real time. It has a queue, and other objects can hand it Lists, which it drops into its queue. When the queue is not empty, it's taking lists out of it and doing some processing on them. That would be a List of Lists.

There are probably other cases where you'd use this, but as mac says, it's not something you'd reach for usually. If you can spell out what it is you're trying to do, there's probably a better way to do it.

This post has been edited by jon.kiparsky: 11 June 2012 - 08:00 AM

Was This Post Helpful? 2
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,586
  • Joined: 27-December 08

Re: multi dimensional linked list

Posted 11 June 2012 - 08:07 AM

Quote

A Linked List of Linked Lists sounds a little weird to me, but it's possible that you'd be generating lists, each of which needs to be processed by some scheme. I'm having trouble coming up with a use case, but that's when you'd want something like this.

The only real case I can think of for something like this is a Graph, and there are more efficient ways of designing a Graph class.
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7292
  • View blog
  • Posts: 12,102
  • Joined: 19-March 11

Re: multi dimensional linked list

Posted 11 June 2012 - 08:10 AM

Quote

The only real case I can think of for something like this is a Graph, and there are more efficient ways of designing a Graph class.


Yeah, mine was a bit of a reach. I think I strained something...
Was This Post Helpful? 0
  • +
  • -

#9 smoothedatol412  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 22-May 12

Re: multi dimensional linked list

Posted 11 June 2012 - 11:32 AM

What I need a Multi Dimensional linked list is for doing adjacency matrices work with graphs; dijkstra's shortest path algorithm I do not want to use array, for the simple reason that I like using Linked List better. Even though using an array would be more simpler and easier to understand for someone reading the code, its still my code and linked list is the data structure that I want to use to represent that data and the reference between them.
Was This Post Helpful? 0
  • +
  • -

#10 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7292
  • View blog
  • Posts: 12,102
  • Joined: 19-March 11

Re: multi dimensional linked list

Posted 11 June 2012 - 11:39 AM

I guess there's something weirdly respectable about an aesthetic commitment to a particular data structure.

So you've got your answer: yes, you can.

List<Node> would be a list of Nodes, List<List<Node>> would be a list of lists of lists of Nodes.

You might consider the advantages of making an object to wrap around that inner list, but yes you can do this with a list of lists.
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,586
  • Joined: 27-December 08

Re: multi dimensional linked list

Posted 11 June 2012 - 11:55 AM

An adjacency matrix is not a good tool for pathfinding algorithms like Dijkstra's because you have to deal with non-adjacent vertices and adjacent vertices. A series of adjacency lists is really a better way to set things up. At the very least, a Map<Node, List<Node>> to map each Vertex to its adjacent Vertices is cleaner. I have a Graphs tutorial as well if you want a more involved Graphs class, and an associated tutorial on Dijkstra's algorithm.

Some supplemental reading as well on representing graphs: http://www.dreaminco...senting-graphs/
Was This Post Helpful? 1
  • +
  • -

#12 smoothedatol412  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 22-May 12

Re: multi dimensional linked list

Posted 12 June 2012 - 11:18 AM

I just like coding everything from the ground up by myself, so I know what is really going on inside of the data structure and how is it managed in the computer's memory either by being static or dynamic. Arrays are too much of a started data structure, with a finite number of elements that have to be estimated before being compiled, where as a linked list can hold an unlimited number of reference depending on the size and availability of the computer's memory.
I like being in total control of my data and the structure that are built around it.
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,586
  • Joined: 27-December 08

Re: multi dimensional linked list

Posted 12 June 2012 - 08:53 PM

Implementing your own data structures to learn is a good thing. A lot of times though, an ArrayList or a static array is better to use than a LinkedList, due to the efficiency tradeoffs. Especially if you're doing Graph Theory work, choose what's efficient and easy to work with rather than trying to overcomplicate things. You'll be doing yourself a real disservice overcomplicating things with graph theory.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1