My references in different kinds of sorting:

1. bubble sort: http://en.wikipedia.org/wiki/Bubble_sort
2. insertion sort: http://en.wikipedia.org/wiki/Insertionsort
3. shell sort: http://en.wikipedia.org/wiki/Shell_sort
4. heap sort: http://en.wikipedia.org/wiki/Heap_sort
5. merge sort: http://en.wikipedia.org/wiki/Merge_sort
6. quick sort: http://en.wikipedia.org/wiki/Quick_sort
7. bucket sort: http://en.wikipedia.org/wiki/Bucket_sort

QUEUE IMPLEMENTATION(group activity)

Concept: List of BSIT enrollee

//declaring a constructor

class Queue{

public int entrynum;

public String firstname;

public String lastname;

public char middlename;

public Queue next;

public Queue (int Enum, String Fname String Lname char M, )

{

entrynum=Enum;

firstname=Fname;

lastname=Lname;

middlename=M;

}

//displaying the elements on the list

public void displayQueue()

{

System.out.print(entrynum +” “ + firstname +” “ +” “middlename+ “ “ +: + lastname)

}

}

/*a separate class which contains the methods of the data structure Queue implemented in a linked list*/

class QueueList

private Queue first;

private Queue last;

public QueueList()

{

first=null;

last=null;

}

//checking if the list has elements or not

public Boolean isEmpty()

{

return (first==null);

}

//inserting an element on the queue

public void Enqueue(int Enum, String Fname String Lname char M, )

{

Queue newQueue= new Queue (int Enum, String Fname String Lname char M, )

if( isEmpty())

last = newQueue;

newQueue.next=first;

first=newQueue;

}

//Deleting an element on the queue

public void Dequeue (int Enum)

{

Queue newQueue=new Queue (Enum);

int temp=first.entrynum;

if (first.next==null)

last=null;

first=first.next;

return temp

}

}

public class MainClass {

public static void main(String[] args) {

LinkQueue theQueue = new LinkQueue();

theQueue.enqueue(001, “Marjorie”, “Egot” , ‘T’, )

theQueue.enqueue(002, “Chrisdyll”, “Pellejo”, ‘P’)

System.out.println(theQueue);

theQueue.enqueue(003, “Julie”, “Pabio”, ‘L’)

System.out.println(theQueue)

theQueue.dequeue(001);

System.out.println(theQueue);

System.out.println(theQueue);

}

}

QUEUES

• is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position.
• First-In-First-Out (FIFO) data structure,the first element added to the queue will be the first one to be removed.
• an example of a linear data structure
• are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes
• are dynamic collections which have some concept of order

Method Summary
boolean	add(E e) Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E	element() Retrieves, but does not remove, the head of this queue.
boolean	offer(E e) Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E	peek() Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E	poll() Retrieves and removes the head of this queue, or returns null if this queue is empty.
E	remove() Retrieves and removes the head of this queue.

references:
http://en.wikipedia.org/wiki/Queue_(data_structure)
http://www.cs.auckland.ac.nz/software/AlgAnim/queues.html
http://java.sun.com/javase/6/docs/api/java/util/Queue.html

Stack Implementation

//a class
class Link{
public int iData=0;


public Link(int iData, ) //constructor
{
iData=id;

}

public void displayLink() //displaying data
{
System.out.println(iData+":" );
}
}

//the classfor operations on the stack
class StackList{
private Link first;

public StackList(){ //declaring as empty or null
first=null;

}

public boolean isEmpty() {
return (first == null);
}

public void insertFirst( int id) { //for insertion
Link newLink = new Link( id);
newLink.next = first;
first = newLink;
}

public Link deleteFirst() //for deletion
{
Link temp=first;
return temp;
}

public Link pick()
{
Link temp=first;
return temp;
}

public void displayList //display data
{
System.out.print("Elements on the stack: ");
Link temp=first;
while(temp!=null)
{
temp.displayList();
}

System.out.println(" ");
}
}

//the main class
class StackListApp
{
public static void main (String[]args)
{
StackList theList=new StackList();

theList.insertFirst(116);//show the insertion of items
theList.insertFirst(82);
theList.insertFirst(34);

theList.deleteFirst();//show the delete item/element

theList.displayList();
}
}

Doubly-Linked List

//this is the implementation of
//Doubly-Linked List

class Link {

public int iData;
public double dData:
public Link next;

public Link(int id,double dd) {
iData = id;
dData=dd;
}
public void displayLink(){
System.out.print("{" +iData+"," dData+"}");
}


class FirstLastList {
private Link first;
private Link last;
public FirstLastList() {
first = null;
last = null;
}

public boolean isEmpty() {
return (first == null);
}
public void insertFirst(int id,double dd) { //method for insertFirst
Link newLink = new Link(id,dd);
if (isEmpty ())
last = newLink;
newLink.next = first;
first = newLink;
}
public void insertLast(int id,double dd) { //method for insertLast
Link newLink = new Link(id,dd);
if (isEmpty()
first = newLink;
else
last.next = newLink;
last = newLink;
}
public Link deleteFirst(int id,double dd) { //method for deletion
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
public Link deleteLast(int id, double dd){
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}
public void displayList(){
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null){
current.displayLink();
current=current.next;
}
}
System.out.println(" ");
}
}
public class FirstLastApps{ //for application
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();

theList.insertFirst(16,3.89);
theList.insertFirst(56,6.45);
theList.insertLast(26,5.00);
theList.insertLast(86,6,90);


System.out.println(theList);
theList.deleteFirst();
theList.deleteLast();
System.out.println(theList);
}
}

Double-ended link list

• list with first and last references

• allow for insertions in the front or in the back of the list
• Double-ended, single-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.

  Nodes have only forward pointers, so the natural traversal is forward, and nodes may be inserted or removed after any node.

• Double-ended, double-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.

  Nodes have both forward and backward pointers, so both traversals are natural, and nodes may be inserted or removed before or after any node.

//code for double-ended

class Link { //a class of methods
public int iData;
public double dData:
public Link next;

public Link(int id,double dd) {
iData = id;

dData=dd;
}
//display elements
public void displayLink(){

System.out.print("{"+iData+","dData+"}");
}
}

//another class of methods

class DoubleEndList {
private Link first;
private Link last;


public DoubleEndList() {
first = null;
last = null;
}
public boolean isEmpty() {
return (first == null);
}

//insertion method at first
public void insertFirst(int id,double dd) {
Link newLink = new Link(id,dd);

if (isEmpty ())
last = newLink;
newLink.next = first;

first = newLink;
}
//insertion method at last
public void insertLast(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}


//deletion of the first node
public Link deleteFirst(int id,double dd) {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

//deletion the last node
public Link deleteLast(int id, double dd){
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}

//for displaying elements
public void displayList(){
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null){
current.displayLink();
current=current.next;

}
}
System.out.println(" ");
}
}

//the main class

public class DoubleEndApp{
public static void main(String[] args) {

DoubleEndList theList = new DoubleEndList();

//application of the insertion methods on the first and the last
theList.insertFirst(44,87);
theList.insertFirst(56,09);
theList.insertLast(07,85);
theList.insertLast(788,02);

System.out.println(theList);

//for deletion
theList.deleteFirst();
theList.deleteFirst();
System.out.println(theList);
}
}
references:

my.safaribooksonline.com/
www-personal.umich.edu/~williams/archive/forth/lists/index.html

STACK

Definition:

• is an abstract data type and data structure based on the principle of Last In First out (LIFO).
• are used extensively at every level of a modern computer system.
• s a container of nodes and has two basic operations: push and pop. Push adds a given node to the top of the stack leaving previous nodes below. Pop removes and returns the current top node of the stack.  [1.] [en.wikipedia.org/wiki/Stack_(data_structure)]

      The key methods of the Stack class are push(), peek(), pop(), empty() and search():
            push() - adds an element to the top of the stack.
            peek() - returns the first element from the top of the stack without removing it from the                                stack.
            pop() - as peek() but removes it from the stack.
            empty() - checks wheter there are elements in the stack or not

            search() - returns the position of an element in the stack. [2.] http://www.javadb.com/using-                                 a-stack

Illustration:

This figure is a representation of stack from [1.] http://en.wikipedia.org/wiki/Stack_(data_structure)

references:

[1.] http://en.wikipedia.org/wiki/Stack_(data_structure)

[2.] http://www.javadb.com/using-a-stack