Home  Previous  Next 

CSC205::Lecture Note::Week 08
Assignments 
Handouts 
Resources 
Email Thurman {
compufoo::Twitter 
Facebook 
YouTube}
GDT::Bits::
Time

Weather

Populations

Special Dates
Main.java
[linkedlist]
SinglyLinkedList.java
{OOP version} 
DoublyLinkedList.java
[stack]
NumberSystemStack.java 
Stack.java 
ParenChecker.java 
Stack2.java
[queue]
Queue.java 
FootNotes.java
(footnotes.in.txt) 
Q.java 
TestQ.java 
PriorityQueue.java 
CircularArrayQ.java
A list is a linear data structure whose components can only be accessed sequentially, one after another.The first item is a list is called the head or front and the last item is called the tail , back or end.
Lists have the following features:
List operations include:
 varying lengths (a list grows when items are added to it, and it shrinks when items are removed)
 homogeneous components (e.g. list of integers, list of prime numbers, list of
string
objects) sequential access to components via a list cursor
 define a list
 check if a list is empty
 check if a list is full
 reset (move list cursor to front of the list)
 advance the list cursor
 endoflist (move list cursor to back of the list)
 get current item
 insert before current item
 insert after current item
 remove item
GDT::Java::Code::GoofyIntList.java
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).
The objects of a set are called elements (or members).
A set the following properties:
 all elements of a set belong to some universe
 any object of the universe is either in a set or it is not
 there is no particular ordering of elements within a set
Example of sets:
 a set of classes that a student it taking
 a set of email addresses in an adress book
 a set of prime numbers
The following operations are performed on a set:
 construct (i.e. define/create/instantiate) a set
 check to see if an object is a member of a set
 test if a set is empty
 get the cardinality (size of a set; number of elements/members)
 check if set A is included in set B (if so, then A is subset of B and B is superset of A)
 determine union of two sets (all elements appearing in A or B)
 determine intersection of two sets (all elements appearing in A and B)
 difference between to sets (all elements of set A not in set B  notation: A  B)
 add an object to a set
 remove an object from a set
 clear all objects from a set
An array (i.e. vector) can be used to store a set.
A class that is used to represent a set could have the following instance methods:
Set(); Set(int capacity); boolean isMember(Object element); boolean isEmpty(); boolean isSubset(Set other); int size(); Set union(Set other); Set intersection(Set other); Set difference(Set other); void add(Object element); void remove(Object element); void clear();
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
A stack is a data structure in which all access is restricted to the mostrecentlyinserted elements (LIFO: LastInFirstOut).
My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the topmost plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and pushes them on top of the stack  now John Q. Customer comes up and is stuck using a hot plate.
A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called push , pop and top .
Elements are inserted onto a stack by using a push operation.
Elements are deleted from a stack by using a pop operation.
The mostrecently inserted element can be examined by using a top operation.
Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:
 create an empty stack
 read symbols until EOF
 if the symbol is an opening symbol, push it onto the stack
 if the symbol is a closing symbol and the stack is empty, then report an error
 otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
 at EOF, if stack is *not* empty, then report an error
A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is deallocated from the stack. In addition, "jump" information and return value data is stored on the stack.
Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
A queue is a data structure in which all access is restricted to the leastrecentlyinserted elements (FIFO: FirstInFirstOut).
Operations are:
enqueue
 insert at the back of the line (append)dequeue
 remove from the front of the linefront
 access item from front of the lineExamples of a queue: buffered input and a line printer spooler.
Another queue example: message queues.
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
A priority queue allows the highest priority element to be removed from a queue even though it may not be the "oldest."
Real world example of a priority queue: You go to a restaurant with a friend that has a wait. There are a number of queues: a queue for two person table, a queue for a four person table, and a queue for large party table. You are placed on the queue for a two person table. There are three "elements" ahead of you. In comes a VIP with a friend. The next two person table that opens up is given to the VIP.
An operating system may use a priority queue when scheduling jobs. By default, each job is given the same priority. CPU access is granted using a queue (first come, first served). In certain cases, however, you may have a job that needs to get more CPU usage. In those cases, it will be given a priority higher than the default. The OS will use a scheduling algorithm to ensure the higher priority job gets the CPU with more frequency.
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
A linked list is a lowlevel structure upon which highlevel data structures can be built (e.g.
stacks
andqueues
can be implemented using a linkedlist).Sometimes the only Abstract Data Type (ADT) available for organizing data is the builtin array; however, this can be problem if the elements of the array need to be stored in some sort of order and elements are going to be inserted and deleted from the array. It can also be problem when arrays need to grow (i.e. increase in length [capacity]). In these cases a linkedlist may be the solution.
A linkedlist is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members: a data member (the data value of the list item) and a link member (a value locating the next node).
If each node contains only one link member, then we have a singly linked list.
Unlike an array, the nodes of a linkedlist do not necessarily occupy consecutive memory locations.
The implementation of a linkedlist relies heavily on dynamic memory allocation. [Every node is dynamically allocated. When a linkedlist is created, its length (i.e. # of nodes) is unknown.]
Terminology
A linked list consists of a set of nodes. Each node contains data and link members. The first element is called the front and is pointed to by head. The endoflist (EOL) is called the rear its link data member has the value
NULL
(i.e. 0). In some implementations the rear is pointed to by tail. List applications traverse the linked list using a cursor as a reference (or pointer) to the current element.class Node
Example instance variables.
some_data_type data // 1 or more of these Node next // pointer to next node Node prev // if doublylinkedlistclass LinkedList
Example instance variables.
head // handle to the 1st node in the linkedlist size // # of nodes in linkedlist capacity // maximum nodes allowed // maybe more...Possible instance methods.
constructors to initial linkedlist objects add()  add nodes to the end of linkedlist insert()  insert nodes into a linkedlist delete()  delete (remove) nodes from a linkedlist update()  update (modify) a node in a linkedlist search()  search a linkedlist for data // maybe more...Bjarne Stroustrup: Why you should avoid Linked Lists
LinkedList notes: Singly  Doubly
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
Home  Previous  Next 
