Design Pattern: Strategy

 Strategy pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. It lets the algorithm vary independently from clients that use it.

Strategy Design Pattern
Strategy Design Pattern

Abstract Class: Duck.java

We create objects  after sub classing it into a concrete class from an abstract type. In our case, is the Duck Class. This provides the basis for all the XxxDuck objects that are created. Two things to be mentioned;

  1. We are programming the different “behavior” to an interface. And this could be an abstract class as well. References to these instance variables are provided as instance variables in the Class Definition.
  2. Public “Setters” are provided so that the behavior of the object can be set or changed dynamically as shown in this example.
package com.npk.strategy;

public abstract class Duck {

FlyBehavior flyBehavior;
QuackBehavior quackBehavior;

public abstract void display();

public void setFlyBehavior(FlyBehavior flyBehavior){
this.flyBehavior = flyBehavior;
}

public void setQuackBehavior(QuackBehavior quackBehavior){
this.quackBehavior = quackBehavior;
}

public void performFly(){
flyBehavior.fly();
}

public void performQuack(){
quackBehavior.quack();
}

public void performSwim(){
System.out.println("All ducks can swim!");
}
}

Interface: FlyBehavior.java and QuackBehavior.java

Any variable behavior of an object are to be programmed to an interface.
This way, you get two things:

  1. Compostion
  2. Loosely coupled objects.

Both of which are good OO Designs aspects.


package com.npk.strategy;

public interface FlyBehavior {

public void fly();
}

package com.npk.strategy;

public interface QuackBehavior {

public void quack();
}

Concrete Implementation: DummyDuck.java

We subclass the abstract Duck class to get a concrete DummyDuck class where we can set the behavior in the class constructor ( optional )


package com.npk.strategy;

public class DummyDuck extends Duck {

public DummyDuck(){
this.setFlyBehavior(new FlyNoWay());
this.setQuackBehavior(new SquekQuack());
}

@Override
public void display() {
System.out.println("This is a dummy duck.");

}

}

Concrete classes: FlyNoWay.java and SquekQuack.java

These form the actual implementation of the FlyBehavior and the QuackBehavior interfaces respectively.


package com.npk.strategy;

public class FlyNoWay implements FlyBehavior {

@Override
public void fly() {
System.out.println("Cannot fly.");

}

}

package com.npk.strategy;

public class SquekQuack implements QuackBehavior {

@Override
public void quack() {
System.out.println("Duck squeking.");

}

}

The Application Launcher We show two things here.

  1. Setting the behavior using the constructor.
  2. Changing the set behavior using the setters provided.

package com.npk.strategy;

public class Launcher {

public static void main(String[] args) {
Duck duck = new DummyDuck();
duck.display();
duck.performFly();
duck.performQuack();

System.out.println("---------------------");
duck.setFlyBehavior(new FlyWithWings());
duck.setQuackBehavior(new MuteQuack());

duck.performFly();
duck.performQuack();
}

}

The final output


This is a dummy duck.
Cannot fly.
Duck squeking.
---------------------
Duck flying.
Mute quack.

Design Pattern: Strategy

String Reversal in Java using StringBuffer, toCharacterArray and Recursion

Using StringBuffer Class

new StringBuffer(name).reverse().toString()

Using CharArray and StringBuilder

        public static String charReverse(String data){
		StringBuilder sb = new StringBuilder();
		char[] ca = data.toCharArray();
		
		for (int i=data.length()-1; i>=0;i--){
			sb.append(ca[i]);
		}
		return sb.toString();
	}

Using Recursion

public static String recursiveReverse(String data){
		
		if (data.length() < 2)
			return data;
		
		return recursiveReverse(data.substring(1)) + data.charAt(0);
	}

StringReversal Class

public class StringReversal {

	public static void main (String[] args){
		String name = "linuxjunkies";
		
		System.out.println("StringBuffer: " + new StringBuffer(name).reverse().toString());
		System.out.println("CharacterArray: " + charReverse(name));
		System.out.println("Recursion: " + recursiveReverse(name));
	}
	
	public static String charReverse(String data){
		StringBuilder sb = new StringBuilder();
		char[] ca = data.toCharArray();
		
		for (int i=data.length()-1; i>=0;i--){
			sb.append(ca[i]);
		}
		return sb.toString();
	}
	
	public static String recursiveReverse(String data){
		
		if (data.length() < 2)
			return data;
		
		return recursiveReverse(data.substring(1)) + data.charAt(0);
	}
}

The Output

StringBuffer: seiknujxunil
CharacterArray: seiknujxunil
Recursion: seiknujxunil
String Reversal in Java using StringBuffer, toCharacterArray and Recursion

The entire Server code in all its Glory!


import java.io.*;
import java.net.*;
import java.util.*;

public class Server {

 ArrayList clientOutputStreams;

 //String[] output;

 public class ClientHandler implements Runnable{

 BufferedReader reader;
 Socket sock;

 //constructor
 public ClientHandler(Socket clientSocket){

 try{
 sock = clientSocket;
 InputStreamReader isReader = new InputStreamReader(sock.getInputStream());
 reader = new BufferedReader(isReader);
 }catch(Exception ex){
 ex.printStackTrace();
 }
 }

 public void run(){
 String message;
 try{

 while((message = reader.readLine()) != null){
 System.out.println("Read " + message);
 tellEveryone(message);
 }
 }catch(Exception e){
 e.printStackTrace();
 }
 }

 }


 public void go(){
 clientOutputStreams = new ArrayList();


 try{
 ServerSocket serverSock = new ServerSocket(5000);

 while(true){
 Socket clientSocket = serverSock.accept();
 PrintWriter writer = new PrintWriter(clientSocket.getOutputStream());
 clientOutputStreams.add(writer);
 //writer.println(clientOutputStreams);
 Thread t = new Thread(new ClientHandler(clientSocket));
 t.start();
 System.out.println("Got a connection!");
 }

 }catch(Exception exx){
 exx.printStackTrace();
 }
 }

 public void tellEveryone(String messages){
 Iterator it = clientOutputStreams.iterator();
 while(it.hasNext()){

 try{

 PrintWriter writer = (PrintWriter) it.next();
 writer.println(messages);
 writer.flush();
 }catch(Exception e){
 e.printStackTrace();
 }
 }
 }

 public static void main(String[] args){
 new Server().go();
 }

}

The entire Server code in all its Glory!

The entire Chat Application in its glory!

import java.io.*;
import java.util.*;
import javax.swing.*;
import java.net.*;
import java.awt.*;
import java.awt.event.*;

public class Client {

	JTextArea incoming;
	JTextField outgoing;
	JButton sendbutton;

	BufferedReader reader;
	PrintWriter writer;

	Socket sock;

	public void go(){
		JFrame frame = new JFrame("Client");
		JPanel mainpanel = new JPanel();

		incoming = new JTextArea(15,50);
		incoming.setLineWrap(true);
		incoming.setWrapStyleWord(true);
		incoming.setEditable(false);

		JScrollPane qScroller = new JScrollPane(incoming);
		qScroller.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_ALWAYS);
		qScroller.setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_ALWAYS);

		outgoing = new JTextField(20);
		sendbutton = new JButton("Send");

		sendbutton.addActionListener(new SendButtonListener());

		mainpanel.add(qScroller);
		mainpanel.add(outgoing);
		mainpanel.add(sendbutton);

		setUpNetworking();

		Thread readerThread = new Thread(new IncomingReader());
		readerThread.start();

		frame.getContentPane().add(BorderLayout.CENTER, mainpanel);
		frame.setSize(400, 400);
		frame.setVisible(true);

	}

	public static void main(String[] args){

		Client client = new Client();
		client.go();
	}

	private void setUpNetworking(){

		try{

			sock = new Socket("127.0.0.1", 5000);
			InputStreamReader streamReader = new InputStreamReader(sock.getInputStream());
			reader = new BufferedReader(streamReader);
			writer = new PrintWriter(sock.getOutputStream());
			System.out.println("Networking established!!");

		}catch(IOException e){
			e.printStackTrace();
		}
	}

	public class SendButtonListener implements ActionListener{

		public void actionPerformed(ActionEvent e){
			try{
				writer.println(outgoing.getText());
				writer.flush();
			}catch(Exception ex){
				ex.printStackTrace();
			}

			outgoing.setText("");
			outgoing.requestFocus();
		}
	}

	public class IncomingReader implements Runnable{

		public void run(){
			String message;
			try{
				while((message = reader.readLine()) != null){
					System.out.println("read" + message);
					incoming.append(message + "\n");
					//incoming.setText(message + "\n");
				}
			}catch(Exception e){
				e.printStackTrace();
			}
		}
	}

}

The entire Chat Application in its glory!

A Simple Chat Server in Java using threads Part 1

The Client
———

The client side first. We import the necessary stuff  needed for this program. The java.net.* contains all
the necessary packages for the networking part. The swing and awt packages are for the GUI.

import java.io.*;
import java.util.*;
import javax.swing.*;
import java.net.*;
import java.awt.*;
import java.awt.event.*;

public class Client {

The JTextArea will be used to display all the chat proceedings in real time. The objective of this program is to have mutiple clients connect to a server and receive the information passed to them in real time. We make use of threads in this case.

JTextField is used for passing the chat comments.
JButton is ofcourse used for sending the message.

JTextArea incoming;
JTextField outgoing;
JButton sendbutton;

BufferedReader is used to buffer the inputstream from another source.
We use the PrintWriter to print to the socket. It is similar to using the system println function.

BufferedReader reader;
PrintWriter writer;

Sockets
——–
Sockets form the important part of this program. Simply put, it is an IP addreass with a port number. Now, port numbers vary from about 0 to 65535. It should be noted that the port numbers from 0 to 1023 are reserved and should not, unless for a reason, be used. In this example we will be using the port number 5000 to connect to the server.

Socket sock;

The function go()
—————–
This is the first method to be called. This does the following:
1. Sets up a GUI environment like I mentioned in previous posts.
2. Calls the setUpNetworking() function which will be explained later. Basically, it sets up the networking environment.
3. Most importantly, we start the threads, which I will explain.

public void go(){
JFrame frame = new JFrame("Client");
JPanel mainpanel = new JPanel();

incoming = new JTextArea(15,50);
incoming.setLineWrap(true);
incoming.setWrapStyleWord(true);
incoming.setEditable(false);

JScrollPane qScroller = new JScrollPane(incoming);
qScroller.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_ALWAYS);
qScroller.setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_ALWAYS);

outgoing = new JTextField(20);
sendbutton = new JButton("Send");

sendbutton.addActionListener(new SendButtonListener());

mainpanel.add(qScroller);
mainpanel.add(outgoing);
mainpanel.add(sendbutton);

setUpNetworking();

Now what this  does is set up a mainpanel which is JPanel. On it we add a JTextArea, which itself is added onto a JScrollPane as seen from the code. The different paramenters of this are set accordingly. The JButton is added and ofcourse, the ActionListener() for the button.

Thread readerThread = new Thread(new IncomingReader());
readerThread.start();

This is how a thread is created. Here we pass a new object of the class IncomingReader which implements the Runnable class, which I will explain in a moment.

frame.getContentPane().add(BorderLayout.CENTER, mainpanel);
frame.setSize(400, 400);
frame.setVisible(true);

}

These are just basic frame housekeeping stuff.

public static void main(String[] args){
Client client = new Client();
client.go();
}

The program begins here ofcourse. An object of the type client is created and the go() function is called.

private void setUpNetworking(){

try{

sock = new Socket("127.0.0.1", 5000);

This step creates a socket at the address “127.0.0.1” which is the localhost, ie, the same computer. And we select arbitary socket number of 5000. This number is known to the server.

InputStreamReader streamReader = new InputStreamReader(sock.getInputStream());

The InputStreamReader reads the bytes of data coming from the socket inputstream.

reader = new BufferedReader(streamReader);

This is then passed on to the BufferedReader object.

writer = new PrintWriter(sock.getOutputStream());

The PrintWriter object is finally responsible for putting the message onto the output stream.

System.out.println("Networking established!!");

}catch(IOException e){
e.printStackTrace();
}
}

Before I mention about the networking function, I will explain the concept of the try — catch block of code. Now, while running a code block, exceptions are bound to happen. If we know in advance, that a particular error is likely to happen at a place, we can place it in a try block. So what happens is that if any error occurs in this part will be caught by the catch() statement and then the housekeeping stuff inside the catch block executes. The whole idea of this is to make the program stop gracefully in case of an error.
We make the exception object print out the StackTrace in this case.

public class SendButtonListener implements ActionListener{

public void actionPerformed(ActionEvent e){
try{
writer.println(outgoing.getText());
writer.flush();

We push the content typed into the JTextField into the outputstream of the socket using the writer and
clear the buffer after every step.

}catch(Exception ex){
ex.printStackTrace();
}

outgoing.setText("");
outgoing.requestFocus();
}
}

Once you send the message, you clear the JTextField and then give the focus back to the JTextfield so that the user can type in agagin.

This is the ActionListener for the JButton Send.

public class IncomingReader implements Runnable{

public void run(){
String message;
try{
while((message = reader.readLine()) != null){
System.out.println("read" + message);
incoming.append(message + "\n");

}
}catch(Exception e){
  e.printStackTrace();
  }
 }
 }
}

This is an important part of the program. This class is passed into the thread as an object. This class implements the Runnable interface. Now, each time a thread is created, this class is called. For each Client object created, new copies or threads of execution of this same program is spawned from the existing main thread, which is the only case in a sequential program and they run independently of each other till they complete or the mother thread stops.

Here what we do is to read from the BufferedReader as and when it is not empty and then post in onto the console as well as onto the JTextField using the append function.

A Simple Chat Server in Java using threads Part 1

Data Structures using Java Part 11: Java Interfaces, Java Packages, Building packages, Compiling packing, Using packages

Java Interfaces
——————
Are public method prototype and behaviour. We make use of the “interface” keyword.
It is like an abstract class with two differences:
1. A class can inherit from only one class, but can “implement” as many interfaces you want.
2. A Java interface
cannot implement any methods at all.
nor cannot include any fields except “static final” constants
Only contains method prototype and constants.

//Nukeable.java
public interface Nukeable{
	public void nuke(); // no body
}

// in java.lang
public interface Comparable{
	public int compareTo(Object o);
}

public class SList extends List implements Nukeable, Comparable{
	// all that matters
	public void nuke(){
		head = null;
		size = 0;
	}
	
	public int compareTo(Object o){
		// code that retruns a number thats less than 0 if <0 and 0 if =0 and >0 if >0
	}
}

Nukeable n = new SList(); // correct!
Comparable c = (Comparable)n; // need to use a cast as some Nukeable are not Comparable
n.nuke();
if (c.compareTo > 0){
// do something
}

Arrays class in java.util sorts arrays of Comparable objects.

public static void sort(Object[] a){ }

Runtime error occurs if any item in a is not Comparable. An interface can have a subinterface and it can itself have sub interfaces.

//NOTE this!!
public interface NukeAndCompare extends Nukeable, Comparable{ }

Java Packages
—————
Package is a collection of classes, Java interfaces and subpackages.

Three benifits:
1. Packages can contain hidden classes not visible outside package.
2. Classes can have fields and methods visible inside the package only.
3. Different packages can have classes with same name.

Example: java.io standard library.

Using Packages
—————-
Fully qualified name:

java.lang.System.out.println();

import java.io.File; // can now refer to File class
import java.io.*; // refer to all things in io

Every program implicitly import java.lang.*

Also x.y.z.Classfile should be in x/y/z/Classfile.class

Building packages
——————

//list/SList.java
package list;

public class SList{
	
	SListNode head;
	int size;
}

//list/SListNode.java
package list;

class SListNode{ //"Package protection"
	Object item; //"Package protection"
	SListNode list; //"Package protection"
}

Package protection is between private and protected.

A class/variable has package protection is visible to any class in the same package.
But it is not visible at all outside the package. ie files outside that directory.
The files that are outside only see the public classes/methods inside the package.

Public class must be declared in a file named after the class. The “package” class can appear in any *.java file.

Compiling and running
———————–
Must be done from outside the package.

//How to compile?

javac -g list/SList.java
javac -g list/ *.java
javac -g heap / *.java / *.java // this takes care of dependancies also
// How to run?
java list.Slist 

The four levels of protection
——————————-

			in same package	         in a subclass	everywhere	
1. public 			x				x			x
2. protected		x				x
3. package		        x
4. private

Data Structures using Java Part 11: Java Interfaces, Java Packages, Building packages, Compiling packing, Using packages

Data Structures using Java Part 10: Inheritence, Constructors, invoking orverriden methods, protected keyword, dynamic method lookup, Abstract class


Inheritence
————-
TailList is a subclass of SList.
SList is the superclass of TailList.

A subclass can modify a superclass in three different ways:
1. It can declare new fields.
2. It can declare new methods.
3. It can override old methods with new implementations. It is not necessary to orverride all.

public class TailList extends SList{

	// the head and size is inherited

	private SListNode tail;

	// override the insertEnd method
	public void insertEnd(Object obj){
	// solution
	}

}

Inheritence and Constructors
——————————–
Java executes the TailList constructor, but first it executes SList() constructor.

public TailList(){
	//SList constructor is called

	//additional
	Tail = null;
}

Zero parameter constructor is called by default. To change:

public TailList(int x){
	super(x); // calls the super class constructor and must be executed FIRST.
	tail = null;
}

Invoking overridden methods
——————————-

public void insertFront(Object obj){
	super.insertFront(obj); // for the superclass and  not necessarly the first line.
	if(size == 1){
	tail = head;
	}
}

The “protected” keyword
—————————-

public class SList{

	protected SListNode head;
	protected int size;
}

Both “protected ” field and method is visible to the declaring class and to all its subclasses.
In contrast, “private ” fields are not visible to subclasses.

Dynamic method lookup
————————
For Java “Every TailList is an SList”.

SList s = new TailList(); // TailList is a subclass of SList and SList is not abstract
s.insertFront(obj);

Abstract class
—————-
A class whose sole purpose it to be inherited. This is an ADT. An abstract method lacks the implementation.

public abstract class List{

	protected int size;

	public int lenght(){
		return size;
	}

	public abstract void insertFront(Object obj);

}

List mylist;
mylist = new List(); //compile time error

A non abstract class may never
1. contain an abstract method.
2. inherit one without providing an implementation.

List mylist = new SList(); // correct!
mylist.insertFront(obj);

One list sorter can sort every kind of list.

public void listSort(List l){
//code
}

Subclasses of List: SList, DList,TailList
TimedList: record amount of time doint list operations
TransactionList: Logs all the changes on a disk for power outage.

Data Structures using Java Part 10: Inheritence, Constructors, invoking orverriden methods, protected keyword, dynamic method lookup, Abstract class

Data Structures using Java Part 9: equals(), Degree of equality and Testing

equals
——-
Every class has one equals() method.

r1.equals(r2);
r1 == r2;

Now, if the content of the object (same or not same) pointed by r1 and r2 are the same then the first statement is true. The second statement is true iff both point to the same object. Many classes define equals() to compare the contents of the two objects.

Four degrees of equality
————————–
1. Reference equality, ==
2. Shallow Strutural equality, ie fields ==
3. Deep structural equality, ie fields equals()
4. Logical equality
a. Fractions 1/3 and 2/6 are “equals” from a mathematical point of view
b. “Set” objects are “equals” if they contain the same elements, irrelevent of the order.

public class SList{
public boolean equals(SList other){
if (size != other.size)
return false; // two SLists with different size cannot be same

SListNode n1 = head;     // initial offsets of both the SLists
SListNode n2 = other.head;

while(n1 != null){
if(!n1.item.equals(n2.item)){
return false;
}
n1 = n1.next;
n2 = n2.next;
} // end of while

return true;
}
}
Data Structures using Java Part 9: equals(), Degree of equality and Testing

Data Structures using Java Part 8: Heaps and Stack, Binary Search, Recursion, Scope, Parameter passing

The Stack and the Heap
————————–
The heap stores all objects, including arrays and all the class variables.
The stack stores all the local variables including parameters.

When a method is called Java creates a stack frame (or called an activation record). It stores the parameters and the local variables. The JVM maintains an entire stack of “stack frames”. When the method completes, its stack frame is erased. Most OS give enough space for a few thousands of stack frames.

Thread.dumpstack()
———————-
This method when called will print out the contents of the stack frame. Its present in the java.lang package and so doesnt need to be imported.

Parameter passing
——————–
In Java , the parameters are passed by value. That is they are copied.

class IntBox{

	static void donothing(int x){
		x = 2;
	}

	public int i;

	static void set3(Intbox ib){
	ib.i = 3;
	}

	static void badSet4(IntBox ib){
		ib = new IntBox(4);
		ib.i = 4;
	}
}

// called
	static void donothing(int x){
		x = 2;
	}

// calling
	int a = 1;
	donothing(a);

The variable a will be created in present stack frame. When the function donothing() is called, a new stack frame is created on top of the previous frame and the variable x resides in this frame. Note that no change happens to a after the function completes. The frame is erased once the function exits.

When the parameter is a reference, the reference is copied and not the object it is pointing to.

//called

	static void set3(Intbox ib){
	ib.i = 3;
	}

//calling
	IntBox b = new IntBox();
	set3(b);

In the local stack variable b is created. The object is created in heap with the variable i inside it. b points to object. set3() creates a parameter ib, both in new stack frame and then ib points to object pointed by b. The value of the object is changed by ib which is reflected on b, since both point to the same thing.

// called
	static void badSet4(IntBox ib){
		ib = new IntBox(4);
		ib.i = 4;
	}
//calling
	IntBox b = new IntBox();
	badSet4(b);

The difference here is that now a new object is created by the setBad() function and its value of ib is being set. The old heap object still retains its value. This happens to be a common programming error.

Binary Search
—————-
Used to search a sorted array. Suppose we want to search in a sorted int array. In this example , we try to find whether the variable “find” exists in the array, if so then return its array index. If not, return failure. This is going to be a predefined constant like FAILURE = -1. I have used a recursive algorithm.

Binary Search Procedure
// Binary Search
public static final int FAILURE = -1; // set as -1 because no index is less than 0 and final implies constant

public static int binarySearch(int[] i, int left, int right, int find){

	if (left > right)				// this is the base case; exit if the case.
		return FAILURE;

	int mid = (left + right)/2;          // find the middle element ; base case

	if (find = i[mid]){
		return mid;			// found!
	}else if (find < i[mid]){		// less implies the left subarray
		return binarySearch(i, left, mid -1, find);
	}else {					// more implies the right subarray
		return binarySearch(i, mid + 1, right,  find);
	}
	}
}

Recursion base cases:
1. if find = middle element: return index
2. if subarray is of length 0, nothing is there to search, return 0.

How fast is it?
Takes log n (base 2) recursive binarySearch calls.

Scope and Recursion
———————-
Scope of a variable : is portion of the program , actual lines of code, that can access the variable.
1. Class variables: (static fields) are in scope everywhere in the class except where shadowed by local variables. (like when using “this”)
2. Fully qualified class variable:For example “System.out” is not ambiguous. They are in scope everywhere in the class and are not shadowed. If public, they are in scope in ALL classes.
3. Instance variables: These are in scope in methods that are not static, except when shadowed.
4. Fully qualified instance variable: For example: “this.name” Same as 2.
5. Local variables: which includes parameters, only in scope in the block that defines them.

Data Structures using Java Part 8: Heaps and Stack, Binary Search, Recursion, Scope, Parameter passing

Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)

private field
————–
private field is invisible and inacessable to other classes.
Reasons:
1. To prevent data to be corrupted by other classes.
2. You can improve the implementation without causing the other classes to fail.

public class Date{

	private int day;
	private int month;

	public void setMonth(int m){
		month  = m;
	}

	public Date(int month , int date){
	// implementation and error checking code
	}
}
public class Evil{

	public void tamper(){

	Date d = new Date(10,10,2010); // this step is possible

	// these are not going to work!
	d.day =2000;
	d.setMonth(56);
	}
}

Interfaces
————
The interface of a class is made up of two things:
1. prototype for public methods and
2. the descriptions of the method behaviour.

Abstract Data Types(ADT)
——————————
ADT is a class(s) that has a well defined interface, but whose implementation details are firmly hidden from other classes.

Invarient
———-
Invarient is a fact about a data structure that is always true. (assuming there are no bugs). For example the “Date” object always represents a valid date.
Not all classes are ADTs. Some are just store data(no invarients).

The SList ADT
—————–

Another advantage of having a seperate SList class is that it enforces two invarients:
1. “size” is always correct.
2. list is never circularly linked.

Both of these goals are accomplised through simple Java mechanisms. Only the SList methods can change the lists.

SList ensures this:
1. The fields of the SList class are private. The “head” and “size” are private.
2. No method of SList returns an SListNode.

Doubly Linked Lists
———————

Doubly linked list

Inserting or deleting an element at the front of list is easy:

public void deleteFront(){
	if (head != null){
	head = head.next;
	size--;
	}
}

Inserting or deleting the item from the end of the list takes a lot of time in traversals.

public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

public class DList{

	private DListNode head; // points to start of the list
	private DListNode tail; // points to the end of the list
}

Insert and delete items at both ends in constant running time.
Removes the tail node (at least 2 items in DList):

tail.prev.next = null;
tail = tail.prev;

Sentinel
———
A special node that does not represent an item. It is to be noted that the sentinel node does not store an item.

Circularly linked Doubly linked list
————————————

 // no changes here
 public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

// changes here
public class DList{

	private DListNode head; // head will point to the sentinel
	private int size; // keeps track of the size of the list excluding the sentine.
}

DList invarients with sentinel:
——————————–
1. For any DList data structure d, d.head will never be null.
2. For any DListNode x, x.next is never null.
3. For any DListNode x, x.perv is never null.
4. For any DListNode x, if x.next is == y, then y.perv ==x.
5. For any DListNode x, x.prev ==y, then y.next ==x.
6. A DLists “size” field is number of DListNodes, NOT COUNTING sentinel. The sentinel is always hidden.
7. In empty DLists, the sentinels next and prev point to itselfs.

Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)