Double Ended Link List

illustration




code

class Link {
public int iData;

public Link next;

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

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

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 method
public class Deli {
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);
}
}

Doubly Link List

Concept

According to National Institute of Standards and Technology
*a list in which each item has a link to the previous item as well as the next. This allows an accessing items backward, forward and deleting an item in a constant time.

[ ANIST ]

*each node has 2 pointers, one to the next and the other to the previous and the end is defined by NULL. With the doubly link list , we can move the current pointer backward and forward .

Illustration

Reference:
http://richardbowles.tripod.com/cpp/linklist/doublist.htm

implementation of doubly Link List

class Link {
public int iData;
public Link next;
public Link previous;

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

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

class DoublyLinkedList {
private Link first;
private Link last;

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

public boolean isEmpty() {
return first == null;
}
//insertion
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;
}
//deletion
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 method
public class MainClass {
public static void main(String[] args) {
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(lovely);
theList.insertFirst(matet);
theList.insertFirst(tina);

theList.insertLast(nemz);
theList.insertLast(nellen);
theList.insertLast(jeany);

System.out.println(theList);

theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(nemz);

System.out.println(theList);

theList.insertAfter(lovely, jerrold);
theList.insertAfter(nellen, baste);

System.out.println(theList);
}
}

reference:

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

Stack(Data Stucture)

Concept

According to wikipedia

- a stack is an abstack data type and its based on the principle of Last In First Out(LIFO).
-stacks are used to run a Java Virtual Machine.
-it is ubiquitous
a stack-based computer system
-one that stores temporary information

history of stack
-it was first proposed on 1995 and the patented in 1957 by Friedrich L. Bauer.

as an Abstact data Type
-the stack is a container of nodes and has basic operations.

Basic Operations
Push-adds a given node to the top and leaving previous nodes below.
Pop- removes and returns the current top node of the stack.
top(peek)- can return the current top element without removing it from the stack.

a typical stack is an area of a computer memory with a fixed origin and a variable size. The size of the stack is zero. A stack pointer ,usually in the form of a hardware registers.

some environments
*Dup(licate)- the top item is popped and pushed again.
*peek- the topmost item is popped, but the stack pointer is not change.
*Swap or exchange- the two topmost items on the stack exchange places.
*rotate- the topmost items are moved on the stack in a rotating fashion.

[1]
Illustration

[2]

[3]

implementation of stack using link list

class Link {
public int iData;

public Link next;

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

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

class LinkList {
private Link first;

public LinkList() {
first = null;
}

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

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

public int deleteFirst() {
Link temp = first;
first = first.next;
return temp.iData;
}

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

class LinkStack {
private LinkList theList;

public LinkStack() {
theList = new LinkList();
}

public void push(int j) {
theList.insertFirst(j);
}

public double pop() {
return theList.deleteFirst();
}

public boolean isEmpty() {
return (theList.isEmpty());
}

public String toString() {
return theList.toString();
}
}
//main method
public class Stack{
public static void main(String[] args) {
LinkStack theStack = new LinkStack();

theStack.push(me);
theStack.push(you);

System.out.println(theStack);

theStack.push(and you);
theStack.push(they);

System.out.println(theStack);

theStack.pop();
theStack.pop();

System.out.println(theStack);
}
}

[4]
reference::

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

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

[3]http://en.wikipedia.org/wiki/Stack_(data_structure)
[4]http://www.java2s.com/Tutorial/Java/0140__Collections/Demonstratingastackimplementedasalist.htm