Skip to content

anonymous /LinkedList.java secret

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
linkedlist
// A linked list is a sequence of nodes with efficient
// element insertion and removal.
// This class contains a subset of the methods of the
// standard java.util.LinkedList class.
import java.util.NoSuchElementException;
public class LinkedList
{
private int count;
//nested class to represent a node
private class Node
{
public Object data;
public Node next;
}
//only instance variable that points to the first node.
private Node first;
// Constructs an empty linked list.
public LinkedList()
{
first = null;
count = 0;
}
// Returns the first element in the linked list.
public Object getFirst()
{
if (first == null)
{
NoSuchElementException ex
= new NoSuchElementException();
throw ex;
}
else
return first.data;
}
// Removes the first element in the linked list.
public Object removeFirst()
{
if (first == null)
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
{
Object element = first.data;
first = first.next; //change the reference since it's removed.
return element;
}
}
// Adds an element to the front of the linked list.
public void addFirst(Object element)
{
//create a new node
Node newNode = new Node();
newNode.data = element;
newNode.next = first;
//change the first reference to the new node.
first = newNode;
count++;
}
// Returns an iterator for iterating through this list.
public ListIterator listIterator()
{
return new LinkedListIterator();
}
public String toString()
{
String toString = "";
while(first != null) {
for (int i = 0; i < count; i++ )
{
toString += "{" + first.next.data + "}" ;
first.next = first.next.next;
}
}
return toString;
}
public boolean isEmpty()
{
boolean flag = true;
if (count == 0)
{
flag = true;
}
else
{
flag = false;
}
return flag;
}
public void addElement(int index, Object element)
{
Node newNode = new Node();
newNode.data = element;
Node current = new Node();
for (int i = 1; i < index && first.next != null; i++)
{
current.next= first.next;
}
newNode.next = current.next;
current.next = newNode;
count++;
}
public void setElement(int index, Object element)
{
Node current = new Node();
current = first;
for (int i = 1; i < index; i++)
{
current = first.next;
}
}
/*********************************************************
Add your methods here
*********************************************************/
//nested class to define its iterator
private class LinkedListIterator implements ListIterator
{
private Node position; //current position
private Node previous; //it is used for remove() method
// Constructs an iterator that points to the front
// of the linked list.
public LinkedListIterator()
{
position = null;
previous = null;
}
// Tests if there is an element after the iterator position.
public boolean hasNext()
{
if (position == null) //not traversed yet
{
if (first != null)
return true;
else
return false;
}
else
{
if (position.next != null)
return true;
else
return false;
}
}
// Moves the iterator past the next element, and returns
// the traversed element's data.
public Object next()
{
if (!hasNext())
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
{
previous = position; // Remember for remove
if (position == null)
position = first;
else
position = position.next;
return position.data;
}
}
// Adds an element before the iterator position
// and moves the iterator past the inserted element.
public void add(Object element)
{
if (position == null) //never traversed yet
{
addFirst(element);
position = first;
}
else
{
//making a new node to add
Node newNode = new Node();
newNode.data = element;
newNode.next = position.next;
//change the link to insert the new node
position.next = newNode;
//move the position forward to the new node
position = newNode;
}
//this means that we cannot call remove() right after add()
previous = position;
}
// Removes the last traversed element. This method may
// only be called after a call to the next() method.
public void remove()
{
if (previous == position) //not after next() is called
{
IllegalStateException ex = new IllegalStateException();
throw ex;
}
else
{
if (position == first)
{
removeFirst();
}
else
{
previous.next = position.next; //removing
}
//stepping back
//this also means that remove() cannot be called twice in a row.
position = previous;
}
}
// Sets the last traversed element to a different value.
public void set(Object element)
{
if (position == null)
{
NoSuchElementException ex = new NoSuchElementException();
throw ex;
}
else
position.data = element;
}
} //end of LinkedListIterator class
} //end of LinkedList class
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.