Stack Code Implementation

/* Programmer: Pauline Vernadeth Magno
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;


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() {
return (first == null);
}

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

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

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

public void displayList
{
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 Illustration

Double-ended Illustration

Doubly Linked list

A:Concept/Definition:

••a doubly linked list is not an abstract data type, but only an implementation type. This fact does not prevent doubly linked lists from being extremely useful, however.

As with simply linked lists, we assume that the elements on the list are in the form of pointers, so that we respect uniform reference semantics. There is another application that makes it a "doubly linked list" [TUTORIALS]

••its because it has a pointer or reference to the previous e link, thus it makes it more complicated but at least, you can go back to the previous list, unlike in a Singly linked list.

B:Illustration:

C: Java Code:

//constructor class

class Link {

public int iData;

public Link next;

public Link previous;

public Link(int id) {

iData = id;

}

public String toString() {

return "{" + iData + "} ";

}

}

//a class that has the methods or operation of doubly linked list

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;

}

public String toString() {

String str = "List (first-->last): ";

Link current = first;

while (current != null) {

str += current.toString();

current = current.next;

}

System.out.println("");

System.out.print("List (last-->first): ");

current = last;

while (current != null) {

str += current.toString();

current = current.previous;

}

return str;

}

}

//main class that executes the operation on the doubly linked lists

public class MainClass {

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);

}

}

D:References:

http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/MTP/Common/Strandh-Tutorial/double-list.html

[TUTORIALS]

Double Ended Lists

A) Definition/Concept:

A double ended list has references to the first and last element of the linked list. It will be easy for the insertion and deletion operations because there is an access to the first and last element of the list..

[JAVA_TUTORIALS]

B) Illustration:

C) Code:

Double-Ended Lists: list with first and last references

//constructor
class Link {
public int iData;

public Link next;

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

public String toString() {
return "{" + iData + "} ";
}
}

//methods/operations of a double ended

class FirstLastList {
private Link first;
private Link last;

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

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

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

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

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

public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

//main class/application of the methods
public class MainClass {
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();

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.deleteFirst();

System.out.println(theList);
}
}

References:

[JAVA_TUTORIALS]

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

IT123A0809

Stack

A.Definition/Concept

Stack an abstract data type and data structure based on LIFO or the Last In First Out. It is used extensively at every level of modern computer system. Example of this, a modern PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls.[wiki]

B. Illustration

C. References

 [1]  http://en.wikipedia.org/wiki/File:Data_stack.svg
 [2] http://en.wikipedia.org/wiki/Stack_(data_structure)