CODEWITHSUNDEEP
javalinked-list
user5140999
user5140999

Reputation:

size of linkedList

I'm very new to Java, and I was given this Linkedlist set-up, I need to use recursion or while loop to write the size function that return the size of the linkedList. I guess I'm very confused as to how to do the size function when this linkedlist setup doesn't initialize Node, head etc.

package list;

public class LinkedList {
  public int value;
  public LinkedList next;

  public LinkedList (int value, LinkedList next) {
    this.value = value;
    this.next = next;
  }

  public static LinkedList list () {
    return new LinkedList(1, new LinkedList(2, new LinkedList(3, null)));
  }

  public int size () {
    int size = 0;
    Node Current = head;
    while(Current.next != null)
    {
      Current = Current.next;
      size++;     
    }
    return size;
  }
}

Upvotes: 1

Views: 11795

Answers (4)

Gowrav
Gowrav

Reputation: 289

public int size()
{
    int size = 1;
    LinkedList head = this;
    while (head.next != null)
    {
        head = head.next;
        size++;
    }

    return size;
}

Upvotes: 1

Mshnik
Mshnik

Reputation: 7042

Another way of computing size in a linked list like the one you've created is to use recursion. There are only two cases:

  1. A linked list with no next has size 1 - just itself
  2. A linked list with a next has size 1 plus the size of the next.

Thus, we have the following function:

public int size(){
    if(next == null){
        return 1;
    } else {
        return 1 + next.size();
    }
}

This can be written extremely concisely using a ternary operator:

public int size(){
    return next != null ? 1 + next.size() : 1;
}

For the iterative solution, there's no need to use the Node class, as each LinkedList object represents both itself (one single value) and all of the values to follow (a list of values). From that point of view, we have to loop from "here" until there is nowhere else to go.

public int size () {
   int size = 1;
   LinkedList Current = this;
   while(Current.next != null){
     Current = Current.next;
     size++;     
   }
   return size;
}

Upvotes: 2

Stephen C
Stephen C

Reputation: 719739

In your current formulation, your LinkedList instances are actually nodes as well as lists. That's OK, but it means that there is no distinguished "head" of the list ...

In this context, the fix is to change:

    Node Current = head;

to

    LinkedList current = this;

(And, yes, the size variable should start as 1. In this formulation, an empty list is represented by null. If you are calling size() on an instance of LinkedList, then the size of the list must be at least 1.)

@Konrad states "A list itself should encapsulate the nodes."

Actually that is a design choice. If you are following OO design principles then it should. However, there are situations where pragmatically you don't want to do that. Sometimes it is necessary to "sacrifice" abstraction to get better performance or reduce memory utilization.

Upvotes: 3

Konrad
Konrad

Reputation: 355

Change it like:

public int size () {
    int size = 0;
    // set the head as current note
    Node current = head;
    // while a current node is set
    while(current != null)
    {
      // increment site
      size++;     
      // and set the next as current node
      current = current.next;
    }
    return size;
}

The list itself is not a list. It's a linked list of nodes. A list itself should encapsulate the nodes.

Upvotes: 0

Related Questions