Bubble sort
Definition:
It is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.
Run-time complexity Analysis:
♥ This is observing through the first two elements then swap the lesser to greater.
♥ Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with the substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.
Codes:
procedure bubbleSort( A : list of sortable items ) defined as:
do
swapped := false
for each i in 0 to length(A) - 2 inclusive do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end procedure
Application:
♥ For example, swapping the height of the participants of the running event.
Reference:
http://en.wikipedia.org/wiki/Bubble_sort
Monday, April 6, 2009
Heapsort
Definition:
It is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort.
It is a much more efficient version of selection sort.
It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called aheap, a special type of binary tree.
Once the data list has been made into a heap, the root node is guaranteed to be the largest element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.
Run-time Complexity Analysis:
♥ It has the advantage of a worst-case Θ(n log n) runtime. It is an in-place algorithm, but is not a stable sort.
Codes:
function heapSort(a, count) is
input: an unordered array a of length count
(first place a in max-heap order)
heapify(a, count)
end := count - 1
while end > 0 do
(swap the root(maximum value) of the heap with the last element of the heap)
swap(a[end], a[0])
(decrease the size of the heap by one so that the previous max value will
stay in its proper placement)
end := end - 1
(put the heap back in max-heap order)
siftDown(a, 0, end)
function heapify(a,count) is
(start is assigned the index in a of the last parent node)
start := (count - 2) / 2
while start ≥ 0 do
(sift down the node at index start to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count-1)
start := start - 1
(after sifting down the root all nodes/elements are in heap order)
function siftDown(a, start, end) is
input: end represents the limit of how far down the heap
to sift.
root := start
while root * 2 + 1 ≤ end do (While the root has at least one child)
child := root * 2 + 1 (root*2+1 points to the left child)
(If the child has a sibling and the child's value is less than its sibling's...)
if child + 1 ≤ end and a[child] < a[child + 1] then
child := child + 1 (... then point to the right child instead)
if a[root] < a[child] then (out of max-heap order)
swap(a[root], a[child])
root := child (repeat to continue sifting down the child now)
else
return
Application:
♥ Comparing the array of numbers in a sorted list.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Heapsort
Definition:
It is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort.
It is a much more efficient version of selection sort.
It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called aheap, a special type of binary tree.
Once the data list has been made into a heap, the root node is guaranteed to be the largest element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.
Run-time Complexity Analysis:
♥ It has the advantage of a worst-case Θ(n log n) runtime. It is an in-place algorithm, but is not a stable sort.
Codes:
function heapSort(a, count) is
input: an unordered array a of length count
(first place a in max-heap order)
heapify(a, count)
end := count - 1
while end > 0 do
(swap the root(maximum value) of the heap with the last element of the heap)
swap(a[end], a[0])
(decrease the size of the heap by one so that the previous max value will
stay in its proper placement)
end := end - 1
(put the heap back in max-heap order)
siftDown(a, 0, end)
function heapify(a,count) is
(start is assigned the index in a of the last parent node)
start := (count - 2) / 2
while start ≥ 0 do
(sift down the node at index start to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count-1)
start := start - 1
(after sifting down the root all nodes/elements are in heap order)
function siftDown(a, start, end) is
input: end represents the limit of how far down the heap
to sift.
root := start
while root * 2 + 1 ≤ end do (While the root has at least one child)
child := root * 2 + 1 (root*2+1 points to the left child)
(If the child has a sibling and the child's value is less than its sibling's...)
if child + 1 ≤ end and a[child] < a[child + 1] then
child := child + 1 (... then point to the right child instead)
if a[root] < a[child] then (out of max-heap order)
swap(a[root], a[child])
root := child (repeat to continue sifting down the child now)
else
return
Application:
♥ Comparing the array of numbers in a sorted list.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Heapsort
Insertion sort
Definition:
It is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time.
It is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms.
It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one.
Run-time Complexity Analysis:
♥ This is efficient and sequential.
Codes:
insertionSort(array A)
begin
for i := 1 to length[A]-1 do
begin
value := A[i];
j := i-1;
while j ≥ 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j-1;
end;
A[j+1] := value;
end;
end;
Application:
Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort
Definition:
It is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time.
It is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms.
It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one.
Run-time Complexity Analysis:
♥ This is efficient and sequential.
Codes:
insertionSort(array A)
begin
for i := 1 to length[A]-1 do
begin
value := A[i];
j := i-1;
while j ≥ 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j-1;
end;
A[j+1] := value;
end;
end;
Application:
Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort
Shell sort
Definition:
Invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time.
It is a sorting algorithm that is a generalization of insertion sort, with two observations:
insertion sort is efficient if the input is "almost sorted", and
insertion sort is typically inefficient because it moves values just one position at a time.
Run-time Complexity Analysis:
♥ This is an effective in terms of the efficiency of the sorted list.
Codes:
input: an array a of length n
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)
Application:
♥ Sorting the numbers in a certain row.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Shell_sort
Definition:
Invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time.
It is a sorting algorithm that is a generalization of insertion sort, with two observations:
insertion sort is efficient if the input is "almost sorted", and
insertion sort is typically inefficient because it moves values just one position at a time.
Run-time Complexity Analysis:
♥ This is an effective in terms of the efficiency of the sorted list.
Codes:
input: an array a of length n
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)
Application:
♥ Sorting the numbers in a certain row.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Shell_sort
Merge Sort
Definition:
An 0(n log n) comparison-based sorting algorithms.
In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output.
It is an example of the divide and conquer algorithmic paradigm.
It was invented by John von Neumann in 1945.
Run-time Complexity Analysis:
♥ Efficient and effective
Code:
function merge_sort(m)
var list left, right, result
if length(m) ≤ 1
return m
// This calculation is for 1-based arrays.
For 0-based, use length(m)/2 - 1.
var middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
Application:
♥ Merging a bundle of something like sticks and other.
Reference:
en.wikipedia.org/wiki/Merge_sort
http://en.wikipedia.org/wiki/Sorting_algorithm#Merge_sort
Definition:
An 0(n log n) comparison-based sorting algorithms.
In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output.
It is an example of the divide and conquer algorithmic paradigm.
It was invented by John von Neumann in 1945.
Run-time Complexity Analysis:
♥ Efficient and effective
Code:
function merge_sort(m)
var list left, right, result
if length(m) ≤ 1
return m
// This calculation is for 1-based arrays.
For 0-based, use length(m)/2 - 1.
var middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
Application:
♥ Merging a bundle of something like sticks and other.
Reference:
en.wikipedia.org/wiki/Merge_sort
http://en.wikipedia.org/wiki/Sorting_algorithm#Merge_sort
Quick sort
Definition:
It is a well-known sorting algorithm developed by C.A.H Hoare.
It is a divide and conquer algorithm. It relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time andin-place We then recursively sort the lesser and greater sublists.
Run-time Complexity Analysis:
♥ this is performed through finding its pivot and sort it.
♥ typically unstable and somewhat complex but among the fastest sorting algorithms.
Codes:
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
Application:
finding the pivot of a given example and then sort it.
Reference:
http://en.wikipedia.org/wiki/Quicksort
Definition:
It is a well-known sorting algorithm developed by C.A.H Hoare.
It is a divide and conquer algorithm. It relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time andin-place We then recursively sort the lesser and greater sublists.
Run-time Complexity Analysis:
♥ this is performed through finding its pivot and sort it.
♥ typically unstable and somewhat complex but among the fastest sorting algorithms.
Codes:
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
Application:
finding the pivot of a given example and then sort it.
Reference:
http://en.wikipedia.org/wiki/Quicksort
Bucket Sort
Definition:
It is also called bin sort.
It is a sorting algorithm that works by partitioning it into a number of buckets. Each bucket is then sorted individually using the different sorting algorithm, or by recursively applying the bucket sorting algorithm.
Bucket sort works as follows:
Set up an array of initially empty "buckets."
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.
Run-time Complexity Analysis:
♥ efficient and effective in sorting the list.
Codes:
function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]
Application:
♥ Given an array, put the array of numbers in a bucket where they must be placed then sort the list.
Reference:
commons.wikimedia.org/wiki/File:Bucket_sort_2.png
http://en.wikipedia.org/wiki/Bucket_sort
Definition:
It is also called bin sort.
It is a sorting algorithm that works by partitioning it into a number of buckets. Each bucket is then sorted individually using the different sorting algorithm, or by recursively applying the bucket sorting algorithm.
Bucket sort works as follows:
Set up an array of initially empty "buckets."
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.
Run-time Complexity Analysis:
♥ efficient and effective in sorting the list.
Codes:
function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]
Application:
♥ Given an array, put the array of numbers in a bucket where they must be placed then sort the list.
Reference:
commons.wikimedia.org/wiki/File:Bucket_sort_2.png
http://en.wikipedia.org/wiki/Bucket_sort
Bucket Sort
Definition:
It is also called bin sort.
It is a sorting algorithm that works by partitioning it into a number of buckets. Each bucket is then sorted individually using the different sorting algorithm, or by recursively applying the bucket sorting algorithm.
Bucket sort works as follows:
Set up an array of initially empty "buckets."
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.
Run-time Complexity Analysis:
♥ efficient and effective in sorting the list.
Codes:
function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]
Application:
♥ Given an array, put the array of numbers in a bucket where they must be placed then sort the list.
Reference:
commons.wikimedia.org/wiki/File:Bucket_sort_2.png
http://en.wikipedia.org/wiki/Bucket_sort
Definition:
It is also called bin sort.
It is a sorting algorithm that works by partitioning it into a number of buckets. Each bucket is then sorted individually using the different sorting algorithm, or by recursively applying the bucket sorting algorithm.
Bucket sort works as follows:
Set up an array of initially empty "buckets."
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.
Run-time Complexity Analysis:
♥ efficient and effective in sorting the list.
Codes:
function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]
Application:
♥ Given an array, put the array of numbers in a bucket where they must be placed then sort the list.
Reference:
commons.wikimedia.org/wiki/File:Bucket_sort_2.png
http://en.wikipedia.org/wiki/Bucket_sort
Thursday, March 12, 2009
Code Implementation of Queue
/* Programmer’s name: Chrisdyll Pellejo
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 Courses Offered in the College
//class constructor
class Queue{
public int coursenum;
public String coursename;
public int unitnum;
public String deptname;
public Queue next;
public Queue (int Cnum, String Cname, int Unum, String Dname; )
{
coursenum=Cnum;
coursename=Cname;
unitnum=Unum;
deptname=Dname;
}
//displaying the elements on the list
public void displayQueue()
{
System.out.print(coursenum +” “ + deptname +” “ +” “+unitnum+ “ “ +: + coursename)
}
}
/*a separate class which contains the ,methods that would be used in implementing the program */
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 Cnum, String Cname, int Unum, String Dname; )
{
Queue newQueue= new Queue (int Cnum, String Cname, int Unum, String Dname )
if( isEmpty())
last = newQueue;
newQueue.next=first;
first=newQueue;
}
//deleting an element on the queue
public void Dequeue (int Cnum)
{
Queue newQueue=new Queue (int Cnum, String Cname, int Unum, String Dname )
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, “BSIT”, 118, “ICSD” )
theQueue.enqueue(2, “BSN”, 368, “ND”);
System.out.println(theQueue);
theQueue.dequeue(2);
System.out.println(theQueue);
System.out.println(theQueue);
}
}
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 Courses Offered in the College
//class constructor
class Queue{
public int coursenum;
public String coursename;
public int unitnum;
public String deptname;
public Queue next;
public Queue (int Cnum, String Cname, int Unum, String Dname; )
{
coursenum=Cnum;
coursename=Cname;
unitnum=Unum;
deptname=Dname;
}
//displaying the elements on the list
public void displayQueue()
{
System.out.print(coursenum +” “ + deptname +” “ +” “+unitnum+ “ “ +: + coursename)
}
}
/*a separate class which contains the ,methods that would be used in implementing the program */
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 Cnum, String Cname, int Unum, String Dname; )
{
Queue newQueue= new Queue (int Cnum, String Cname, int Unum, String Dname )
if( isEmpty())
last = newQueue;
newQueue.next=first;
first=newQueue;
}
//deleting an element on the queue
public void Dequeue (int Cnum)
{
Queue newQueue=new Queue (int Cnum, String Cname, int Unum, String Dname )
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, “BSIT”, 118, “ICSD” )
theQueue.enqueue(2, “BSN”, 368, “ND”);
System.out.println(theQueue);
theQueue.dequeue(2);
System.out.println(theQueue);
System.out.println(theQueue);
}
}
Sunday, February 15, 2009
Stack (Java Code Implementation)
/* Programmer: Chrisdyll P. Pellejo
Program name: A Stack Code Implementation
Purpose: To implement a Stack Code.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures*/
//a class which declares the variables and the constructors
class Link{
public int iData=0;//data item
public Link(int iData, ) //constructor
{
iData=id;
}
public void displayLink() //displaying the data
{
System.out.println(iData+":" );
}
}
//the class which contains the methods or the operations on the stack
class StackList{
private Link first;
public StackList(){ //declaring the list as empty or null
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();
}
}
Program name: A Stack Code Implementation
Purpose: To implement a Stack Code.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures*/
//a class which declares the variables and the constructors
class Link{
public int iData=0;//data item
public Link(int iData, ) //constructor
{
iData=id;
}
public void displayLink() //displaying the data
{
System.out.println(iData+":" );
}
}
//the class which contains the methods or the operations on the stack
class StackList{
private Link first;
public StackList(){ //declaring the list as empty or null
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();
}
}
Saturday, February 14, 2009
Doubly-Linked Lists
Concept/Definition:
"a doubly linked list is not an abstract data type, but only an implementation type".[TUTORIAL_DOUBLY]
"a doubly linked list is not an abstract data type, but only an implementation type".[TUTORIAL_DOUBLY]
Double-linked lists require more space per node and their elementary operations are more expensive but they are often easier to manipulate because they allow sequential access to the list in both directions. In particular, one can insert or delete a node in a constant number of operations given only that node's address. [WIKI].
As what I Have Learned in our class..
doubly linked lists are complicated because there is another feature which is the "previous" in such you can access to the previous link. In inserting or deleting a node, you have to keep track of the four pointers: "2 next and 2 previous" pointers.
Code Implementation:
/* Programmer: Chrisdyll P. Pellejo
Program name: A Doubly-Linked List
Purpose: To implement a doubly linked list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures
*/
Program name: A Doubly-Linked List
Purpose: To implement a doubly linked list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures
*/
//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 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 + "} ";
}
}
return "{" + iData + "} ";
}
}
/*another class which contains the methods for the program*/
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;
}
}
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;
}
}
/*another class which is the main that applies all of the methods*/
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);
}
}
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:
[TUTORIAL_DOUBLY]
[WIKI]
Sunday, February 8, 2009
A Double Ended List
Illustration
Concept/Definition:
♥♥ In going through the concept of a double ended Linked List, you must first understand the full concept of a singly linear linked list since it is so much connected with one another.♥♥The concept of a double ended List is that it has access to the first and last element of the nodes of a Linked List. "Double ended lists allow for insertions in the front or in the back of the list. Each type of link list will build off of the previous one. First we'll examine the singly linked list before moving onto the double-ended and doubly linked lists. "[SAFARI_BOOKS]
What I Have Learned in our class
....as what Iv'e also learned in our class, it is very important that a linked list should be always connected with one another because once it losses access to the other, it can never be back again since the java garbage collector would erase it immediately......i would really advice that all the nodes of the list should be connected so that it would always be in the list or else!!! say goodbye to the list...
Code Implementation
/* Programmer: Chrisdyll P. Pellejo
Program name: A Double Ended List
Purpose: To implement a double ended list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures
*/
/*a class that contains the constructor*/
class Link {
public int iData;
public double dData:
public Link next;
public Link(int id,double dd) {
iData = id;
dData=dd;
}
//displaying the elements in the list
public void displayLink(){
System.out.print("{"+iData+","dData+"}");
}
}
/*another class which contains the methods*/
class DoubleEndList {
private Link first;
private Link last;
public DoubleEndList() {
first = null;
last = null;
}
//testing if the the list has elements or if it is null
public boolean isEmpty() {
return (first == null);
}
//inserting a node to be the first element
public void insertFirst(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty ())
last = newLink;
newLink.next = first;
first = newLink;
}
//inserting a node on the last part
public void insertLast(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}
//deleting the first node on the list
public Link deleteFirst(int id,double dd) {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
//deleting the last node of the list
public Link deleteLast(int id, double dd){
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}
//display the elements on the list
public void displayList(){
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null){
current.displayLink();
current=current.next;
}
}
System.out.println(" ");
}
}
/*another class for the application of the program.
Or it is formally called 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(12,25);
theList.insertFirst(2,45);
theList.insertFirst(67,89);
theList.insertLast(1,99);
theList.insertLast(243,33);
theList.insertLast(234,90);
//displaying the elements on the node
System.out.println(theList);
//deletion operation on the first and last element on the list
theList.deleteFirst();
theList.deleteFirst();
System.out.println(theList);
}
}
Reference:
[SAFARI_BOOKS] http://my.safaribooksonline.com/30000LTI00162/ch05lev1sec2
Concept/Definition:
♥♥ In going through the concept of a double ended Linked List, you must first understand the full concept of a singly linear linked list since it is so much connected with one another.♥♥The concept of a double ended List is that it has access to the first and last element of the nodes of a Linked List. "Double ended lists allow for insertions in the front or in the back of the list. Each type of link list will build off of the previous one. First we'll examine the singly linked list before moving onto the double-ended and doubly linked lists. "[SAFARI_BOOKS]
What I Have Learned in our class
....as what Iv'e also learned in our class, it is very important that a linked list should be always connected with one another because once it losses access to the other, it can never be back again since the java garbage collector would erase it immediately......i would really advice that all the nodes of the list should be connected so that it would always be in the list or else!!! say goodbye to the list...
Code Implementation
/* Programmer: Chrisdyll P. Pellejo
Program name: A Double Ended List
Purpose: To implement a double ended list.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures
*/
/*a class that contains the constructor*/
class Link {
public int iData;
public double dData:
public Link next;
public Link(int id,double dd) {
iData = id;
dData=dd;
}
//displaying the elements in the list
public void displayLink(){
System.out.print("{"+iData+","dData+"}");
}
}
/*another class which contains the methods*/
class DoubleEndList {
private Link first;
private Link last;
public DoubleEndList() {
first = null;
last = null;
}
//testing if the the list has elements or if it is null
public boolean isEmpty() {
return (first == null);
}
//inserting a node to be the first element
public void insertFirst(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty ())
last = newLink;
newLink.next = first;
first = newLink;
}
//inserting a node on the last part
public void insertLast(int id,double dd) {
Link newLink = new Link(id,dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}
//deleting the first node on the list
public Link deleteFirst(int id,double dd) {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
//deleting the last node of the list
public Link deleteLast(int id, double dd){
int temp=last.iData;
if(last.next==null)
first=null;
last=last.next;
return temp;
}
//display the elements on the list
public void displayList(){
System.out.print("List(first-->Last);");
Link current=first;
while(current!=null){
current.displayLink();
current=current.next;
}
}
System.out.println(" ");
}
}
/*another class for the application of the program.
Or it is formally called 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(12,25);
theList.insertFirst(2,45);
theList.insertFirst(67,89);
theList.insertLast(1,99);
theList.insertLast(243,33);
theList.insertLast(234,90);
//displaying the elements on the node
System.out.println(theList);
//deletion operation on the first and last element on the list
theList.deleteFirst();
theList.deleteFirst();
System.out.println(theList);
}
}
Reference:
[SAFARI_BOOKS] http://my.safaribooksonline.com/30000LTI00162/ch05lev1sec2
STACK DATA STRUCTURE
Illustration of the stack data structure [WIKI]
Definition/Concept
Stack is an abstract data type and data structure. It’s principle is a LIFO (w/c means last in first out). Among other uses, stacks are used to run a Java Virtual Machine, and the Java language itself has a class called "Stack", which can be used by the programmer. "The stack is ubiquitous."
Stack is an abstract data type and data structure. It’s principle is a LIFO (w/c means last in first out). Among other uses, stacks are used to run a Java Virtual Machine, and the Java language itself has a class called "Stack", which can be used by the programmer. "The stack is ubiquitous."
[WIKI]
The meaning of ubiquitous is that it is omnipresent or present everywhere. "It also means universal." [blurtit.com]
How do we connect a stack data structure in a real world representation??
In connecting a stack data structure in areal worls representation, just imagine pingpong balls put into a straight glass tube or your plates at home being arranged vertically or just a pile of hollowblocks. If you could really imagine, the first thing that you put on your pile is the last thing you could pull out and the last thing you put is the first that you could pull out. That is the concept of a stack..
In connecting a stack data structure in areal worls representation, just imagine pingpong balls put into a straight glass tube or your plates at home being arranged vertically or just a pile of hollowblocks. If you could really imagine, the first thing that you put on your pile is the last thing you could pull out and the last thing you put is the first that you could pull out. That is the concept of a stack..
..in our class discussion for the stack data structure, pop is the same as deletion and push is just the same with inserting and you cannot cheat on this kind of structure, you really have to go through it's method of deleting elements.♥♥♥♥
..iv'e also learned about different stack operations:
•isEmpty()//checking if the list is empy or null
•push() //the same as insertion operation
•pop() //the same as deletion operation
•top() //operation that will determine the top element of the list but will not delete it
Reference:
[WIKI] http://en.wikipedia.org/wiki/Stack_(data_structure)
[WIKI] http://en.wikipedia.org/wiki/Stack_(data_structure)
[blurtit.com] http://www.blurtit.com/q122638.html
Subscribe to:
Posts (Atom)
