Linked List in Java

A linked list consists of sequence of nodes.

Each node contains a value and a link (pointer or reference) to some other node. The last node contains a null link. The list may (or may not) have a header.

More terminology

A node’s successor is the next node in the sequence the last node has no successor node’s predecessor is the previous node in the sequence. The first node has no predecessor list’s length is the number of elements in it list may be empty (contain no elements).


Pointers and references

  In C and C++, we have “pointers,” while in Java, we have "references," This  is essentially the same thing, The difference is that C and C++ allow you to modify pointers in arbitrary ways, and to point to anything, In Java, a reference is more of a “black box,” or ADT.

 Available operations are:

DE references (“follow”)

  copy

  Compare for equality

There are constraints on what kind of thing is referenced: for example, a reference to an array of into can only refer to an array of into.

 Creating references

  The keyword new creates a new object, but also returns a reference to that object.

  For example, Person p = new Person("John")

   New Person("John") creates the object and returns a reference to it.

  We can assign this reference to p, or use it in other ways.

class Cell {      int value;      Cell next;      Cell (int v, Cell n) { // constructor      value = v;      next = n; }      }      Cell temp = new Cell(17, null);      temp = new Cell(23, temp);      temp = new Cell(97, temp);      Cell myList = new Cell(44, temp);

Posted in: Data structure