current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite
1

Here is my insertion method for a doubly linked list. It works, but passing two parameters for the method seems cumbersome. Can anyone suggest a cleaner approach than this?

   LinkedList list = new LinkedList();
    Link link1 = new Link("A");
    list.insert(list.head,link1);
    Link link2 = new Link("B");
    list.insert(link1, link2);
    Link link3 = new Link("C");
    list.insert(link2, link3);
    list.display_List_Start_From_Head();

public void insert(Link currentNode, Link newNode)
    {
        if(head == null)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            currentNode.next = newNode;
            newNode.prev = currentNode;
            tail = newNode;
        }


    }
share|improve this question
1  
Tagged reinventing the wheel, because Java already has LinkedLists. –  Pimgd Apr 27 at 0:27

2 Answers 2

up vote 3 down vote accepted 
    if(head == null)
    {
        head = newNode;
        tail = newNode;
    }
    else
    {
        currentNode.next = newNode;
        newNode.prev = currentNode;
        tail = newNode;
    }

hmmm

    if(head == null)
    {
        head = newNode;
    }
    else
    {
        currentNode.next = newNode;
        newNode.prev = currentNode;
    }
    tail = newNode;

Yep, that's shorter.

Okay, and now a more serious answer:

A LinkedList, no matter if it's doubly linked or not, always is gonna require two things for insertAt: The object to insert, and some means of specifying where it goes. There's no way to circumvent this. Best you can do is take a Node (or Link, in your case) and give it an insertAfter method.

Oh yeah, back to your code example:

LinkedList list = new LinkedList();
Link link1 = new Link("A");
list.insert(list.head,link1);
Link link2 = new Link("B");
Link link3 = new Link("C");
list.insert(link2, link3);
list.insert(link1, link2);
list.display_List_Start_From_Head();

You have some serious bugs in there.

This should work fine, of course, but try iterating it backwards; you won't get the correct elements back.

Here's another way your list blows up:

LinkedList list = new LinkedList();
Link link1 = new Link("A");
list.insert(list.head,link1);
Link link2 = new Link("B");
list.insert(link1, null);//NullPointerException
list.insert(link1, link2);//If it didn't crash just now, this will clear the list and leave link2 as head
share|improve this answer
    
Okay I will fix the bug issue. You make a lot of great points about considering using a different parameter type for the method. I actually designed the method around having all the non-null link objects linked together. You gave me a lot of great perspective introducing a buggy scenario. –  Nicholas Apr 27 at 1:40
up vote 2 down vote

In general, and in Java in particular, exposing the Link instances to the outside world is considered to be bad practice.

Your 'users' should not have a 'Link' to insert after, or a Link to insert. They should have a value to insert, and a location at which to insert it, and with those values, you should locate the insertion-point Link, and create a new Link to add.

The Link should be private.

What you have is a classic strategy from C-like languages which do not have object orientation or encapsulation.

This is also in part why Java has Generics, because it makes this system easier to work with.

Bottom line, is that your method should look more like:

public class LinkedList<T> {

    ....

    public void insert(T before, T toInsert) {
        Link<T> beforeLink = locateLink(before);
        Link<T> toAdd = new Link<>(toInsert);
        .....
        // insert the toAdd link before the beforeLink
        .....    
    }

}

@Pimgd has given good advice already about how you should improve that inner process alread.

share|improve this answer
    
Making the Link private leads to less shenanigans which blow things up too, so that's a nice bonus. –  Pimgd Apr 27 at 0:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.