Programming language: Java

List Class:

public class SinglyLinkedList2 {

private Node head = null; private Node tail = null; private int size = 0;

public SinglyLinkedList2() { }

public int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() { if (head == null) return null; return head.getElement(); }

public E last() { if (tail == null) return null; return tail.getElement(); }

public void addFirst(E e) { head = new Node(e, head); if (size == 0) tail = head; size++; }

public void addLast(E e) { Node newest = new Node(e, null); if (isEmpty()) head = newest; else tail.next = newest; tail = newest; size++; }

public E removeFirst() { if (isEmpty()) return null; E answer = head.getElement(); head = head.next; size--; if (size == 0) tail = null; return answer; }

// public E removeLast() { E answer = tail.getElement(); if (isEmpty()) return null; if (head == tail) head = tail = null;

else { Node temp = head;

while (temp.getNext() != tail) { temp = temp.next; temp.next = null; tail = temp; } } return answer; }

// public void display() { for (Node i = head; i != null; i = i.next) System.out.println(i.getElement()); }

// public void Concatenate(SinglyLinkedList2 newLinkList) { tail.next = newLinkList.head; tail = newLinkList.tail;

}

}

As presented in the lab, linked lists must be searched sequentially. For large lists, this can result in poor performance. A common technique for improving list-searching performance is to create and maintain an index to the list. An index is a set of references to key places in the list. For example, an application that searches a large list of words could improve performance by creating an index with 26 entries-one for each letter of the alphabet. A search operation for a last name beginning with Y' would then first search the index to determine where the 'Y" entries begin, then "jump into" the list at that point and search linearly until the desired name is found, This would be much faster than searching the linked list from the beginning. Use the List class in lab 8 as the basis of an IndexedList class Write a program that demonstrates the operation of indexed lists. Be sure to include methods displayIndexedList, insertInIndexedList, searchIndexedList and deleteFromIndexedList