Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java Linked List - add method

Data structures class, implementing a singly linked-list with head, tail and current nodes. Having trouble with a method, could use a nudge in the right direction.

From the assignment, write the method:

add( item ) : adds the item (String) after the current node in the list and sets the current pointer to refer to the new node.

My attempt:

public void add(String item)
{
    if(curr != null)
    {
        Node newNode = new Node(item, curr.next);
        curr.next = newNode;
        curr = newNode;
    }
    else
    {
        head = tail = new Node(item, null);
        curr = head;
    }
}

My add method only seems to work when I'm adding items to the middle of the list, not on either end. If I use it to add a few items and then print the list, only the first one I added will be on the list, while my prepend and append methods have tested just fine.

Is there any glaring issue with my code? I feel like I'm missing something obvious.

All:

public class LinkedList {
    Node head = null; /* Head of the list */
    Node tail = null; /* Tail of the list */
    Node curr = null; /* Current node in the list */

    public void prepend(String item) {
        if (head == null) {
            head = tail = new Node(item, null);
            curr = head;
        } else {
            head = new Node(item, head);
            curr = head;
        }
    }

    public void append(String item) {
        if (head == null) {
            head = tail = new Node(item, null);
            curr = tail;
        } else {
            tail.next = new Node(item, null);
            tail = tail.next;
            curr = tail;
        }
    }

    public void add(String item) {
        if (curr != null) {
            Node newNode = new Node(item, curr.next);
            curr.next = newNode;
            curr = newNode;
        } else {
            head = tail = new Node(item, null);
            curr = head;
        }
    }

    public void delete() {
        if (curr.next == null) {
            Node temp = head;
            while (temp.next != curr) {
                System.out.println(temp.item);
                temp = temp.next;
            }
            temp.next = null;
            curr = head;
        }
    }

    public void find(String item) {
        Node temp = new Node(curr.item, curr.next);
        if (item.equals(temp.item))
            curr = temp;
        else {
            temp = temp.next;
            while (temp.next != null && temp != curr) {
                if (item.equals(temp.item))
                    curr = temp;
            }
        }
    }

    public String get() {
        if (curr != null)
            return curr.item;
        else
            return "";
    }

    public boolean next() {
        if (curr != tail) {
            curr = curr.next;
            return true;
        } else
            return false;
    }

    public void start() {
        curr = head;
    }

    public void end() {
        curr = tail;
    }

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

Node class:

class Node {
    Node next;
    String item;

    Node(String item, Node next) {
        this.next = next;
        this.item = item;
    }
}
like image 989
dysania Avatar asked Jan 16 '12 19:01

dysania


People also ask

How GET method works in LinkedList in Java?

LinkedList get() Method in Java LinkedList. get() method is used to fetch or retrieve an element at a specific index from a LinkedList. Parameters: The parameter index is of integer data type that specifies the position or index of the element to be fetched from the LinkedList.

Which method is used to add an element at the end of the LinkedList?

Elements can be added at the end of a LinkedList by using the method java. util. LinkedList. addLast().


1 Answers

There is indeed a problem in add: it doesn't update tail when nodes already exist. Consider this sequence of actions:

LinkedList list = new LinkedList(); 
list.add("one");
list.add("two");
list.append("three");

If you were to then print it using this:

public void print() {
    Node curr = this.head;
    while(curr != null) {
        System.out.println(curr.item);
        curr = curr.next;
    }
}

Like this:

list.print();

You'd get the following output:

one
three

This happens because tail -- which append relies on -- continues to point to the first Node after the second add operation is performed.

like image 74
Wayne Avatar answered Sep 28 '22 08:09

Wayne