How to implement a sorted custom list class

Question

So i have a class called List and a class called SortedList which inherits the class List. Also there is a class called node. I have created another class which contains the printing method.

But, everytime i insert three names for example, and i call the printing method it only prints the last name i have inserted. So my question is: does this code makes a sorted list? And if so, why does it print only the last name?

List class:

public class List {

    protected Node head;
    protected int length;

    public void list()
    {
        head=null;
        length=0;
    }
    public boolean isEmpty()
    {
        return head==null;
    }
    public Node insert(Item a)
    {
        length++;
        head=new Node(a, head);
        return head;
    }

SortList class:

public class SortList extends List {

    private Node head;
    public SortList()
    {
        this.head=null;
    }
    public Node getFirst()
    {
        return head;
    }
    public Node Insert(Item newitem)
    {
        Node node = new Node(newitem);
        Node previous = null;
        Node current = head;
        while(current!=null && current.getValue().less(newitem))
        {
            previous=current;
            current=current.getNext();
        }
        if(previous==null)
        {
            head=node;
        }
        else
        {
            previous.setNext(node);
            node.setNext(current);
        }
        return head;
    }
    public void printlist()
{

    Node current = head; //ΑΡΧΗ ΤΗΣ ΛΙΣΤΑΣ.
    while(current!=null)
    {
        current.print();
        current = current.getNext();
    }
}

Node class:

public class Node {

    private Item info;
    private Node next;
    public Node(Item dat)
    {
        info=dat;
    }
    public Node (Item dat, Node b)
    {
        info=dat;
        next=b;
    }
    public Item getValue()
    {
        return info;
    }
    public void setNext(Node a)
    {
        next=a;
    }
    public Node getNext()
    {
        return next;
    }
    public void print()
    {
        info.print();
    }
}

@ᴳᵁᴵᴰᴼ You... must... use... Python...! Not... JAVA! — Zizouz212
– Zizouz212, Commented May 16, 2015 at 23:37
Why can't you use Collections.sort() on every change in the list's content? — Malik Brahimi
– Malik Brahimi, Commented May 16, 2015 at 23:37
Look at the constract of the List class public void list() it must be public void List() — Maraboc
– Maraboc, Commented May 16, 2015 at 23:38
Well thank you very much but i have to complete a project for my technical university and we have to use Java. So... — Maria
– Maria, Commented May 16, 2015 at 23:40
@Maria don't you get a nullpointerexception when trying to put the very first node inside the sortedlist? — guido
– guido, Commented May 16, 2015 at 23:42

TimoStaudinger · Accepted Answer · 2015-05-17 00:03:37Z

3

In your Implementation of List, you have a major bug in the insert() method:

public Node insert(Item a)
{
    length++;
    head=new Node(a, head);
    return head;
}

You do not attach the new element to the end of the list, but rather replace the list's head each time, thus discarding the previous element.

This would explain why you always only see the last element you have inserted.

Edit: Turns out, the insert() method actually does work, since you set the reference to the next node in the node's constructor.

In your sorted list however, you have one insert case for which the next node is not set:

if(previous==null)
{
    head=node;

}

I your sorted list, you don't set the next element in the constructor of the node. In all other cases, you set the next element in the insert() method, but not in this case. If the element you want to insert is the smallest in the list, previous is null, which is correct -- your new element is the new head of the list. Since you don't set the new element's successor, however, all elements that have been in the list are now gone.

If the last element you insert into the list is the smallest, the last element will also be the only one remaining and you print out only the last element.

Try setting the successor:

if(previous==null)
{
    head=node;
    head.setNext(current);
}

edited May 17, 2015 at 0:03

answered May 16, 2015 at 23:36

TimoStaudinger

42.7k16 gold badges91 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

guido Over a year ago

mmh, the head maybe should be renamed tail... but it should still work becuase the reference is not discarded, the current head reference will be next for the new head

Maria Over a year ago

Ok, i understand what you say but can you be more specific? Can you give me an example or the correct code?

TimoStaudinger Over a year ago

@ᴳᵁᴵᴰᴼ is actually right, your code should work. I just missed that the reference to the next element is set inside the constructor of the new Node. My Bad!

Collectives™ on Stack Overflow

How to implement a sorted custom list class

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related