trying to understand how linked lists work

shollpat · August 11th, 2011, 08:59 PM

Hi,
I started programming using FORTRAN (yes, I'm ancient) and we used matrices and indexing for connecting things to "next-things". I am starting to use Java and am looking at a chapter on linked lists and I am having a hard time visualizing how things are connected. For example, we have a node:

public class ListPoint
{
private Point point; // the x,y coordinate for this list point
private ListPoint next; // refers to next ListPoint in the list
etc.
}

To me, this looks recursive. However, I don't really understand it. Is the compiler taking care of connecting the points by "indexing" internally? or what?!

Need more of the code? - let me know.
Thanks all!
Pat

n0v1c3 · August 17th, 2011, 01:33 AM

Hello,

I am new to the forums however, I can try to help.

The class is the outline for each declaration of ListPoint. Simply put each time you create a new ListPoint the object created contains a pointer to a Point and a pointer to a ListPoint.

You can now set the ListPoint pointer inside of your newly created ListPoint object to any ListPoint object.

Code:

ListPoint first = new ListPoint();
ListPoint second = new ListPoint();
ListPoint last = new ListPoint();

first.setListPoint(second); //Assuming set function exists in class ListPoint
second.setListPoint(last); //first.getListPoint().setListPoint(last);

first.toString(); //Output "first"
first.getListPoint().toString(); //Output "second"
first.getListPoint().getListPoint().toString(); //Output "last"

The variable first and the ListPoint next contained inside of it are stored the same way, as a pointer to the space in memory that the Object has been created.

shollpat · August 17th, 2011, 10:20 PM

Thanks! that helps.
pat

n0v1c3 · August 18th, 2011, 12:09 PM

Glad I could help, I hope...

If you are new to Java, I would take some time to master Double Linked Lists to the point where you can set up a Search Tree.

Hint:

Code:

public class Node
{
  private Node leftNode;
  private Node rightNode;

  private int/char/String data;
}

Understanding this is important, especially later as multiple classes are accessing the same object. You don't want to accidentally change the data of the object in one class and expect it to have remained constant in a different one. I have seen many people mess this up.

For Example:

Code:

private Node node1 = new Node(SomeData);
private Node node2 = node1;

Now node1 and node2 are pointing to the same space in memory. Now if a change is made to the data in one the data changes in both.

Code:

node2.setData(NewData);
node1.toString(); //Revels NewData , SomeData is lost forever