Skip to main content

Linked List Trouble

1 reply [Last post]
caseysimplified
Offline
Joined: 2008-02-21

Hello everyone. This is my first post so please bare with me if I don't follow all the correct procedures.

I am also some what of a newbie at Java. I am a senior in high school and I am in my third Java class but we have just started learning about Linked Lists so my knowledge on them is limited.

I am supposed to make a Linked List class, List Iterator interface, and Linked List Tester class all from scratch without using any part of the already made Linked List and List Iterator class. I am also supposed to create and add most of the methods you would use in a Linked List like removeFirst(), getLast(), currentSize(), etc.

I am able to make all the methods except for the that have to do with adding, removing and displaying the last object in the list.

If someone could help me be able to do these things to my project I'd be very thankful.

I hope I gave enough information for you guys to understand. If you don't please let me know what I can do to help you better understand what I mean. Thanks!

Casey

/**
Casey Holgado
Computer Science 4
Period 2
02/19/08
*/
public interface ListIterator
{
Object next();
Object previous();
boolean hasNext();
boolean hasBefore();
void add(Object element);
void remove();
void set(Object element);
}

/**
Casey Holgado
Computer Science 4
Period 2
02/19/08
*/
import java.util.*;
public class LinkedListTester
{
public static void main()
{
LinkedList list = new LinkedList();
ListIterator itr = list.listIterator();
itr.add("Casey");
itr.add("Sbaa");
itr.add("Bob");
itr.add("Mike");
itr.add("Tim");
list.addFirst("Joe");
list.addLast("Steve");

System.out.println("currentSize: " + list.currentSize());
System.out.println("getFirst: " + list.getFirst());
System.out.println("getLast: " + list.getLast());
System.out.println("removeFirst: " + list.removeFirst());
System.out.println("removeFirst: " + list.removeFirst());

//commented out because they dont work
//System.out.println("removeLast: " + list.removeLast());
//System.out.println("removeLast: " + list.removeLast());

System.out.println("getCurrentSize: " + list.currentSize());
System.out.println("getFirst: " + list.getFirst());

//commented out because they dont work
//System.out.println("getLast: " + list.getLast());
}
}

/**
Casey Holgado
Computer Science 4
Period 2
02/19/08
*/
import java.util.*;
public class LinkedList {

public LinkedList()
{
first = null;
last = null;
}

public Object getFirst()
{
if (first == null)
throw new NoSuchElementException();
return first.data;
}

public Object getLast()
{
if (last == null)
throw new NoSuchElementException();
return last.data;
}

public Object removeFirst()
{
if (first == null)
throw new NoSuchElementException();
Object element = first.data;
first = first.next;
currentSize--;
return element;
}

public Object removeLast()
{
if (last == null)
throw new NoSuchElementException();
Object element = last.data;
last = last.previous;
currentSize--;
return element;
}

public void addFirst(Object element)
{
Node newNode = new Node();
newNode.data = element;
newNode.next = first;
first = newNode;
currentSize++;
}

public void addLast(Object element)
{
Node newNode = new Node();
newNode.data = element;
newNode.next = last;
last = newNode;
currentSize++;
}

public int currentSize()
{
return currentSize;
}

public ListIterator listIterator()
{
return new LinkedListIterator();
}

private Node last;
private Node first;
private int currentSize = 0;

private class Node
{
public Object data;
public Node next;
public Node previous;
}

private class LinkedListIterator implements ListIterator
{
public LinkedListIterator()
{
position = null;
previous = null;
next = null;
}

public Object next()
{
if (!hasNext())
throw new NoSuchElementException();
previous = position;

if (position == null)
position = first;
else
position = position.next;

return position.data;
}

public Object previous()
{
if (!hasBefore())
throw new NoSuchElementException();
next = position;

if (position == null)
position = first;
else
position = position.previous;

return position.data;
}

public boolean hasNext()
{
if (position == null)
return first != null;
else
return position.next != null;
}

public boolean hasBefore()
{
if (position == null)
return last != null;
else
return position.previous != null;
}

public void add(Object element)
{
if (position == null)
{
addFirst(element);
position = first;

}
else
{
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
position.next = newNode;
position = newNode;
currentSize++;
}
previous = position;
}

public void remove()
{
if (previous == position)
throw new IllegalStateException();

if (position == first)
{
removeFirst();
}
else
{
previous.next = position.next;
currentSize--;
}
position = previous;
}

public void set(Object element)
{
if (position == null)
throw new NoSuchElementException();
position.data = element;
}

private Node next;
private Node position;
private Node previous;
}
}

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
tarbo
Offline
Joined: 2006-12-18

Casey,

This appears to be a copy-paste issue.

[code]public void addLast(Object element)
{
Node newNode = new Node();
newNode.data = element;
newNode.next = last; // << should be newNode.previous
last = newNode;
currentSize++;
}[/code]

You may also want to be careful with your removeFirst and removeLast methods. Check whether you are removing the last element there -- if so, you will need to null both [i]first[/i] and [i]last[/i], or one of them will keep pointing to the removed node. Just so you don't run into other nasty surprises. ;)

Good luck with your assignment,
Jonathan