Question

The MyLinkedList class is a one-way directional linked list that enables one-way traversal of the list. Modify the Node class to add the new field name previous to refer to the previous node in the list, as follows:

    public class Node {

      E element;

Node next;

      Node previous;

      public Node(E o) {

        element = o;

      }

    }

Implement a new class named MyTwoWayLinkedList that uses a doubly linked list to store elements.

Hint. The MyLinkedList class in the text extends MyAbstractList. You may define MyTwoWayLinkedList to extend the java.util.AbstractSequentialList class. You need to implement the methods listIterator() and listIterator(int index). Both return an instance of java.util.ListIterator. The former sets the cursor to the head of the list and the latter to the element at the specified index.

Answer 1

Program Plan:

• Create class doublyLinkedList.

• Create a static inner class TwoWayLinkedList, which inherits from AbstractSequentialList class, inside the doublyLinkedList class.

• Create an object myList of type TwoWayLinkedList.

• Add elements in the list myList by calling methods add(), addFirst() and addLast().

• Remove elements from the list myList by calling methods remove(), removeFirst() and removeLast().

• Create an object myIterator of type ListIterator and initialize it with the value returned on calling iterator() method of myList.

• Traverse the list myList from beginning to end and then vice versa.

• In static inner class TwoWayLinkedList:

• Create a private inner class LinkedListIterator which implements the ListIterator class.

• Override method getFirst() to return the first element of the list myList.

• Override method getLast() to return the last element of the list myList.

• Override method addFirst() to add an element at the beginning of the list myList.

• Override method addLast() to add an element at the end of the list myList.

• Override method add() to add element at the specified index.

• Override method removeFirst() to remove an element from the beginning of the list myList.

• Override method removeLast() to remove an element from the end of the list myList.

• Override method remove() to remove an element from the specified index in the list myList.

• Override the toString() method to store the content of the list in a string.

• Override the clear() method to empty the list.

• Override the contains() method to check whether the specified object is in the list or not.

• Override the get() method to return the element at the specified index.

• Override the indexOf() method to return the index of the element passed to it.

• Override the lastIndexOf() method to return the index at which the last occurrence of element is.

• Override the set() method so that a new element is placed at the place of the element present at the specified index.

• Override the size() method to return the size of the list.

• Override the iterator() method so that it returns the object of LinkedListIterator.

• Create an inner class LinkedListIterator.

• Create an inner class Node.

• In inner class LinkedListIterator:

• Define the constructor such that the iterator points at the specified index.

• Override the hasNext() method which returns false if the current node is null.

• Override the next() method so that it returns the current element and make the iterator point to the next element.

• Override the remove() method so that it removes the current element.

• Override the hasPrevious() element so that it returns false if the current node does not have predecessor.

• Override the nextIndex() method so that it returns the index of the next element.

• Override the previousIndex() method so that it returns the index of the previous element.

• Override the set() method so that it replaces the current element with the specified element.

• Override the add() method so that it adds an element after the current position of the iterator.

Program:

/*****************************************************

* Program to implement the TwoWayLinkedList and *

* Traverse it using an iterator *

*****************************************************/

import java.util.ListIterator;

public class doublyLinkedList

{

public static void main(String[] args)

{

//Creating myList of TwoWayLinkedList

TwoWayLinkedList myList = new

TwoWayLinkedList<>();

//adding elements to myList

myList.add(1);

myList.addFirst(2);

myList.addLast(3);

myList.add(4);

myList.add(2,9);

myList.add(5,10);

myList.add(1);

myList.add(8);

System.out.println("List after adding elements");

//printing content of the list

System.out.println(myList.toString());

myList.removeLast();

myList.removeFirst();

myList.remove(3);

System.out.println("List after removing elements");

//printing content of the list

System.out.println(myList.toString());

//creating an Iterator class object myIterator for

// myList

java.util.ListIterator myIterator =

myList.iterator();

//traversing myList

System.out.println("\nTraversing the list using "

+"the iterator from head to tail:");

while(myIterator.hasNext())

{

System.out.print(myIterator.next() +" ");

}

//setting Iterator to last element

myIterator = myList.listIterator(myList.size-1);

System.out.println("\nTraversing the list using "

+"the iterator from tail to head:");

// run loop till myIterator has previous element

while(myIterator.hasPrevious())

{

System.out.print(myIterator.previous() + " ");

}

}

// Class TwoWayLinkedList contains methods to

//manipulate and create a Two way linked list

static class TwoWayLinkedList extends

java.util.AbstractSequentialList

{

private Node head, tail;

private int size;

//constructor of TwoWayLinkedList

public TwoWayLinkedList()

{

}

//creating a list and filling it with objectArray

public TwoWayLinkedList(E[] objectArray)

{

for (E eObj : objectArray)

{

add(eObj);

}

}

// method to return first element in list

public E getFirst()

{

//checking if list is empty

if (size == 0)

{

return null;

}

//returning head element

else

{

return head.element;

}

}

// method to return last element of list

public E getLast()

{

//if list is empty

if (size == 0)

{

return null;

}

//returning tail element

else

{

return tail.element;

}

}

// method to add an object to the front

public void addFirst(E eObj)

{

//creating a new node

Node newNode = new Node<>(eObj);

//pointing the next element of node to the head

newNode.next = head;

//making head point to the newNode

head = newNode;

//incrementing the size of list

size++;

//if newNode is only element in list

if (tail == null)

{

//tail and head are same

tail = head;

}

//if there are elements already in the list

//myList

if (head != tail)

{

//to implement the two way List

head.next.previous = head;

}

}

//this method adds an element to the end of the

//list myList

public void addLast(E eObj)

{

//create newNode, a node, to be added

Node newNode = new Node<>(eObj);

//to store the tail element

Node temp = tail;

//tail is null implies that the list myList is

//empty

if (tail == null)

{

//both head and tail points to the newNode

head = tail = newNode;

}

//if list myList is not empty

else

{

//last element's next point to newNode

tail.next = newNode; // Link the new with

//the last node

//make newNode the tail

tail = tail.next;

}

//increment the size of the list

size++;

//make the previous of new tail point to the

//previous tail

tail.previous = temp;

}

//to add a new element at the specified index

@Override

public void add(int index, E eObj)

{

//if specified index is 0

if (index == 0)

{

//call addFirst method to add element at

//the front

addFirst(eObj);

}

//if specified index is greater than the size

//of the list

else if (index >= size)

{

//call addLast method to add element at the

//last

addLast(eObj);

}

//if specified index is in between

else

{

//create a new node, current and initialize

//it with head

Node current = head;

//traverse to the specified index

for (int idx = 1; idx < index; idx++)

{

current = current.next;

}

//create a temp node

Node temp = current.next;

//add element after the current

current.next = new Node<>(eObj);

//next element of current point to the temp

(current.next).next = temp;

//increment the size of the list myList

size++;

//previous of temp is next of current

temp.previous = current.next;

//previous of current's next is now current

current.next.previous = current;

}

}

//remove the head element of the myList and return

//the element in the head

public E removeFirst()

{

//if list myList is empty

if (size == 0)

{

//return null

return null;

}

//if list myList is not empty

else

{

//create a temp node and assign head to it

Node temp = head;

//make the successor of head the new head

head = head.next;

head.previous = null;

//decrement the size of the list

size--;

//if the removed element was the only

//element

if (head == null)

{

//make the tail point to null

tail = null;

}

//return the removed element

return temp.element;

}

}

//remove the tail element of the list and

//return the element in the tail

public E removeLast()

{

//switch the size of the list myList

switch (size)

{

//if the list myList is empty

case 0:

return null;

//if the element to be reomved is the only

//element in the list myList

case 1:

{

//create a temp node and assign head to

//it

Node temp = head;

//make head and tail null

head = tail = null;

//make the size of the list 0 as list

//is empty now

size = 0;

//return the removed element

return temp.element;

}

//if size of list myList is more than 1

default:

{

//create a temp node and store tail

//element in it

Node temp = tail;

//make the predecessor of the tail the

//new tail

tail = tail.previous;

//make next of tail null

tail.next = null;

//decrement the size of the list myList

size--;

//return the removed element

return temp.element;

}

}

}

//method to remove the element at the specified

//position in the list myList

@Override

public E remove(int index)

{

//if the specified index is out of bound

if (index < 0 || index >= size)

{

//no element will be removed

return null;

}

//if the specified index is 0 then remove

//the first element by calling method

//removeFirst

else if (index == 0)

{

//call method removeFirst

return removeFirst();

}

//if the specified index is size -1 then remove

//the last element by calling method removelast

else if (index == size - 1)

{

//call method removeLast

return removeLast();

}

//if the element to be removed is in between

else

{

//create a temporary head node

Node current = head;

//traveerse to the element to be removed

for (int idx = 1; idx < index; idx++)

{

current = current.next;

}

//temo node to store the next element of

//the current

Node temp = current.next;

//removing the node

current.next = temp.next;

//updating the previous of the successor of

//the temp as this is a TwoWayList

temp.next.previous = current;

//decrement the size

size--;

//return the removed element

return temp.element;

}

}

// method to convert to string

@Override

public String toString()

{

// creating StringBuilder class object

StringBuilder listContent = new

StringBuilder("[");

// setting current node as head

Node current = head;

// run loop to convert the elements to string

for (int idx = 0; idx < size; idx++)

{

listContent.append(current.element);

current = current.next;

if (current != null)

{

// Separate two elements by a comma

listContent.append(", ");

}

else

{

// Insert the closing bracket ‘]’ in

//the output string

listContent.append("]");

}

}

// returning the list as string

return listContent.toString();

}

// clear the list myList

@Override

public void clear()

{

// setting head and tail as null

head = tail = null;

}

// method to check if myList has the specified

//element

@Override

public boolean contains(Object eObj)

{

// assigning current node as head

Node current = head;

// run loop to check if the given object

//matches the element in the list

for(int idx=0;idx

{

if(current.element == eObj)

// if element matches return true

return true;

current = current.next;

}

return false;

}

// return the element at the specified index

@Override

public E get(int index)

{

// if the given index within a specified range

if(index>=0 && index

{

// setting current node as head

Node current = head;

// running loop to check and return element

//at given index

for(int idx=0;idx

current = current.next;

return current.element;

}

// else return null

else

{

return null;

}

}

// return the index of the specified element

@Override

public int indexOf(Object eObj)

{

// setting current node as head

Node current = head;

// running a loop to check if the given element

//matches the element in the list and return

//its position

for(int idx=0;idx

{

// if element matches the given object then

//return the position

if(current.element == eObj)

return idx;

current = current.next;

}

return -1;

}

// method to return the index of last matching

// element

@Override

public int lastIndexOf(Object eObj)

{

int l=-1;

// assigning the current node as head

Node current = head;

// run loop to check the last index of the

//given element

for(int idx=0;idx

{

if(current.element == eObj)

l=idx;

current = current.next;

}

return l;

}

// method to replace the element at specified index

@Override

public E set(int index, E eObj)

{

// check if the index is between a specified

// range

if(index>=0 && index < size)

{

// setting current node as head

Node current = head;

// running the loop till given object is

// found and replacing it

for(int idx=0;idx

current = current.next;

current.element = eObj;

}

else

throw new IndexOutOfBoundsException

("Index: " + index + ", Size: "

+ size);

return null;

}

// Overriding the iterator method

@Override

public java.util.ListIterator iterator()

{

return new LinkedListIterator<>();

}

// method to return iterator object for a given

// index

@Override

public ListIterator listIterator(int index)

{

return new LinkedListIterator<>(index);

}

// this class is used to implement linked list

// iterator

private class LinkedListIterator implements

ListIterator

{

// Current index

private Node current = (Node) head;

int index = 0;

// constructor

public LinkedListIterator()

{

}

// parameterized constructor

public LinkedListIterator(int index)

{

if (index < 0 || index > size)

{

throw new IndexOutOfBoundsException

("Index: " + index + ", Size: "

+ size);

}

for (int nextIndex = 0; nextIndex < index;

nextIndex++)

{

current = current.next;

}

}

// method to check next element

@Override

public boolean hasNext()

{

return (current != null);

}

// method to return next element

@Override

public E next()

{

E eObj = current.element;

current = current.next;

return eObj;

}

// method to remove the element

@Override

public void remove()

{

if(index==0)

{

current = current.next;

current.previous = null;

}

else

{

current.previous.next = current.next;

current.next.previous =

current.previous;

}

}

// checking if the list has previous element

@Override

public boolean hasPrevious()

{

return current != null;

}

// method to return the next index

@Override

public int nextIndex()

{

return index+1;

}

// method to return the previous element

@Override

public E previous()

{

E eObj = current.element;

current = current.previous;

return eObj;

}

// method to return previous index

@Override

public int previousIndex()

{

return index-1;

}

// method to set the object in the list

@Override

public void set(E eObj)

{

current.element = eObj;

}

// method to add a object to the list

@Override

public void add(E eObj)

{

Node newNode = new Node<>(eObj);

Node temp = current.next;

if(temp==null)

{

newNode.previous = current;

current.next = newNode;

}

else

{

newNode.next = current.next;

newNode.previous = current;

current.next.previous = newNode;

current.next = newNode;

}

}

}

// this class implements a node for linked list

public class Node

{

// defining variables

E element;

Node next;

Node previous;

// constructor

public Node(E o)

{

element = o;

}

}

// method to return size

@Override

public int size()

{

return size;

}

}

}

Sample Output:

List after adding elements

[2, 1, 9, 3, 4, 10, 1, 8]

List after removing elements

[1, 9, 3, 10, 1]

Traversing the list using the iterator from head to tail:

1 9 3 10 1

Traversing the list using the iterator from tail to head:

1 10 3 9 1

i hope it helps..

If you have any doubts please comment and please don't dislike.

PLEASE GIVE ME A LIKE. ITS VERY IMPORTANT FOR ME