C# Console Application:

In the assignment, you will write code to enhance the class List. Figure 19.4 of the textbook shows the code of this class (and other related classes):

// Fig. 19.4: LinkedListLibrary.cs

// ListNode, List and EmptyListException class declarations.

using System;

namespace LinkedListLibrary

{ // class to represent one node in a list

public class ListNode

{

// automatic read-only property Data

public object Data { get; private set; }

// automatic property Next

public ListNode Next { get; set; }

// constructor to create ListNode that refers to dataValue

// and is last node in list

public ListNode( object dataValue )

: this( dataValue, null )

{

} // end default constructor

// constructor to create ListNode that refers to dataValue

// and refers to next ListNode in List

public ListNode( object dataValue, ListNode nextNode )

{

Data = dataValue;

Next = nextNode;

} // end constructor

} // end class ListNode

// class List declaration

public class List

{

private ListNode firstNode;

private ListNode lastNode;

private string name; // string like "list" to display

// construct empty List with specified name

public List( string listName )

{

name = listName;

firstNode = lastNode = null;

} // end constructor

// construct empty List with "list" as its name

public List()

: this( "list" )

{

} // end default constructor

// Insert object at front of List. If List is empty,

// firstNode and lastNode will refer to same object.

// Otherwise, firstNode refers to new node.

public void InsertAtFront( object insertItem )

{

if ( IsEmpty() )

firstNode = lastNode = new ListNode( insertItem );

else

firstNode = new ListNode( insertItem, firstNode );

} // end method InsertAtFront

// Insert object at end of List. If List is empty,

// firstNode and lastNode will refer to same object.

// Otherwise, lastNode's Next property refers to new node.

public void InsertAtBack( object insertItem )

{

if ( IsEmpty() )

firstNode = lastNode = new ListNode( insertItem );

else

lastNode = lastNode.Next = new ListNode( insertItem );

} // end method InsertAtBack

// remove first node from List

public object RemoveFromFront()

{

if ( IsEmpty() )

throw new EmptyListException( name );

object removeItem = firstNode.Data; // retrieve data

// reset firstNode and lastNode references

if ( firstNode == lastNode )

firstNode = lastNode = null;

else

firstNode = firstNode.Next;

return removeItem; // return removed data

} // end method RemoveFromFront

// remove last node from List

public object RemoveFromBack()

{

if ( IsEmpty() )

throw new EmptyListException( name );

object removeItem = lastNode.Data; // retrieve data

// reset firstNode and lastNode references

if ( firstNode == lastNode )

firstNode = lastNode = null;

else

{

ListNode current = firstNode;

// loop while current node is not lastNode

while ( current.Next != lastNode )

current = current.Next; // move to next node

// current is new lastNode

lastNode = current;

current.Next = null;

} // end else

return removeItem; // return removed data

} // end method RemoveFromBack

// return true if List is empty

public bool IsEmpty()

{

return firstNode == null;

} // end method IsEmpty

// output List contents

public void Display()

{

if ( IsEmpty() )

{

Console.WriteLine( "Empty " + name );

} // end if

else

{

Console.Write( "The " + name + " is: " );

ListNode current = firstNode;

// output current node data while not at end of list

while ( current != null )

{

Console.Write( current.Data + " " );

current = current.Next;

} // end while

Console.WriteLine( " " );

} // end else

} // end method Display

} // end class List

// class EmptyListException declaration

public class EmptyListException : Exception

{

// parameterless constructor

public EmptyListException()

: base( "The list is empty" )

{

// empty constructor

} // end EmptyListException constructor

// one-parameter constructor

public EmptyListException( string name )

: base( "The " + name + " is empty" )

{

// empty constructor

} // end EmptyListException constructor

// two-parameter constructor

public EmptyListException( string exception, Exception inner )

: base( exception, inner )

{

// empty constructor

} // end EmptyListException constructor

} // end class EmptyListException

} // end namespace LinkedListLibrary

Enhance the class List by adding two public void methods InsertAfter and Remove.

public void InsertAfter(object insertItem, object targetItem)

{

// This method searches the list for a node that holds the data item

// targetItem. Once this target node is found, create a new node to

// hold the data item insertItem, and insert the newly created node right

// after the target node. Dont forget to update the instance variable

// lastNode if necessary.

// Example: Suppose we have the following list: 7, 2, 13, 5, 8. The call

// InsertAfter(3, 5) will insert 3 after 5. The list after the call will be:

// 7, 2, 13, 5, 3, 8.

// If the targetItem is not found, do not insert anything into the list.

// It the targetItem exists in multiple nodes, insert new node only after

// the first node holding targetItem. For example, suppose we have

// the following list: 7, 2, 1, 2, 5. The call InsertAfter(4, 2) inserts

// 4 only after the first node holding 2. The list after the call will be:

// 7, 2, 4, 1, 2, 5.

}

public void Remove(object targetItem)

{

// This method searches the list for a node that holds the data item

// targetItem. Once this target node is found, remove this node from

// the list. Dont forget to update the instance variables firstNode and

// lastNode if necessary.

// Example: Suppose we have the following list: 7, 2, 13, 5, 8. The call

// Remove(5) removes the node holding 5. The list after the call will be:

// 7, 2, 13, 8.

// If the targetItem is not found, do not remove anything from the list.

// It the targetItem exists in multiple nodes, remove only // the first node holding targetItem. For example, suppose we have

// the following list: 7, 2, 1, 2, 5. The call Remove(2) removes

// the first node holding 2. The list after the call will be:

// 7, 1, 2, 5.

}

Hint: Since both insertAfter and Remove need to search for a node holding a target data item, you may want to write a private Search method for insertAfter and Remove to use.

Use the following code to test your work:

public static void Main(string[] args)

{

List list = new List(); // create List container

// try to insert 3 after 2, should do nothing because the list is empty

Console.WriteLine("Task: Insert 3 after 2");

list.InsertAfter(3, 2);

list.Display();

Console.WriteLine();

// try to remove 2, should do nothing because the list is empty

Console.WriteLine("Task: Remove 2");

list.Remove(2);

list.Display();

Console.WriteLine();

// insert 1 at front

Console.WriteLine("Task: Insert 1 at front");

list.InsertAtFront(1);

list.Display();

// try to insert 3 after 2, should doing nothing because 2 is not there

Console.WriteLine("Task: Insert 3 after 2");

list.InsertAfter(3, 2);

list.Display();

// try to remove 2, should do nothing because 2 is not in the list

Console.WriteLine("Task: Remove 2");

list.Remove(2);

list.Display();

// try to insert 2 after 1

Console.WriteLine("Task: Insert 2 after 1");

list.InsertAfter(2, 1);

list.Display();

// try to insert 4 after 2

Console.WriteLine("Task: Insert 4 after 2");

list.InsertAfter(4, 2);

list.Display();

// try to insert 3 after 2

Console.WriteLine("Task: Insert 3 after 2");

list.InsertAfter(3, 2);

list.Display();

// try to insert 5 after 4

Console.WriteLine("Task: Insert 5 after 4");

list.InsertAfter(5, 4);

list.Display();

// try to remove 2

Console.WriteLine("Task: Remove 2");

list.Remove(2);

list.Display();

// try to remove 1

Console.WriteLine("Task: Remove 1");

list.Remove(1);

list.Display();

// try to remove 5

Console.WriteLine("Task: Remove 5");

list.Remove(5);

list.Display();

// try to remove 3

Console.WriteLine("Task: Remove 3");

list.Remove(3);

list.Display();

// try to remove 4

Console.WriteLine("Task: Remove 4");

list.Remove(4);

list.Display();

Console.WriteLine();

} // end Main

Expected output:

Task: Insert 3 after 2

Empty list

Task: Remove 2

Empty list

Task: Insert 1 at front

The list is: 1

Task: Insert 3 after 2

The list is: 1

Task: Remove 2

The list is: 1

Task: Insert 2 after 1

The list is: 1 2

Task: Insert 4 after 2

The list is: 1 2 4