aig aig - 3 months ago 16
Java Question

What is wrong with the implementation of my DoubleLinkedList?

I am currently learning Data Structures and Algorithm and one of the exercises was to implement a DoublyLinkedList from scratch. Unfortunately when i try to perform the "listDelete" operation on my list, my code works well for some integer values and not for some. It works fine when I try to delete 23, 45, 100, 5, 15. There is an Exception when i try to delete 400 from the list.

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

/**
* Created on 13-Aug-16.
*/
public class DoublyLinkedList<Item> implements Iterable<Item>{
private Node<Item> head ;

private class Node<Item>{
private Item key;
private Node<Item> prev;
private Node<Item> next;
}

public Node<Item> listSearch(Item key)
{
Node<Item> currentNode = head ;

while (currentNode != null && currentNode.key != key)
currentNode = currentNode.next ;

return currentNode ;
}

public void listInsert(Item item)
{
Node<Item> newNode = new Node<>(); //create an object of incoming item
newNode.next = head ;
newNode.prev = null ;
newNode.key = item ;

if (head != null)
head.prev = newNode ;

head = newNode;
}

public void listDelete(Item item){
Node<Item> nodeToDelete = listSearch(item);

if (nodeToDelete == null)
throw new NoSuchElementException("Cant find element");

if(nodeToDelete.prev != null)
nodeToDelete.prev.next = nodeToDelete.next ;
else
head = nodeToDelete.next;

if (nodeToDelete.next != null)
nodeToDelete.next.prev = nodeToDelete.prev ;
}

public Iterator<Item> iterator(){
return new DoublyLinkedListIterator();
}

private class DoublyLinkedListIterator implements Iterator<Item>{
private Node<Item> nextNode;

public DoublyLinkedListIterator(){
nextNode = head;
}

public boolean hasNext(){
return nextNode != null ;
}

public Item next(){
if (!hasNext())
throw new NoSuchElementException();

Item key = nextNode.key;

nextNode = nextNode.next ;

return key;
}

public void remove(){
throw new UnsupportedOperationException();
}
} //end of Iterator class

public String toString(){
StringBuilder sb = new StringBuilder();

for(Item item : this)
sb.append(item + ", ");

return sb.toString();
}

public static void main(String[] args) {
DoublyLinkedList<Integer> numbers = new DoublyLinkedList<>();

Random random = new Random();

numbers.listInsert(23);
for (int i=1; i <=5; i++)
numbers.listInsert(random.nextInt(100));
numbers.listInsert(45);
numbers.listInsert(100);
numbers.listInsert(400);
numbers.listInsert(5);

for (int i=1; i <=10; i++)
numbers.listInsert(random.nextInt(100));
numbers.listInsert(15);

System.out.println("Before");
System.out.println("LIST: " + numbers);

System.out.println("Deleting......................");
numbers.listDelete(100); //doesnot work for some set of integers
System.out.println("After");
System.out.println("LIST: " + numbers);
}
} //end of class

Answer

You are using generic data type (Item) here, so while comparing two elements you should use equals method rather than using reference (==)

public Node<Item> listSearch(Item key)
    {
        Node<Item> currentNode = head ;   
        while (currentNode != null && !currentNode.key.equals(key))
                currentNode = currentNode.next ;
        return currentNode ;
    }