public class DoublyLinkedList<ValueType> implements List<ValueType> { private No
ID: 3740335 • Letter: P
Question
public class DoublyLinkedList<ValueType> implements List<ValueType> {
private Node head;
private Node tail;
private int size;
public DoublyLinkedList() {
//create an empty list
//since head and tail are sentinels, we have to create them
head = new Node(null);
tail = new Node(null);
// note ValueType os always a reference type
//in Java, this means that ValueType is descendant of Object
//these two point to each other
head.setNext(tail);
tail.setPrev(head);
//set size to zero
size =0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return (size == 0);
}
@Override
public int size() {
// TODO Auto-generated method stub
return size;
}
private void addBetween(ValueType value, Node pred, Node succ)
{
//1) Make a new node containing the value, between pred and succ
Node newNode = new Node(value, pred, succ);
//1)Linl the nodes in the list to this new node
pred.setNext(newNode);
succ.setPrev(newNode);
//3) Update size variable
size++;
}
@Override
public void addToFront(ValueType value) {
// TODO Auto-generated method stub
addBetween(value, head, head.getNext());
}
@Override
public void addToBack(ValueType value) {
addBetween (value, tail.getPrev(), tail);
}
///removal methods
private ValueType removeNode (Node n)
{
//we just need to updates n's predecessor to point to n's successor and vice versa
Node prev = n.getPrev();
Node next = n.getNext();
prev.setNext(next);
next.setNext(prev);
//decrement the size
size--;
return n.getValue();
}
@Override
public ValueType removeFront() {
if (isEmpty())
{
throw new IllegalStateException("Cannot Remove From an Empty List");
}
return removeNode(head.getNext());
}
@Override
public ValueType removeBack() {
if (isEmpty())
{
throw new IllegalStateException("Cannot Remove From an Empty List");
}
return removeNode(tail.getPrev());
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("(Size = " + size + ")");
//walk through the list, append all values
for (Node tmp = head.getNext(); tmp != tail ;tmp = tmp.getNext())
{
sb.append(" " + tmp.getValue());
}
return sb.toString();
}
//private inner class
private class Node{
//private variables
private ValueType value; // the value
private Node next; // reference to next node
private Node prev; // reference to previous node
//constructors
public Node(ValueType value,Node prev, Node next)
{
this.value = value;
this.next = next;
this.prev = prev;
}
public Node(ValueType value)
{
this(value, null, null);
}
//getters and setters
public ValueType getValue() {
return value;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public void setValue(ValueType value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}
-----------------------------------------------------------------------------------------------
Explanation / Answer
import java.util.Scanner;
class DoublyLinkedList<ValueType> implements List<ValueType> {
private Node head;
private Node cursor;
private int size;
public DoublyLinkedList() {
//create an empty list
//since head and tail are sentinels, we have to create them
cursor = new Node(null);
head = cursor;
// note ValueType os always a reference type
//in Java, this means that ValueType is descendant of Object
//these two point to each other
cursor.setNext(null);
cursor.setPrev(null);
//set size to zero
size = 0;
}
public boolean isEmpty() {
// TODO Auto-generated method stub
return (size == 0);
}
public int size() {
// TODO Auto-generated method stub
return size;
}
public void addAfterCursor(ValueType value)
{
if(isEmpty())
{
Node newNode = new Node(value, null, null);
cursor = newNode;
head = cursor;
size++;
}
else
{
Node newNode = new Node(value, cursor, head);
cursor.setNext(newNode);
head.setPrev(newNode);
cursor = newNode;
size++;
}
}
public ValueType deleteCursor() {
if (isEmpty())
{
throw new IllegalStateException("Cannot Remove From an Empty List");
}
ValueType vv = cursor.getValue();
Node prev = cursor.getPrev();
Node next = cursor.getNext();
prev.setNext(next);
next.setPrev(prev);
cursor = cursor.getNext();
size--;
return vv;
}
public void advanceCursor(int n) {
if(!isEmpty())
{
for(int i=0; i<n;i++)
{
cursor = cursor.getNext();
}
}
}
public ValueType getValue() {
if (isEmpty())
{
throw new IllegalStateException("Cannot Get Value From an Empty List");
}
return cursor.getValue();
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("(Size = " + size + ")");
//walk through the list, append all values
for (Node tmp = head; tmp != cursor ;tmp = tmp.getNext())
{
sb.append(" " + tmp.getValue());
}
return sb.toString();
}
//private inner class
private class Node{
//private variables
private ValueType value; // the value
private Node next; // reference to next node
private Node prev; // reference to previous node
//constructors
public Node(ValueType value,Node prev, Node next)
{
this.value = value;
this.next = next;
this.prev = prev;
}
public Node(ValueType value)
{
this(value, null, null);
}
//getters and setters
public ValueType getValue() {
return value;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public void setValue(ValueType value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}
public class CircularDoublyLinkedList {
public static void main(String[] args) {
DoublyLinkedList<Integer> dll = new DoublyLinkedList();
System.out.println("1:Insert");
System.out.println("2:Delete");
System.out.println("3:Move cursor");
System.out.println("4:Get value at Cursor");
System.out.println("5:Exit");
Scanner sc = new Scanner(System.in);
int input = sc.nextInt();
while(input != 5)
{
switch(input)
{
case 1:
System.out.println("Enter value to insert");
int n = sc.nextInt();
dll.addAfterCursor(n);
break;
case 2:
System.out.println(dll.deleteCursor() + "deleted from list");
break;
case 3:
System.out.println("Enter movement");
int m = sc.nextInt();
dll.advanceCursor(m);
break;
case 4:
System.out.println("Value at cursor is " + dll.getValue());
break;
default:
System.out.println("Wrong choice");
break;
}
System.out.println("1:Insert");
System.out.println("2:Delete");
System.out.println("3:Move cursor");
System.out.println("4:Get value at Cursor");
System.out.println("5:Exit");
input = sc.nextInt();
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.