CODEWITHSUNDEEP
javalist
user4060080
user4060080

Reputation:

Java-single-linked list and constructor

I am trying to figure out how to initialize the current object list in a List constructor so initially it doesn't contain any elements. How would I do this if I wanted to use a single-linked list? I know that this is a rather basic question about Lists haha. And how would it be different if I wanted to use a double-linked list, tail reference, circularly-linked, or dummy node (if it's not too annoying to do that for all of them)

       public class List<T extends Comparable<T>> implements Iterable<T> {
             private class Node<D extends Comparable<D>> {
                private D data;
                private Node<D> next;
              }

Upvotes: 2

Views: 175

Answers (1)

Jonatan Cloutier
Jonatan Cloutier

Reputation: 929

There is two way of thinking about linked list when it come to signalling the end of the list (which is basically the case of an empty list)

The first one is to set the node to null. After that when you do action on the list (add, remove, iterate) you can check if it's null before going further

The second one is to use a special object (called sentinel) that is use as flag instead of null. This might be a special node that when you get data from it throw an exception. The advantage being that you don't need to manage the null value in all method, but might have to manage the exception instead.

In case of double linked list, it's exactly the same, only the node content change (you have a back pointer that is added)

In case of tail reference, you add a pointer in you list class that keep a reference on the list tail, so you manage it as the head pointer, it's initially null or with a flag object and when the first object is added to the list, both reference will be updated on the same node.

In case of a circular list it's still stay the same for initialization, then when you add the first object, you link it to it self at the same time.

ex:

 public class List<T extends Comparable<T>> implements Iterable<T> {
         private class Node<D extends Comparable<D>> {
            private D data;
            private Node<D> next;
          }
          Node firstNode;

          public List(){
               firstNode=null;
          }

         // other methods
 }

Upvotes: 2

Related Questions