Question

Introduction:

In this project you will create a generic linked list using
Java Generics.



Description:

   Create a generic class called GenLinkedList.  GenLinkedList will use nodes
   that store a value of the generic type to store its contents.

   It should have the following methods.  The methods should 
   all operate on the object making the call (none are static).  

   Perform checking of the parameters and throw exceptions where 
   appropriate.

   The linked list should be singly-linked.

   It should not use sentinel nodes (empty header and tail nodes).  

   You should strive for an efficient implementation of each method.


7 points each (a-h)

   a.  addFront
        receives an item to add as a parameter, and adds to the front of the list.

   b.  addEnd
        receives an item to add as a parameter, and adds to the end of the list.

   c.  removeFront
        removes a node from the front of the list.

   d.  removeEnd
        removes a node from the end of the list.

   e.  set
        receives a position and item as parameters, sets the element at this
        position, provided it is within the current size

   f.  get
        receives a position as a parameter, returns the item at this position,
        provided it is within the current size

   g.  swap
        receives two index positions as parameters, and swaps the nodes at
        these positions, provided both positions are within the current size

   h.  shift
        receives an integer as a parameter, and shifts the list forward or
        backward this number of nodes, provided it is within the current size


11 points each (i-l)
   i.  removeMatching
        receives a value of the generic type as a parameter and removes all
        occurrences of this value from the list.

   j.  erase 
        receives an index position and number of elements as parameters, and
        removes elements beginning at the index position for the number of 
        elements specified, provided the index position is within the size
        and together with the number of elements does not exceed the size

   k.  insertList
        receives a generic List (a Java List) and an index position as parameters, 
        and copies each value of the passed list into the current list starting
        at the index position, provided the index position does not exceed the size.
        For example, if list has a,b,c and another list having 1,2,3 is inserted at
        position 2, the list becomes a,b,1,2,3,c

   l.  main
        add code to the main method to demonstrate each of your methods
  

Submit to eLearning:
 GenLinkedList.java

Answer 1

code

solution

//Gen_LinkedList.java

//output

//copyable code

//Import the necessary packages

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.List;

import java.util.ArrayList;

import java.lang.IndexOutOfBoundsException;

import java.util.Random;

import java.util.Stack;

// Declare the class

public class Gen_LinkedList<T>

{

// Declare the variables

private GenNode<T> headnode;

// Definition of the function

private static class GenNode<T>

{

public T data;

public GenNode<T> nextnode;

public GenNode(T data)

{

this(data, null);

}

public GenNode(T data, GenNode<T> nextnode)

{

this.data = data;

this.nextnode = nextnode;

}

}

// Definition of the method add_Front

public void add_Front(T itemvalue)

{

headnode = new GenNode<T>(itemvalue, headnode);

}

//Definition of the method add_End()

public void add_End(T itemvalue)

{

// Check whether headnode is null or not

if (headnode == null)

{

headnode = new GenNode<T>(itemvalue);

return;

}

GenNode<T> end = headnode;

// While loop to insert GenNodes

while (end.nextnode != null)

end = end.nextnode;

end.nextnode = new GenNode<T>(itemvalue);

}

// Definition of the method remove_Front()

public T remove_Front()

{

// Check whether headnode is null or not

if (headnode == null)

return null;

    // Removes GenNodes

    GenNode<T> front = headnode;

    headnode = headnode.nextnode;

    return front.data;

    }

    // Definition of the method remove_End()

    public T remove_End()

    {

    // Check whether headnode is null or not

    if (headnode == null)

    return null;

    GenNode<T> previous = null, end = headnode;

    // startnode the while loop to remove elements

    while (end.nextnode != null)

    {

    previous = end;

    end = end.nextnode;

   }

    // Check whether the previous is null or not

    if (previous != null)

    {

    previous.nextnode = null;

    return end.data;

    }

    else

    {

    headnode = null;

    return end.data;

    }

    }

    // Definition of the function

    // get the in between elements of link list.

    private GenNode<T> getSecondToEndGenNode()

    {

    GenNode<T> previous = headnode;

    // While loop to traverse the elements.

    while (previous != null && previous.nextnode != null

    && previous.nextnode.nextnode != null)

    previous = previous.nextnode;

    return previous;

    }

    // Definition of the method to get the end GenNode

    private GenNode<T> getEndNode()

    {

    GenNode<T> end = headnode;

    while (end != null && end.nextnode != null)

    end = end.nextnode;

    return end;

    }

    private GenNode<T> getGenNode(int ind)

    throws IndexOutOfBoundsException

    {

    return get_After_node(ind, headnode);

    }

private GenNode<T> get_After_node(int ind, GenNode<T> startnode)

    {

    // check whether the list found or not

    if (ind < 0 || startnode == null)

    throw new IndexOutOfBoundsException(

    " ind: " + ind);

    int psot = 0;

    // while loop

    while (ind != psot)

    {

    if (startnode.nextnode == null)

    throw new IndexOutOfBoundsException(

    "ind:" + ind);

    startnode = startnode.nextnode;

  psot++;

    }

    return startnode;

    }

     public void set(int ind, T itemvalue)

    throws IndexOutOfBoundsException

    {

    getGenNode(ind).data = itemvalue;

    }

    public T get(int ind)

    throws IndexOutOfBoundsException

    {

    return getGenNode(ind).data;

    }

    public void swap(int ind1, int ind2)

    throws IndexOutOfBoundsException

    {

    // Call to the function

    int startnode_ind = Math.min(ind1, ind2);

    int nextnodeind = Math.max(ind1, ind2);

    GenNode<T> startnode = getGenNode(startnode_ind);

GenNode<T> nextnode = get_After_node(nextnodeind - startnode_ind,

    startnode);

    T tempvalue = startnode.data;

    startnode.data = nextnode.data;

    nextnode.data = tempvalue;

    }

    public void shift(int GenNodeShifts)

    {

    if (GenNodeShifts == 0 || headnode == null

    || headnode.nextnode == null)

    return;

    else if (GenNodeShifts < 0)

    {

    GenNode<T> oldheadnode = headnode;

    headnode = headnode.nextnode;

    getEndNode().nextnode = oldheadnode;

    oldheadnode.nextnode = null;

    shift(GenNodeShifts + 1);

    }

    else

    {

    GenNode<T> oldheadnode = headnode,

    previous = getSecondToEndGenNode();

    headnode = getEndNode();

    headnode.nextnode = oldheadnode;

    previous.nextnode = null;

    shift(GenNodeShifts - 1);

    }

    }

    public Gen_LinkedList<T> reversenode()

    {

    if (headnode == null)

    return new Gen_LinkedList<T>();

    else if (headnode.nextnode == null)

    {

    Gen_LinkedList<T> ret = new Gen_LinkedList<T>();

  ret.add_Front(headnode.data);

    return ret;

    }

    Gen_LinkedList<T> ret = new Gen_LinkedList<T>();

    GenNode<T> GenNode = headnode;

    while (GenNode != null)

    {

    ret.add_Front(GenNode.data);

    GenNode = GenNode.nextnode;

    }

    return ret;

    }

    public void erasenode(int ind, int n)

    {

    if (n <= 0)

    return;

    if (ind == 0)

    try

    {

   

    headnode = getGenNode(n);

    }

    catch (IndexOutOfBoundsException e)

    {

    headnode = null;

    }

    else

    {

    GenNode<T> behindGenNode = getGenNode(ind - 1);

    behindGenNode.nextnode = get_After_node(n + 1,

    behindGenNode);

    }

    }

     public void Insert_list(List<T> list, int ind)

    {

    if (list.isEmpty())

    return;

    // Check headnode

    if (headnode == null)

    {

    GenNode<T> GenNode = new GenNode<T>(list.get(0));

    headnode = GenNode;

    for (int k = 1; k < list.size(); k++)

    {

    GenNode.nextnode = new GenNode<T>(list.get(k));

    GenNode = GenNode.nextnode;

    }

    }

    else if (ind == 0)

    {

    GenNode<T> GenNode = new GenNode<T>(list.get(0));

    GenNode<T> oldheadnode = headnode;

    headnode = GenNode;

    // loop to traverse the element

    for (int k = 1; k < list.size(); k++)

    {

    GenNode.nextnode = new GenNode<T>(list.get(k));

    GenNode = GenNode.nextnode;

    }

    GenNode.nextnode = oldheadnode;

    }

    else

    {

    GenNode<T> begin = getGenNode(ind - 1);

    GenNode<T> old_node = begin.nextnode;

    // startnode the for each loop

    for (T itemvalue : list)

  {

    GenNode<T> GenNode = new GenNode(itemvalue);

    begin.nextnode = GenNode;

    begin = GenNode;

    }

    begin.nextnode = old_node;

    }

    }

    // method toString.

    public String toString()

    {

    StringBuffer o = new StringBuffer("[");

    GenNode<T> tempvalue = headnode;

    while (tempvalue != null)

    {

    // Check whether the tempvalue is equal to headnode or not

    if (tempvalue != headnode)

    o.append(',');

    o.append(tempvalue.data.toString());

    tempvalue = tempvalue.nextnode;

    }

    o.append(']');

    return o.toString();

    }

    public static void main(String[] args)

    {

    System.out.println(

    "List test element" + " an Empty List");

    // Create the object list

Gen_LinkedList<Integer> list = new Gen_LinkedList<Integer>();

    //call method test

    test(list);

    System.out.println(

    "Testing the list with one" + " element:");

    // Create object

    list = new Gen_LinkedList<Integer>();

    list.add_Front(1);

    test(list);

    System.out.println("Test the list with"

    + " ten elements: ");

    list = new Gen_LinkedList<Integer>();

    // startnode the for loop

    for (int k1 = 0; k1 < 9; k1++)

    list.add_End(k1);

    test(list);

    }

    // Declare the method test to perform

    public static void test(Gen_LinkedList<Integer> list)

    {

    // Display output

System.out.println("\t Adding an itemvalue to the"+ " front list element:");

    // startnode the for loop

    for (int k1 = 0; k1 < 4; k1++)

    //call add_front method

    list.add_Front(k1);

    print(list);

System.out.println("\t Add an itemvalue to the "+ "end list element:");

    for (int k1 = 0; k1 < 4; k1++)

    list.add_End(k1);

    print(list);

System.out.println("\tRemoving an itemvalue to "+ " the front list:");

    // startnode the for loop

    for (int k1 = 0; k1 < 4; k1++)

    System.out.println("\t\t" + list.remove_Front());

    // Call to the function

    print(list);

    // Display the output

System.out.println("\tRemoving an itemvalue from"+ " end list element:");

    for (int k1 = 0; k1 < 4; k1++)

    System.out.println("\t\t" + list.remove_End());

    print(list);

    try

    {

    int get = list.get(0);

    System.out.println("\t Accessing the 0th index:" + " " + get);

    // Display the output

System.out.println("\t Set position of 0th index"+ " to 100th index:");

    //call method

    list.set(0, 100);

    print(list);

    // Display the output

System.out.println("Set position of 0th index to" + " initial data:");

    list.set(0, get);

    print(list);

    }

    catch (IndexOutOfBoundsException e)

   {

    // Display the output

    System.out.println(

    "\t could not access 0th " + " index");

    }

    try

  

   {

    //call method

    int get = list.get(4);

System.out.println("\t Accessing the fouth index element :"    + " " + get);

    // Display the output

System.out.println("\t Set postion of fourth index"    + " to 100 index:");

    list.set(4, 100);

    print(list);

    // Display the output

System.out.println("Set position of fourth index"    + " to initial data:");

    //call method

    list.set(4, get);

    print(list);

    }

    catch (IndexOutOfBoundsException e)

    {

    // Display the output

    System.out.println(

    "\tcould not access fourth index");

    }

    try

  {

    // Display the output

    System.out.println("\t Swapping 0 & 1");

    //call method

    list.swap(0, 1);

    print(list);

    // Display the output

    System.out

    .println("\t Without Swapping 0 & 1 ");

    //call method

    list.swap(0, 1);

    print(list);

    }

    catch (IndexOutOfBoundsException e)

    {

    // Display the output

    System.out .println("could not"    + " swap");

    }

    // Display the output

    System.out.println("\t Shifts the list forward by 4");

    //call method

  

    list.shift(4);

    print(list);

    // Display the output

    System.out.println(    "\tShifts the list backward by 4");

    //call method

    list.shift(-4);

    print(list);

    //call method

System.out.println( "\t reversenode List: " + list.reversenode());

    ArrayList<Integer> aL = new ArrayList<Integer>();

    for (int k1 = -5; k1 < 0; k1++)

    //call method

   aL.add(k1);

    // Display the output

System.out.println(    "\t Add the ArrayList at 0th" + "index");

    //call method

    list.Insert_list(aL, 0);

    print(list);

    // Display the output

System.out.println("\t erasenode the four elements "    + "startnode from 0th index");

    //call method

    list.erasenode(0, 4);

    print(list);

    }

    // Define a method print()

   public static void print(Gen_LinkedList<Integer> list)

    {

    System.out.println("\t List: " + list);

    }

    }