General Properties of a List

• Maintains data order
• Time of insertion, priority, alphabetical,...
• Recall Ordered Array & Priority Queue
• Slow insertion O(N)
• Had to search, then move N/2 (average) items
• Deletion O(1) for Priority Q
  but O(N) for Ordered Array
• List allows insertion or deletion anywhere
• Stacks, queues, dequeues limit insert & delete
• Priority Queue limits delete
• Lists & Ordered arrays allow insert/delete anywhere

• Most like the ordered array
• Problems include
• Slow insert & delete
• Static size limit
• Can't make array dynamic (w/o vectors)
• Or, amortized allocate and copy
• Can we speed up insert & delete?
• Have to search a linear structure for location

• They are simple
• Basic problem is the ordering of the elements
• the connection between them is based solely on location
• The next element is the next contiguous memory location
• previous abuts on the other side
• This is a property of arrays --> It lets us get fast, easy "random access"
• How does that work?

• We can use a separate array of integers to indicate which element is next in our list.
• Neighbor elements no longer need to be contiguous
• They are instead "linked" by the second array
• Separate Array of Cells in Use

• To insert an item (999) at end
  Put value in next available location: Data[newIndex] // Data[5]
  Next[last] = newIndex
  last = newIndex
• Cost?
  Traversal just became more difficult
  Had to use a second array (of ints)
  Linked list in an array - Next[i] is our "pointer"
• To insert an item (1) at start
  Put value in next available: data[5]
  Next[newIndex] = first
  first = newIndex
• Can we insert in the middle?
• Search for location (666)
  Let found be index of cell that will precede the new value

Current <- first
While (Data[next[current]] < v)
	current <- next[current]
found <- current



Next[newIndex] = Next[found]
Next[found] = newIndex
Data[newIndex] = v

okay for 1st and last item?

Special cases:

1. check beginning before loop

2. If (Next[current] == last) // at end

General Insert:

Search for location 
If (Data[first] > v)
	//Use insert at beginning
Current <- first
While (current != last && Data[next[current]] < v)
    current <- next[current]
found <- current
If (found == last)
	// use insert at end
else  
	// use insert in middle

Delete an element

• Simply adjust Next to skip over an element (543)

  If found is the index of cell preceding the cell to be deleted
  	Next[found] =   Next[ Next[found] ]
  

• Special cases - first & last elements are almost always special cases!
• Issues
  • where did we get NewIndex
  • How do we keep track of empty cells?
  • Use a sentinel // Next[avl] = -1;
  • Use a separate available array
    Could be a list, stack or queue
    Or, maintain a second list in the same array
  • Complicated (even if implemented as ADT)
    Uses "parallel arrays" or interweaves lists
  • We have to "manage memory"
    Getting an available cell is like new operation in Java
    Next values are like references (or C++ pointers)
• Array implementation is still static ... overflow
• Typical use as static arrays - memory management

Linked Lists ADT

• Arrays are NOT the way to go!
• Use Linked lists to implement stacks and queues
• Disadvantages:
  Have to work with references & "dynamic memory"
  Can't (easily) access items at random locations
  No [ ] operator for direct access
• 
• 
• Differs from array
• A Link is an object composed of
  data - probably an object reference
  next - a reference to another link object (or null
• This probably uses more space than array of int
• Java handles memory management for us
  New cells are obtained using new
  Deleted cells are returned to system for re-use
• In Java, this is implicit for an unreferenced object
• Linked list code

Special Cases

• Dealing with empty list
  Insert into empty list, or delete last node
• Insert or delete at beginning of list
• Insert or delete at end of list
• Often makes sense to think of general case first, then deal with special cases
• Working in middle of the List
• search operation (find)
  Book code -->Assume list is not empty. (What if it is empty?)
• Need to iterate through the list
• Delete a Cell
• Insert a Cell
• Find a Cell
• Linked list code for finding specified links

Using Lists for Sorting

• Don't know how many elements are in list.
• Can only directly access the first Link.
• Link must have a displayLink() method
• Check for empty list in removeFirst().
• Check for full list in insertFirst()?

  public Link removeFirst() {
   Link temp = first;
   if (first)
       first = first.next;
   return temp;
   }
  

• Delete Cases:
  1. Item found in center of list
  2. Item found at beginning of list
  3. Item found at end of list
  4. Item not found
  5. Empty list (code change?)
  6. Duplicate values?
• Insert Cases:
  1. Item belongs in center of list
  2. Item belongs at beginning of list
  3. Item belongs at end of list
  4. Item is a duplicate
  5. Empty list
• Efficiency:
  • Insert, delete and Find are O(N)
    Need to traverse half the list on average
  • Display is O(N)
    Need to traverse entire list
  • insertFirst and reomve First are O(1)
• sorted Linked list Code
• Algorithm Analysis of using a list to sort an array
  • Insert
    For each element in unsorted array, insert the element into a sorted List
    Best(beginning): O(1) Avg: O(N/2) Worst (end): O(N)
  • Delete
    while !list.isEmpty(),Copy first element back into array & delete it
    Each operation is O(1)
  • O(N²+N) and uses "twice" the space
    not an "n place" sort
  • Thus, O(N²)
• Insertion sort can also be coded using a linked list
  listInsertionSort Code
• Make sure you understand the array of links in the above code

Other liked list ADTS

• Implement a Stack
  insertFirst() & removeFirst()
  linkStack Code
• Implement a Queue?
  Need a doubly ENDED List
  Double-Ended list allows fast insertLast()
  
  linkQueue Code
• What if you want to traverse the list backwards?
• Add a back-pointer to the Link that references the previous node in the list
• current and previous - only need one pointer now
• Doubly linked lists
• Doubly Linked list Code
• First Last Doubly Linked list Code
• How does it affect the efficiency of the implementation?
  • Insert, delete and Find are O(N)
    Need to traverse half the list on average
  • Traverse list forward or backward is O(N)
  • insertFirst and reomveFirst,insertLast, and removeLast are O(1)
• Can easily implement deque, queue & stack

Iterators ~ array index

• Want to be able to traverse the list operating on each data record…
• Need a way to
  • reference a particular node
    for(i=0;i<MAX;i++){ A[i]... }
  • increment (or decrement) the reference, accessing the "next" node
  • use multiple iterators (at same time)
  • use an iterator to find (return "index"), insert (at "index") or delete (item at "index")
• Iterator API
  • Constructor:
    a reference to the list (first)
  • void reset()
    iterator to first
  • boolean atEnd()
    if iterator is at end of list
  • void nextlink()
    to next node
  • Link getCurrent()
    ref to current node
    data in the node can be examined or modified
  • void prevLink()
    to previous node
    assumes a doubly-linked list and a new previous field
    Add atFirst() method and last to traverse backward
• 
• Iterator Issues
  • atEnd() - Are you at the end of the list when pointing to the last node or just beyond it?
  • nextlink() - What is result of nextLink() when referencing the last node?
  • Equivalent issues for atFirst() and prevLink()
  • Iterator sometimes has to access first
  • What if some other iterator (or the LinkList itself) is adding/removing a node at the same time?
  • What if the list is empty?
• Java Colections
  boolean add(Object obj)
  Iterator iterator()
• Java Iterator
  Object next()
  boolean hasNext()
  void remove()

  public final class LoopStyles { 
  public static void main(String... aArguments) { 
    List flavours = new ArrayList<>(); 
    flavours.add("chocolate"); 
    flavours.add("strawberry"); 
    flavours.add("vanilla"); 
    useWhileLoop(flavours); 
    useForLoop(flavours); 
  }
  private static void useWhileLoop(Collection aFlavours) { 
    Iterator flavoursIter = aFlavours.iterator(); 
    while (flavoursIter.hasNext()){ 
       System.out.println(flavoursIter.next()); 
  } } 
  
  /** * Note that this for-loop does not use an integer index. */ 
  private static void useForLoop(Collection aFlavours) {
    for (Iterator flavoursIter = aFlavours.iterator(); flavoursIter.hasNext();){ 
      System.out.println(flavoursIter.next()); 
  } } 
  
  private static void forInLoop(Collection aFlavours){
     for (String f : aFlavours)
         System.out.println(f);
  }