Problems with understanding a linked list implementation

Question

Update: Thanks a lot to everybody who responded!!! It made me feel that I'm not completely alone in my efforts to learn Java. Please excuse me, but I guess I didn't clarify enough what I don't get about linked lists and the exercise application -

first - how can a class definition contain an object of itself, OK I know that this is recursion but it's still a very strange and alien concept to me.

second - how exactly can a linked list object "link" to another node?

third - if two objects are separated by an equals sign it means what - that the second object disappears and what's left of it is it's "name" that now points to the first object or vice versa?

then - the thing that I don't get about the program I quoted below is the following: after the linkList class is instantiated it's constructor is called and it gives the object of class Link private Link first the value of null, i.e. sets it pointing to nothing. Then, when the first new node is created the method public void insertFirst is called, it gives the object values to its variables and then something absurd happens - the object first that points to nothing is assigned to the new item thus making both objects pointing to nothing and with the first = newLink; I'm completely lost...

I'm doing a college course on Algorithms and Data structures and since the professor is really mean and his explanations are useless I'm trying to learn on my own from a book called Algorithms and data structures by Robert Lafore.

Now I'm learning Linked lists and there is the following code example for a linked list implementation in the book:

Link.java:

class Link
   {
   public int iData;              // data item
   public double dData;           // data item
   public Link next;              // next link in list

   public Link(int id, double dd) { // constructor
      iData = id;                 // initialize data
      dData = dd;                 // ('next' is automatically
      }                           //  set to null)

   public void displayLink() {     // display ourself
      System.out.print("{" + iData + ", " + dData + "} ");
      }
   }

LinkList.java:

class LinkList {
   private Link first;            // ref to first link on list

   public LinkList() {             // constructor
      first = null;               // no links on list yet
      }

   public boolean isEmpty() {      // true if list is empty
      return (first==null);
      }
                                  // insert at start of list
   public void insertFirst(int id, double dd) { // make new link
      Link newLink = new Link(id, dd);
      newLink.next = first;       // newLink --> old first
      first = newLink;            // first --> newLink
      }

   public Link deleteFirst() {     // delete first item
      // (assumes list not empty)
      Link temp = first;          // save reference to link
      first = first.next;         // delete it: first-->old next
      return temp;                // return deleted link
      }

   public void displayList() {
      System.out.print("List (first-->last): ");
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      System.out.println("");
      }
   }

LinkListApp.java:

class LinkListApp {
   public static void main(String[] args) {
      LinkList theList = new LinkList();  // make new list

      theList.insertFirst(22, 2.99);      // insert four items
      theList.insertFirst(44, 4.99);
      theList.insertFirst(66, 6.99);
      theList.insertFirst(88, 8.99);

      theList.displayList();              // display list

      while( !theList.isEmpty() ) {        // until it's empty,
         Link aLink = theList.deleteFirst();   // delete link
         System.out.print("Deleted ");         // display it
         aLink.displayLink();
         System.out.println("");
         }
      theList.displayList();              // display list
      }
   }

I just CANNOT understand the code that inserts and displays items in the linked list class.

How can it be that newLink.next = first; and first = newLink; after the new object is created?

Please help!

Answer 1

Each Link holds a reference .next to the next Link element (except the last element, having .next = null.

A LinkList holds a reference (.first) to the first Link object it contains.

In order to insert a new Link at the front of the LinkList, we need to do the following:

1. Create a new Link object to insert in front (newLink).
2. Let the newly created Link point to the previous first Link object as its .next
3. Reset the .first reference of the LinkList to the newLinkobject, effectively overwriting the previous reference (marked with a cross below).

This is exacly what's going on:

public void insertFirst(int id, double dd) {
    Link newLink = new Link(id, dd);
    newLink.next = first;
    first = newLink;
}