// Linked List Class public class LinkedList<T> { private Node<T> head; // head
ID: 671119 • Letter: #
Question
// Linked List Class
public class LinkedList<T>
{
private Node<T> head; // head of the list always at the front
private Node<T> cursor; // cursor that moves along the one way list
// constructor
public LinkedList ()
{
// the first node is not used, dummy node
// so we're always dealing with the element to the right of
// the cursor not what the cursor is pointing to.
head = new Node<T>(null, null);
cursor = head;
}
// if the cursor's next is null, then we're at the end
public boolean isAtEnd()
{
return(cursor.getNext() == null);
}
// move the cursor to the beginning of the list
public void reset()
{
cursor = head;
}
// advance the cursor one spot to the right
public void advance()
{
cursor = cursor.getNext();
}
// return the node to the right of the cursor
public Node<T> getCurrent()
{
return cursor.getNext();
}
// return the first node in the list
public Node<T> getFirst()
{
return head.getNext();
}
// insert at the beginning of the list, this insert is done to the
// right of the dummy node, but to the left of the first meaningful
// node.
public void listHeadInsert(T value)
{
head.setNext(new Node<T>(value, head.getNext()));
}
// wherever the cursor is, insert to the right of it, and move the
// cursor to point to the newly inserted node
// you may remove the line that advances the cursor, but you need
// to make sure that you advance the cursor when inserting elements
// at the end of the list one after another.
public void listInsert(T value)
{
// insert to the right of the cursor
cursor.setNext(new Node<T>(value, cursor.getNext()));
cursor = cursor.getNext();
}
// move the cursor to the head of the list, and keep moving it
// looking for the value, stop if you either find the value
// or you have reached the end of the list without finding it.
// return the node that contains the given value back to me.
// this return will return null if the value is not found.
public Node<T> listSearch(T value)
{
cursor = head;
while(cursor.getNext() != null &&
!cursor.getNext().getValue().equals(value))
cursor = cursor.getNext();
return cursor.getNext();
}
// first search (first 4 lines of the code)
// if you find it (not null) then just remove it by making the
// cursor's next pointer point to the node next to it's next
// pointer (skip a node)
public void listRemove(T value)
{
cursor = head;
while(cursor.getNext() != null &&
!cursor.getNext().getValue().equals(value))
cursor = cursor.getNext();
if(cursor.getNext() != null)
{
cursor.setNext(cursor.getNext().getNext());
}
}
// don't search, just remove the node to the right of the cursor
// if it's not null.
public void listRemoveCurrent()
{
if(cursor.getNext() != null)
{
cursor.setNext(cursor.getNext().getNext());
}
}
}
--------------------------------------------------------
public class ListDriver
{
public static void main(String [] args)
{
LinkedList<Integer> l = new LinkedList<Integer>();
// LinkedList<Integer> l2 = new LinkedList<Integer>();
int i;
for(i = 0; i < 4; i++)
l.listInsert(new Integer(i+3));
System.out.println("After the first for loop (3,4,5,6)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.listHeadInsert(new Integer(500));
System.out.println("After the head insert(500,3,4,5,6)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.listRemove(new Integer(5));
System.out.println("After the remove (500,3,4,6)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
while(!l.isAtEnd())
l.advance();
for(i = 1; i < 4; i++)
l.listInsert(new Integer(i*100));
System.out.println("After the inserting (100,200,300) at the end");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.reset();
if(l.listSearch(new Integer(200)) != null){
System.out.println(" Searched and found the 200");
System.out.println("--------------------------- ");
}
l.listInsert(new Integer(150));
System.out.println("After the inserting 150 before the 200");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
/*
l2.listInsert(new Integer(500));
l2.listInsert(new Integer(7));
l2.listInsert(new Integer(9));
l2.listInsert(new Integer(200));
l2.listInsert(new Integer(301));
l.addList(l2);
System.out.println("After the inserting list 2 (500,7,9,200,301)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l2.listRemove(new Integer(9));
l2.listRemove(new Integer(200));
l.subtractList(l2);
System.out.println("After removing list 2 (500,7,301)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.reverseList();
System.out.println("After reversing the list");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
*/
}
}
--------------------------------------------
// Node of any Reference type T
public class Node<T>
{
private T value; // this is the data value
private Node<T> next; // this is pointing to the next node
// the node constructor
public Node (T v, Node<T> n)
{
value = v;
next = n;
}
// getters and setters for the node's value and next pointer
public T getValue() {return value;}
public Node<T> getNext() {return next;}
public void setValue(T v){value = v;}
public void setNext(Node<T> n){next = n;}
}
Explanation / Answer
Answer:
The added methods are highlighted in bold letters.
Program code to copy:
// Node of any Reference type T
public class Node<T>
{
private T value; // this is the data value
private Node<T> next; // this is pointing to the next node
// the node constructor
public Node(T v, Node<T> n)
{
value = v;
next = n;
}
// getters and setters for the node's value and next pointer
public T getValue()
{
return value;
}
public Node<T> getNext()
{
return next;
}
public void setValue(T v)
{
value = v;
}
public void setNext(Node<T> n)
{
next = n;
}
}
// Linked List Class
public class LinkedList<T>
{
private Node<T> head; // head of the list always at the front
private Node<T> cursor; // cursor that moves along the one way list
// constructor
public LinkedList()
{
// the first node is not used, dummy node
// so we're always dealing with the element to the right of
// the cursor not what the cursor is pointing to.
head = new Node<T>(null, null);
cursor = head;
}
// if the cursor's next is null, then we're at the end
public boolean isAtEnd()
{
return (cursor.getNext() == null);
}
// move the cursor to the beginning of the list
public void reset()
{
cursor = head;
}
// advance the cursor one spot to the right
public void advance()
{
cursor = cursor.getNext();
}
// return the node to the right of the cursor
public Node<T> getCurrent()
{
return cursor.getNext();
}
// return the first node in the list
public Node<T> getFirst()
{
return head.getNext();
}
// insert at the beginning of the list, this insert is done to the
// right of the dummy node, but to the left of the first meaningful
// node.
public void listHeadInsert(T value)
{
head.setNext(new Node<T>(value, head.getNext()));
}
// wherever the cursor is, insert to the right of it, and move the
// cursor to point to the newly inserted node
// you may remove the line that advances the cursor, but you need
// to make sure that you advance the cursor when inserting elements
// at the end of the list one after another.
public void listInsert(T value)
{
// insert to the right of the cursor
cursor.setNext(new Node<T>(value, cursor.getNext()));
cursor = cursor.getNext();
}
// move the cursor to the head of the list, and keep moving it
// looking for the value, stop if you either find the value
// or you have reached the end of the list without finding it.
// return the node that contains the given value back to me.
// this return will return null if the value is not found.
public Node<T> listSearch(T value)
{
cursor = head;
while (cursor.getNext() != null
&& !cursor.getNext().getValue().equals(value))
cursor = cursor.getNext();
return cursor.getNext();
}
// first search (first 4 lines of the code)
// if you find it (not null) then just remove it by making the
// cursor's next pointer point to the node next to it's next
// pointer (skip a node)
public void listRemove(T value)
{
cursor = head;
while (cursor.getNext() != null
&& !cursor.getNext().getValue().equals(value))
cursor = cursor.getNext();
if (cursor.getNext() != null)
{
cursor.setNext(cursor.getNext().getNext());
}
}
// don't search, just remove the node to the right of the cursor
// if it's not null.
public void listRemoveCurrent()
{
if (cursor.getNext() != null)
{
cursor.setNext(cursor.getNext().getNext());
}
}
// addList()
public void addList(LinkedList<T> second)
{
Node<T> secTemp = second.getFirst();
Node<T> search;
while (secTemp != null)
{
search = listSearch(secTemp.getValue());
if (search == null)
this.listInsert(secTemp.getValue());
else
secTemp = secTemp.getNext();
}
}
// subtractList() method
public void subtractList(LinkedList<T> second)
{
Node<T> secTemp = second.getFirst();
Node<T> search;
while (secTemp != null)
{
search = listSearch(secTemp.getValue());
if (search != null)
{
listRemove(secTemp.getValue());
}
else
secTemp = secTemp.getNext();
}
}
// reverseList() method
public void reverseList()
{
Node<T> reverse = null;
Node<T> present = head;
Node<T> newNext = null;
while (present != null)
{
newNext = present.getNext();
present.setNext(reverse);
reverse = present;
present = newNext;
}
head = reverse;
}
}
public class ListDriver
{
public static void main(String[] args)
{
LinkedList<Integer> l = new LinkedList<Integer>();
LinkedList<Integer> l2 = new LinkedList<Integer>();
int i;
for (i = 0; i < 4; i++)
l.listInsert(new Integer(i + 3));
System.out.println("After the first for loop (3,4,5,6)");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.listHeadInsert(new Integer(500));
System.out.println("After the head insert(500,3,4,5,6)");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.listRemove(new Integer(5));
System.out.println("After the remove (500,3,4,6)");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
while (!l.isAtEnd())
l.advance();
for (i = 1; i < 4; i++)
l.listInsert(new Integer(i * 100));
System.out.println("After the inserting (100,200,300) at the end");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.reset();
if (l.listSearch(new Integer(200)) != null)
{
System.out.println(" Searched and found the 200");
System.out.println("--------------------------- ");
}
l.listInsert(new Integer(150));
System.out.println("After the inserting 150 before the 200");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l2.listInsert(new Integer(500));
l2.listInsert(new Integer(7));
l2.listInsert(new Integer(9));
l2.listInsert(new Integer(200));
l2.listInsert(new Integer(301));
l.addList(l2);
System.out.println("After the inserting list 2 (500,7,9,200,301)");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l2.listRemove(new Integer(9));
l2.listRemove(new Integer(200));
l.subtractList(l2);
System.out.println("After removing list 2 (500,7,301)");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.reverseList();
System.out.println("After reversing the list");
System.out.println("----------------------------------");
l.reset();
while (!l.isAtEnd())
{
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
}
}
Sample output:
After the first for loop (3,4,5,6)
----------------------------------
3
4
5
6
After the head insert(500,3,4,5,6)
----------------------------------
500
3
4
5
6
After the remove (500,3,4,6)
----------------------------------
500
3
4
6
After the inserting (100,200,300) at the end
----------------------------------
500
3
4
6
100
200
300
Searched and found the 200
---------------------------
After the inserting 150 before the 200
----------------------------------
500
3
4
6
100
150
200
300
After the inserting list 2 (500,7,9,200,301)
----------------------------------
500
3
4
6
100
150
200
300
7
9
301
After removing list 2 (500,7,301)
----------------------------------
3
4
6
100
150
200
300
9
After reversing the list
----------------------------------
300
200
150
100
6
4
3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.