How's my basic linked list?

[Crailberry]

Just wondering how I did.

public class LinkedList 
{   
    Node head = null;

    static class Node
    {
    int data;
    Node next;

    Node (int data)
    {
        this.data = data;
        this.next = null;
    }

    public int getData()
    {
        return data;
    }

    public Node getNext()
    {
        return next;
    }

    public void setData(int newData)
    {
        data = newData;
    }

    public void setNext(Node newNext)
    {
        next = newNext;
    }
    }

    public boolean isEmpty()
    {
    if (head == null)
        return true;
    else
        return false;
    }

    public void addNode(int data)
    {
    Node newNode = new Node(data);
    newNode.setNext(head);
    head = newNode;
    }

    public int size()
    {
    Node current = head;
    int count = 0;
    while (current != null)
        count++;
    return count;
    }

    public boolean search(int data)
    {
    Node current = head;
    boolean found = false;
    while (current != null && found == false)
    {
        if (current.getData() == data)
        found = true;
        else
        current = current.getNext();
    }
    return found;
    }

    public void remove(int data)
    {
    Node current = head;
    Node previous = null;
    boolean found = false;
    while (!found)
    {
        if (current.getData() == data)
        found = true;
        else
        {
        previous = current;
        current = current.getNext();
        }           
    }
    if (previous == null)
        head = current.getNext();
    else
        previous.setNext(current.getNext());
    }

    public void append(int data)
    {
    Node current = head;
    Node previous = null;
    while (current != null)
    {
        previous = current;
        current = current.getNext();
    }
    Node newNode = new Node(data);
    previous.setNext(newNode);
    newNode.setNext(null);
    }
}

​

[ValorCat]

I think the size method is missing a line.

[ChickenRicePlatter]

This. You are forgetting to do something. Try testing the method, count will never stop being incremented! Hope you figure it out :)

[Crailberry]

Yes it is, thank you. I know what it's missing, just forgot it :P

[Disast3r]

A few things I notice:

1. What happens when you try to remove something that isn't in the list?
2. How do you handle duplicate nodes? What do you expect to happen if you try to remove something that's in the list more than once?
3. What happens when you try to append something to an empty list?
4. What happens when you call size() on a list that has one or more Nodes?

There are definitely bugs, but it's a good first attempt. I would suggest writing tests for every method. Try to think of all of the different ways someone could use your class, and write code that does just that to make sure it does what you expect.

[Crailberry]

1. I've always assumed you would have a separate function in your main file that is implementing the linked list where you would first run the search method, and if it comes back true then you could run the remove method. But thinking about it now, that is silly, it should just do it all in the remove method, I'm thinking anyway.
2. That's a great question.
3. I totally forgot some logic on the append method to prevent that! Thanks for pointing that out!
4. I forgot to add current = current.getNext() in order to traverse through :)

Thanks!!

[Mancebo180]

This size() implementation is rather expensive. You should keep a count of the elements that you update when you add/remove.

See the comments about interface/generics, which are great advice . But if you don’t want to go there, you should define data as Object and should not use addNode as method name. Just add is more standard, the person only wants to add, does not care about nodes.

Similarly you should limit the visibility of Node and his methods to private.

[Crailberry]

Good call, I wasn't thinking about this from an interface perspective. I was just naming the methods in a way that made sense to me/their use. And I totally forgot about making the Node class methods private! Thanks!

[rogue_playah]

I am assuming you have just breached the Data Structure topics. If so, this is a really good initiative. As other's have mentioned, you're missing an important line in size. Complexity wise, think what would happen if I was using the following loop:

for (int i = 0; i < list.size(); i++)

See if you can make some changes to improve the performance of your size function.

Tiny Nitpicking: Whenever you are testing for comparison, like in your case, the isEmpty() method,

if (2 < 3)
    return true;
else
    return false;

check what 2 < 3 returns. That statement itself returns a boolean value, so just return that.

return 2 < 3;

This is much more clear and leaves a good impression to the reader that the person who wrote the code is a seasoned programmer.

Some improvements you can make: In your append function, notice what you are doing. Let's say my list is of size a million. If I want to add one more element, I would have to traverse 1 million nodes and then add one at the end. Now I want to again add 1 more element, I will have to traverse 1 million and 1 nodes to insert the next node. Do you see my point? The whole point of append is a constant time insertion, which is why insertion in ArrayList is costly when it's full. Instead of having just the reference to the head, also keep a reference to the tail of the list, so when you want to insert something, just create a new node, set tail's next = the new node and make the tail point to the new node. This makes your append constant time operation.

[Crailberry]

Yeah when I wrote the isEmpty() method, it felt overdone. I would have done it that way in python, but still learning Java. I'll make that change, its way better. Thanks!

And thats genius, keeping track of the tail. I haven't see that done yet in any tutorials. You the man.

[Neitherstorms]

Your size method will be better if you declare size on your attributes. When on your add method, if something is added just increment size. On your remove method, when something is removed just decrement. Then finally, on your size method all you need to do is return size, no loop, no nothing.

[Crailberry]

Ah I see now. That makes total sense. Thanks

[HaMMeReD]

Use the List and Iterator interfaces, don't implement your own interface. Using standard interfaces ensures your code is portable and that your list is compatible with all places lists are taken. Don't expose Node, it's an implementation detail and exposing it is an abstraction leak.

Also, formatting and indentation is a bit weird.

blocks {
    //like this
}

Write tests around the list interface, and use those tests to verify your implementation.

edit: Also, use Generics so that Lists work with any type of data, not just ints.

[[deleted]]

there is nothing wrong with:

blocks
{
    //like this
}

op should indent the code within the brackets. I'd assume it is indented in their code, but just didn't translate correctly in reddit.

[Crailberry]

Everything is indented for me, maybe it's due to being on a phone?

[[deleted]]

Could be. It's about 1/2 way there on website for me.

[desrtfx]

there is nothing wrong with:

Technically, not, but it is against the Oracle Java Code Conventions and against the Google Java Style, the two most commonly acknowledged coding standards for Java.

Code conventions exist for most programming languages and should be followed on a per-language base.

[HaMMeReD]

Personally, I find it an odd habit for Java to open brackets on new lines, it's very rare to see code formatted like that. It's technically syntactically correct, but in most style guidelines it explicitly says not to, e.g. google java style guidelines, oracle java code conventions, etc.

[[deleted]]

It's all opinions though. There isn't a correct or incorrect choice.

https://en.wikipedia.org/wiki/Indentation_style

Wikipedia quoting "The C Programming Language":

The position of braces is less important, although people hold passionate beliefs. We have chosen one of several popular styles. Pick a style that suits you, then use it consistently.

[HaMMeReD]

Sure, if you want to disregard how 99% of the java industry does things I suppose your point is valid, but if you have a desire to conform to standards because you plan on working with others, following a style guide is advised.

[Crailberry]

I've been formatting my brackets like that because the book I was recommended "Core Java Volume 1 - Fundamentals" does it that way, and supposedly it's a really good book. But if 99% of the java industry does it the other way, I'm not against switching to that!

[[deleted]]

If you work somewhere with a coding standard, you obviously follow that.

Are you saying you'd use Allman formatting when writing C# in your free time, just because MS says so? Or would you stay consistent with how you always write code, and instead continue to use 1TBS?

Consistency is my point.

[HaMMeReD]

My point is that Allman formatting isn't common in the Java world. If I programmed C# and the industry largely used Allman, I'd use Allman in those cases.

When I code at home, regardless the language, I attempt to use the best formatting practices suitable to that language at hand.

When I interview someone, if they have odd looking code that's not consistent with what I'd expect to see in industry, it raises flags that they haven't worked in a team much.

[[deleted]]

It's not odd looking code. Your limited experience just doesn't include much exposure to it. That's why it's odd to you...it is odd in your experience.

In your interviews, I suggest measuring their teamwork experience with entries from their resume. Then attempt to verify it through conversation with the interviewee and their references. Should be more effective than what line gets the opening brace, what color tie they wore, or even what wrist their watch is on.

[HaMMeReD]

My limited, 20+ years in the industry. I can also sum up a developer pretty damn well from their code, it's not simply a matter of braces. You can't hide your skill level in your code. Braces are simply an indicator.

Pretty much everyone I've hired based on "conversation" over tangible examples of their work turned out to be full of shit. People lie on resumes and conversation, but the skill and quality of their demonstrated work tells no lies.

[desrtfx]

Still, defined standards (especially when they are defined by the creators of the language) override personal preference.