Data Structure 4

Unlike queues and stacks, the Collection ADTs allow retrieval of information based on the contents of the information.

Elements in a collection are not in any particular order. Retrieval of an element requires comparisons.

• It returns true if and only if the
• two variables reference the same object.

or if they have the same value

By copy: The ADT manipulates copies of the data used in the client program.

• By reference: The ADT manipulates references to the actual
• elements passed to it by the client program. This is the most
• commonly used approach and is the approach we use in our
• course.

• Object's clone method, Cloneable interface
• Drawbacks: 
• Copy of object might not reflect up-to-date status of original object
• Copying objects takes time, especially with deep-copying methods.
• Storing extra copies of objects also requires extra memory.

contents of the collection ADT are exposed ot the client program so it has direct access to the individual elements in the collection 

Drawbacks: 

Objects are accessed through aliases so the client program could accidently change an attribute of the objects. This might in turn cause problems. For example if it changes the key value for an element stored in a sorted list, then the order of the list is broken.

• If processing time and space are issues, and if we are comfortable
• counting on the application programs to behave properly, then the
• "by reference" approach is probably best.

• If we are not too concerned about time and space (maybe our list
• objects are not too large), but we are concerned with maintaining
• careful control over the access to and integrity of our lists, then the
• "by copy" approach is probably best.

Insertion for sorted lists: need to shift elements after the insertion position one slot toward the end.

Deletion for sorted lists: need to shift elements after the deletion positionone slot toward the front.

Insertion for unsorted lists: can simply insert the element to the first empty slot in the list. No shift is needed.

Deletion for unsorted lists: use the last element to replace the deleted element. No shift is needed.

Insertion for unsorted lists: can simply insert the element to the front of the list.

Insertion and deletion for sorted lists: need to update references of the related nodes.

data and link(a reference to the next-node)

1.Find the location where the new element belongs;

2.Create a node for the new element;

3.Correctly link the new node into the identified location.

list in which every node has a successor; the "last" element is succeeded by the "first" element.

• public booleanremove (T element)
• // Removes an element e from this list such that
• // e.equals(element) and returns true;
• // if no such element exists returns false.
• {
•   find(element);
•   if (found)
•   {
•      if (list == list.getLink()) // if single element list
•         list = null;
•       else
•           if (previous.getLink() == list) // if removing last node
•               list = previous;
•           previous.setLink(location.getLink()); // remove node
•           numElements--;
•    }
•    return found;
• }

• public void add(T element)
• // Adds element to this list.
• {
•     LLNode<T> newNode= new LLNode<T>(element);
•     if (list == null)
•     {
•         // add element to an empty list
•         list = newNode;
•         newNode.setLink(list);
•     }
•     else
•     {
•       // add element to a non-empty list
•       newNode.setLink(list.getLink());
•       list.setLink(newNode);
•       list = newNode;
•      }
•       numElements++;
• }

linked list in which each node is linked to both its successor (link) and its predecessor (back).

Header node-A placeholder node at the beginning of a list; used to simplify list processing.

Trailer node-A placeholder node at the end of a list; used to simplify list processing.