Implementation of a linked list

• LinkedList


  Generic class named "MyLinkedList" implemented as a doubly linked list
• MyLinkedList


  • Maintains references to both ends of the list
  • Allows constant time cost per operation as long as the operation occurs at a known position
• Classes to be provided

  • MyLinkedList class
  • Node class
  • LinkedListIterator class
• MyLinkedList class


  Contains links to both ends, the size of the list, and a host of methods
• Node class


  A private nested class that contains data and links to the previous and next nodes, along with appropriate constructors
• LinkedListIterator class


  • Abstracts the notion of a position and is a private inner class, implementing the Iterator interface
  • Provides implementations of next, hasNext, and remove
• Sentinel nodes


  Extra nodes at the beginning and/or end of the list representing the beginning and end markers
• Header node


  Node at the front
• Tail node


  Node at the end
• Advantages of using sentinel nodes

  • Greatly simplify the coding by removing a host of special cases
  • Without a header node, removing the first node becomes a special case because we must reset the list's link to the first node during the remove
  • The remove algorithm in general needs to access the node prior to the node being removed
• In a class, the data members are normally private