CSCE 221 Chapter 5

« previous | Tuesday, January 25, 2010 | next »

Vector ADT

• elemAtRank(r)
• replaceAtRank(r, o)
• insertAtRank(r, o)
• removeAtRank(r)

Array-based Implementation

Use array of actual size $N$; keep track of true size with aux variable $n$

	best	average	worst
elemAtRank	$O(1)$	$O(1)$	$O(1)$
replaceAtRank	$O(1)$	$O(n/2)=O(n)$	$O(n)$
insertAtRank	$O(1)$	$O(n/2)=O(n)$	$O(n)$
removeAtRank	$O(1)$	$O(n/2)=O(n)$	$O(n)$

Fixed-size array implementation does not affect speed.

Thursday, January 27, 2011

List ADT

Generic methods:

• unsigned int size()
• bool isEmpty()
• bool isFirst(p) return boolean if item is first in list
• bool isLast(p) return boolean if item is last in list
• Position first() return position of first element
• Position last() return position of last element
• Position before(p) return position of element prior to Position p
• Position after(p) return position of element after Position p
• void replaceElement(p, o) replace element at Position p with Object o
• void swapElements(p, q) switch objects stored at Positions p and q
• Position insertBefore(p, o) insert a new object right before Position p; returns position of inserted object
• Position insertAfter(p, o) insert a new object right after Position p; returns position of inserted object
• Position insertFirst(o) insert a new object at the beginning of the list; returns position of inserted object
• Position insertLast(o) insert a new object at the end of a the list; returns position of inserted object
• void remove(p) removes an object from Position p

Position

An abstraction of a pointer.

• Object& element();
• bool isNull();

Position.element() returns the element stored inside a node; think of Position as a superclass for Node (no public access to next or previous)

Sample implementation of a List ADT with a singly linked list

def first
  return @first
end

def last()
  return new Position(@last);
end

def before(p)
  node = @first
  p_node = new Node(p)
  while node.next != NULL
    return new Position(node) if node.next == p_node
  end
  return new Position(NULL)
end

def after(p)
  return p.next()
end

Sample implementation of a list with a doubly linked list

def before(p)
  return new Position(new Node(p).previous());
end

Sequence ADT

Union of List and Vector:

From List:

• unsigned int size()
• bool isEmpty()
• bool isFirst(p) return boolean if item is first in list
• bool isLast(p) return boolean if item is last in list
• Position first() return position of first element
• Position last() return position of last element
• Position before(p) return position of element prior to Position p
• Position after(p) return position of element after Position p
• void replaceElement(p, o) replace element at Position p with Object o
• void swapElements(p, q) switch objects stored at Positions p and q
• Position insertBefore(p, o) insert a new object right before Position p; returns position of inserted object
• Position insertAfter(p, o) insert a new object right after Position p; returns position of inserted object
• Position insertFirst(o) insert a new object at the beginning of the list; returns position of inserted object
• Position insertLast(o) insert a new object at the end of a the list; returns position of inserted object
• void remove(p) removes an object from Position p

From Vector:

• elemAtRank(r)
• replaceAtRank(r, o)
• insertAtRank(r, o)
• removeAtRank(r)

"Bridge" Methods:

• rankOf(p)
• positionOf(r)

Position stores element and rank