0

I am learning data structures current and below is my implementation for linkedlist.I have kept it as simple as possible as my aim here is to understand the logic.

/*
 * Singly linked list
 */
package linkedlisttest;


class Node {
    int data;
    Node next;

    public Node(int data) 
    {
        this.data = data;
    }

}

class LinkedList {

    Node head;

    public void add(int data) 
    {
        if (head == null) 
        {
            head = new Node(data);  
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    public int getSize() {
        int i = 0;
        Node current = head;
        while (current != null) {
            i += 1;
            current = current.next;
        }
        return i;
    }

    public void add(int data, int index) 
    {
        if (head == null && index == 0) 
        {
              head = new Node(data);
              return;
        } else if (head == null && index != 0) {
              return; // invalid position
        } else if ( index > getSize() ) {
            return;
        }

        Node current = head;
        //iterate through whole list 
        int pos = -1; 
        Node previous = null;
        Node next = null;
        Node newNode = new Node(data);
        //find next and previous nodes with relation to position
        while (current != null) {
            if (pos == index - 1) {
                previous = current;
            } else if (pos == index + 1) {
                next = current;
            }
            pos++;
            current = current.next;
        }
        previous.next = newNode;

        newNode.next = next;

    }

    public void print() 
    {
        Node current = head;
        while (current.next != null) {
            System.out.print(current.data + "->");
            current = current.next;
        }
        System.out.print(current.data);
    }

}

public class LinkedListTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList lt = new LinkedList();
        lt.add(3);
        lt.add(5);
        lt.add(6);
        lt.add(4,1);
        lt.print();
    }

}

The bug happens for lt.add(4,1) and i suspect its an off by one error.

Expected output: 3->4->6

Actual output: 3->5->4

Thanks for the help guys...

Edit

Thanks to @StephenP and @rosemilk for their help.Indeed the code above has a logical bug as it replaces the value at index and not add it.

Here is the new optimized code

/*
 * Singly linked list
 */
package linkedlisttest;

class Node {

    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }

}

class LinkedList {

    Node head;
    int size;

    /**
     *
     * @param data element to add to list 
     * Time Complexity : O(n)
     */
    public void add(int data) {
        if (head == null) {
            head = new Node(data);
            size += 1;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
        size += 1;
    }

    /**
     *
     * @return size of list 
     * Time Complexity: O(1) 
     * This is because we use a class
     * variable size to keep track of size of linked list
     */
    public int getSize() {
        return size;
    }
    /**
     * 
     * @param data element to insert 
     * @param index position at which to insert the element (zero based)
     * Time Complexity : O(n)
     */
    public void add(int data, int index) {

        if (index > getSize()) {
            return; // invalid position
        }

        Node current = head; //iterate through whole list 
        int pos = 0;
        Node newNode = new Node(data);

        if (index == 0) // special case, since its a single reference change!
        {
            newNode.next = head;
            head = newNode; // this node is now the head
            size += 1;
            return;
        }
        while (current.next != null) {
            if (pos == index - 1) {
                break;
            }
            pos++;
            current = current.next;
        }
        // These are 2 reference changes, as compared to adding at index 0
        newNode.next = current.next; // here we are changing a refernce
        current.next = newNode; // changing a reference here as well
        size += 1;

    }

    /**
     * Prints the whole linked list 
     * Time Complexity : O(n)
     */
    public void print() {

        if(getSize() == 0) { //list is empty
            return;
        }
        Node current = head;
        while (current.next != null) {
            System.out.print(current.data + "->");
            current = current.next;
        }
        System.out.print(current.data + "\n"); 
    }
}

public class LinkedListTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LinkedList lt = new LinkedList();
        lt.print();
        lt.add(3);
        lt.add(5);
        lt.add(6);
        lt.print();
        lt.add(4, 1);
        lt.print();
        lt.add(4, 7);// 7 is an invalid index
        lt.add(8, 3);
        lt.print();
    }

}
6
  • Go through your add method with pen and paper and mark down expected vs actual for each variable at each line Commented Jul 21, 2017 at 18:14
  • Shouldn't the expected output be 3->4->5->6? add(n,i) should add the value n at position i, not replace the current value at position i Commented Jul 21, 2017 at 18:14
  • When you've figured out and understand why your add(int, int) method isn't working as you want, afterward consider (as an exercise because you're learning) how/if you could improve your design if your class LinkedList had members Node head; Node tail; int size; that it maintained when adding & removing nodes. Commented Jul 21, 2017 at 23:02
  • @Stephen P you are right ....i did a design mistake.This method should be called replace Commented Jul 22, 2017 at 5:41
  • @StephenP if i use a node for the tail. it will make it a doubly linked list.I am trying to keep it a singly linked list Commented Jul 22, 2017 at 5:43

2 Answers 2

2

Your add (int , int ) function has a logical bug and can be made better. You don't need previous current and next references, and can cleverly manipulate the list using just the reference to current node, handling inseration at index 0 separately. I would write the add function as follows

public void add(int data, int index) 
{
    if ( index > getSize() ) {
        return; // invalid position
    }

    Node current = head; //iterate through whole list 
    int pos = 0; 
    Node newNode = new Node(data);

    if (index == 0) // special case, since its a single reference change!
    {
        newNode.next = head; 
        head = newNode; // this node is now the head
        return;
    }
    while (current.next != null) {
        if (pos == index - 1) {
            break;
        }
        pos++;
        current = current.next;
    }
    // These are 2 reference changes, as compared to adding at index 0
    newNode.next = current.next; // here we are changing a refernce
    current.next = newNode; // changing a reference here as well

}

Also, your print function gives a NullPointerException when you try to print an empty list. I would write the print function like this,

public void print() 
{
    Node current = head;
    while (current != null) {
        System.out.print(current.data + "->");
        current = current.next;
    }
    System.out.println("null"); // this is just to say last node next points to null!
}

Hope this helps :)

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

2 Comments

Nice code, and inserts as I proposed (3->4->5->6) and is O(n) where the OP's is O(n^2) because it calls getSize() which itself has to traverse the entire list.
@StephenP and rosemilk thanks a lot for your help.Check the edit and let me know what you think
0

Currently, if you print out pos in your loop, the indices are -1, 0, 1 (instead of 0, 1, 2), so it'll never "find" the correct next. Replace int pos = -1; with int pos = 0; and it'll work.

I do agree with @StephenP that the output should (arguably) be 3->4->5->6, but that's a design decision.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.