Algorithm

http://en.wikipedia.org/wiki/Algorithm
http://en.wikipedia.org/wiki/Analysis_of_algorithms

Hashing

http://www.palfrader.org/hashing/
http://www.cs.bu.edu/teaching/cs113/spring-2000/hash/

Sorting

http://en.wikipedia.org/wiki/Sorting_algorithm

Code Implementation of Queue

/* Programmer’s name: Marjorie Egot
Name of Program: Queue implementation
Date Started: March 9, 2009
Date Finished : March 12, 2009
Instructor : Mr. Dony Dongiapon
Course: IT 123: Data Structures
Objective: To be able to make a program that implements a queue data structure in a linked list
*/



Concept: List of Barangay Councilor Officials

//declaration of a constructor
class Queue{
public int positionnum;
public String firstname;
public String lastname;
public char middlename;
public Queue next;

public Queue (int Pnum, String Fname String Lname char M, )
{

positionnum=Pnum;
firstname=Fname;
lastname=Lname;
middlename=M;
}


//displaying the elements on the queue
public void displayQueue()
{
System.out.print(positionnum +” “ + firstname +” “ +” “middlename+ “ “ +: + lastname)
}
}


/*a separate class which has the methods to be used by the queue implemented in a linked list*/
class QueueList
private Queue first;
private Queue last;
public QueueList()
{
first=null;
last=null;
}


//checking if the queue has elements
public Boolean isEmpty()
{
return (first==null);
}



//inserting an element on the queue
public void Enqueue(int Pnum, String Fname String Lname char M, )

{
Queue newQueue= new Queue (int Pnum, 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 Pnum)
{
Queue newQueue=new Queue (int Pnum, String Fname String Lname char M, )

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(1, “Marjorie”, “Egot”, ‘T’ )

theQueue.enqueue(2, “Chrisdyll”, “Pellejo”, ‘P’)
System.out.println(theQueue);

theQueue.enqueue(3, “Julie”, “Pabio”, ‘L’)
System.out.println(theQueue)



theQueue.dequeue(3);

System.out.println(theQueue);



System.out.println(theQueue);
}
}

These are references where you can learn codes:
Just click it. =)

http://www.java2s.com/Tutorial/Java/0140__Collections/Adoublylinkedlist.htm

http://www.java2s.com/Tutorial/Java/0140__Collections/DoubleEndedListslistwithfirstandlastreferences.htm

http://www.java2s.com/Tutorial/Java/0140__Collections/Demonstratingastackimplementedasalist.htm

http://www.java2s.com/Tutorial/Java/0140__Collections/AQueueImplementedbyaLinkedList.htm

Stack (Code Implementation)

/* Programmer: Marjorie T. Egot
Program name: A Stack code Implementation
Purpose: To implement a stack data stucture
Instructor: Dony Dongiapon
Subject: IT123 Data Structures
*/

//a class which declares the variables and the constructors
class Link{
public int iData=0;


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

}

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

//the class which contains the methods or the operations on the stack
class StackList{
private Link first;

public StackList(){
first=null;

}

public boolean isEmpty() { //checking if the list is empty or not
return (first == null);
}

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

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

public Link pick() //determining the top of the list but doing nothing with it
{
Link temp=first;
return temp;
}

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

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

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

theList.insertFirst(12);
theList.insertFirst(25);
theList.insertFirst(91);

//when deleting
//just erase the comment if you want to run the method of deletion
theList.deleteFirst();

//when displaying the element
theList.displayList();
}
}

Doubly Linked List
February 16, 2009

Concept/Definition:

A more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each node has two links: one points to the previous node, or points to a null value or empty list if it is the first node; and one points to the next, or points to a null value or empty list if it is the final node.

[wiki]

♥ As what I have learned, you can access the link before or after a node since they are connected with each other. You have the previous and the next links which are its feature. It's complicated since you have to deal with the 4 pointers.

Illustration:

This is taken from the given example of our instructor.


Code Implementation:

/* Programmer: Marjorie T. Egot
Program name: A Doubly Linked List
Purpose: To implement a doubly linked list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structure */

//constructor
class Link
{
public int iData; //data item
public Link next; //next link in the list
public Link previous; //previous link in the list
public Link(int id)
{
iData = id;
}

//display the elements in the list
public void displayList()
{
return "{" + iData + "} ";
}
}

//another class which contains the methods
class DoublyLinkedList
{
private Link first;
private Link last;

public DoublyLinkedList()
{
first = null;
last = null;
}

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

public void insertFirst(int dd)
{
Link newLink = new Link(dd);

if (isEmpty())
{
last = newLink;
}else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}

public void insertLast(int dd)
{
Link newLink = new Link(dd);
if (isEmpty())
{
first = newLink;
}else{
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}

public Link deleteFirst()
{
Link temp = first;
if(first.next == null)
{
last = null;
}else{
first.next.previous = null;
}
first = first.next;
return temp;
}

public Link deleteLast()
{
Link temp = last;
if(first.next == null)
{
first = null;
}else{
last.previous.next = null;
}
last = last.previous;
return temp;
}

public boolean insertAfter(int key, int dd)
{
Link current = first;
while (current.iData != key)
{
current = current.next;
if (current == null)
{
return false;
}
}
Link newLink = new Link(dd);
if (current == last)
{
newLink.next = null;
last = newLink;
}else{
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}

public Link deleteKey(int key)
{
Link current = first;
while (current.iData != key)
{
current = current.next;
if (current == null)
return null;
}
if (current == first)
{
first = current.next;
}else{
current.previous.next = current.next;
}
if (current == last)
{
last = current.previous;
}else{
current.next.previous = current.previous;
}
return current;
}
}

// the main method
public class DoublyLinkedApp
{
public static void main(String[] args)
{
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
System.out.println(theList);

theList.insertAfter(22, 77);
theList.insertAfter(33, 88);
System.out.println(theList);
}
}

References:

• [wiki] http://en.wikipedia.org/wiki/Linked_list