Notes for lab on Linked List Search

The assignment is to implement Search on a Linked List data structure. For Extra Credit, implement Deletion from a Linked List.

As presented in class, a linked list is a chain of similar type objects, called nodes in the linked list. The chain is formed by a variable called next: it holds a reference to the next node in the chain of nodes. The first node in the linked list is called the head. In our version of a linked list, the user of the list is responsible for keeping the head value.

We have reimplemented the LinkedListNode class to make things a bit clearer (we no longer need the casting operator). The base class LinkedListNode has fnctionality common to all linked lists. We have extended it in two ways,

LinkedListIntNode, for a linked list of node objects with integer data, and,
LinkedListStringNode, for a linked list of node objects with String data.

In each extension, we added a data field containing and overrode the printNode method so that when the node is asked to print iteself, it prints this data.

We have also vastly improved to the LinkedListBothTest class to take input from the user. It uses the ReadIntegerAndStrings class.

Assignment

Start with the LinkedListIntNode class and add a search method.

Important: In class I indicated you should add the search method to the base calss LinkedListNode. This is a bit tricky. Just add it in the extended class LinkedListIntNode. OK?

The search method has the signature:

     LinkedListIntNode search(int intToSearchFor )

It returns null if intToSearchFor is not in the list. If it is in the list it returns a value of LinkedListIntNode type that points to a node containing that integer. (There may be multiple possiblities to return, return whichever is easiest for you.)

Derive the test class from LinkedListBothTest, just using the integer part. Input integers forming a linked list until 0 is entered. Then prompt for integers and search for them, printing FOUND or NOT-FOUND accordingly. A zero input exits the program.

Extra Credit

Write a delete method. Again, this is easiest to do directly in the LinkedListIntNode class. Given an integer, search for it: if found delete it; if not found leave the list unchanged. There are two cases: the node to delete is the first node in the linked list, or it is not. If it is, do what's appropriate. If not, you begin your search. Keep a trailing pointer which is referencing the node just before the node you are looking at. That is, if p is the node you are looking at, and the trailing pointer is q, then it should be true that

    q.next==p.

(If you are looking at the first node, there is nothing before it, and that is why the first node deletion is special!)

If and when you find the node you are looking for, it is q that gets changed.

Your test program should input integers similar to the search test program and then enter a deletion phase. If it finds the entered integer it deletes it and prints the list, else it answers NOT FOUND.