Linked List

Linked list is a fundamental data structure, which uses reference stored in each node to iterate through subsequent nodes. A linked list has many types like singly linked list, doubly linked list and circular linked list. Following is a simple bare bone implementation of singly linked list:

The base interface:

view plainprint?

1. public interface LinkedList<t> {  
2.  public boolean add(T t);  
3.  public boolean remove(T t);  
4.  public void removeAll();  
5.  public int size();  
6.  public boolean isEmpty();  
7. }</t>  

public interface LinkedList {
 public boolean add(T t);
 public boolean remove(T t);
 public void removeAll();
 public int size();
 public boolean isEmpty();
}

Class representing each node:

view plainprint?

1. public class LinkNode<t> {  
2.  private LinkNode<t> nextNode = null;  
3.  private T node = null;  
4.   
5.  public LinkNode() {  
6.     
7.  }  
8.    
9.  public LinkNode(T node) {  
10.   this.node = node;  
11.  }  
12.    
13.  public T getNode() {  
14.   return node;  
15.  }  
16.   
17.  public void setNode(T node) {  
18.   this.node = node;  
19.  }  
20.    
21.  public LinkNode<t> getNextNode() {  
22.   return nextNode;  
23.  }  
24.   
25.  public void setNextNode(LinkNode<t> nextNode) {  
26.   this.nextNode = nextNode;  
27.  }  
28.    
29.  public String toString() {  
30.   return node.toString();  
31.  }  
32.    
33.  public int hashCode() {  
34.   return node.hashCode();  
35.  }  
36.    
37.  public boolean equals(LinkNode<t> t) {  
38.   return node.equals(t.getNode());  
39.  }  
40. }</t></t></t></t></t>  

public class LinkNode {
 private LinkNode nextNode = null;
 private T node = null;

 public LinkNode() {
  
 }
 
 public LinkNode(T node) {
  this.node = node;
 }
 
 public T getNode() {
  return node;
 }

 public void setNode(T node) {
  this.node = node;
 }
 
 public LinkNode getNextNode() {
  return nextNode;
 }

 public void setNextNode(LinkNode nextNode) {
  this.nextNode = nextNode;
 }
 
 public String toString() {
  return node.toString();
 }
 
 public int hashCode() {
  return node.hashCode();
 }
 
 public boolean equals(LinkNode t) {
  return node.equals(t.getNode());
 }
}

Implementation for a singly linked list:

view plainprint?

1. public class SingleLinkedList<t> implements LinkedList<t> {  
2.  LinkNode<t> header = null;  
3.  LinkNode<t> lastNode = null;  
4.    
5.  public SingleLinkedList() {  
6.     
7.  }  
8.    
9.  public boolean add(T t) {  
10.   LinkNode<t> newNode = new LinkNode<t>(t);  
11.   if(header == null) {  
12.    header = newNode;  
13.   }  
14.   else {  
15.    lastNode.setNextNode(newNode);  
16.   }  
17.   lastNode = newNode;  
18.   return true;  
19.  }  
20.    
21.  public boolean remove(T t) {  
22.   LinkNode<t> tmp = header;  
23.   LinkNode<t> prev = null;  
24.     
25.   while(tmp != null) {  
26.    if(tmp.getNode().equals(t)) {  
27.     if(prev == null) header = null;  
28.     else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());  
29.     return true;  
30.    }  
31.    prev = tmp;  
32.    tmp = tmp.getNextNode();  
33.   }  
34.   return false;  
35.  }  
36.    
37.  public void removeAll() {  
38.   header = null;  
39.  }  
40.    
41.  public boolean isEmpty() {  
42.   return header == null;  
43.  }  
44.    
45.  public int size() {  
46.   LinkNode<t> tmp = header;  
47.   int size = 0;  
48.   while(tmp != null) {  
49.    size++;  
50.    tmp = tmp.getNextNode();  
51.   }  
52.     
53.   return size;  
54.  }  
55.    
56.  public String toString() {  
57.   StringBuffer str = new StringBuffer("[");  
58.   LinkNode<t> tmp = header;  
59.   while(tmp != null) {  
60.    str.append(tmp.toString());  
61.    tmp = tmp.getNextNode();  
62.    if(tmp != null) str.append(", ");  
63.   }  
64.   str.append("]");  
65.   return str.toString();  
66.  }  
67. }</t></t></t></t></t></t></t></t></t></t>  

public class SingleLinkedList implements LinkedList {
 LinkNode header = null;
 LinkNode lastNode = null;
 
 public SingleLinkedList() {
  
 }
 
 public boolean add(T t) {
  LinkNode newNode = new LinkNode(t);
  if(header == null) {
   header = newNode;
  }
  else {
   lastNode.setNextNode(newNode);
  }
  lastNode = newNode;
  return true;
 }
 
 public boolean remove(T t) {
  LinkNode tmp = header;
  LinkNode prev = null;
  
  while(tmp != null) {
   if(tmp.getNode().equals(t)) {
    if(prev == null) header = null;
    else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());
    return true;
   }
   prev = tmp;
   tmp = tmp.getNextNode();
  }
  return false;
 }
 
 public void removeAll() {
  header = null;
 }
 
 public boolean isEmpty() {
  return header == null;
 }
 
 public int size() {
  LinkNode tmp = header;
  int size = 0;
  while(tmp != null) {
   size++;
   tmp = tmp.getNextNode();
  }
  
  return size;
 }
 
 public String toString() {
  StringBuffer str = new StringBuffer("[");
  LinkNode tmp = header;
  while(tmp != null) {
   str.append(tmp.toString());
   tmp = tmp.getNextNode();
   if(tmp != null) str.append(", ");
  }
  str.append("]");
  return str.toString();
 }
}

Test class which uses the singly linked list implementation:

view plainprint?

1. public class LinkedListTest {  
2.   
3.  /** 
4.   * @param args 
5.   */  
6.  public static void main(String[] args) {  
7.   // TODO Auto-generated method stub  
8.   LinkedList<string> list = new SingleLinkedList<string>();  
9.   System.out.println("Is list empty? " + list.isEmpty());  
10.     
11.   list.add("1");  
12.   list.add("2");  
13.   list.add("3");  
14.   list.add("2");  
15.   list.add("2");  
16.   list.add("3");  
17.   System.out.println(list.size());  
18.   System.out.println(list);  
19.   System.out.println("Is list empty? " + list.isEmpty());  
20.     
21.   list.remove("2");  
22.   System.out.println(list.size());  
23.   System.out.println(list);  
24.   System.out.println("Is list empty? " + list.isEmpty());  
25.     
26.   list.removeAll();  
27.   System.out.println("Is list empty? " + list.isEmpty());  
28.  }  
29.   
30. }</string></string>  

public class LinkedListTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  LinkedList list = new SingleLinkedList();
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.add("1");
  list.add("2");
  list.add("3");
  list.add("2");
  list.add("2");
  list.add("3");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.remove("2");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.removeAll();
  System.out.println("Is list empty? " + list.isEmpty());
 }

}

Adapter Pattern

-  The adapter acts as the middleman by receiving requests from the client and converting them into requests that make sense on the vendor classes

­-  The adapter implements the target interface and holds an instance of the adaptee

-  The actual interface that the client needs is the target interface

-  We wrap the target interface with an adaptee interface, which does the work of the target interface

-  The client makes the request on the adapter, and the adapter delegates it to the adaptee interface

-  The client doesn't know that the actual work was done by the adaptee

-  Client and the adaptee are decoupled – neither knows about the other

-  Here's how the client uses the adapter

o        The client makes a request to the adapter by calling a method on it using the target interface

o        The adapter translates that request into one or more calls on the adaptee using the adaptee interface

o        The client receives the results of the call and never knows there is an adapter doing the translation

­           

­-  The Adapter Pattern converts the interface of a class into another interface the clients expect

­-  Adapter lets classes work together that couldn't otherwise because of incompatible interfaces

­-  This decouples the client from the implemented interface,

­-  If the interface changes over time, the adapter encapsulates the change so that the client doesn't have to be modified each time it needs to operate against a different interface

­-  It is not necessary that the adapter should wrap only one adaptee – it can hold two or more adaptees that are need to implement the target interface

 

­- There are two types of adapters

o        object adapters – uses composition - the adapter is composed of adaptee

§         it can not only adapt an adaptee class, but any of its subclasses

o        class adapters – uses multiple inheritance - the adapter subclasses both the target and the adaptee

§         it is committed to one specific adaptee class, but it doesn't have to reimplement the entire adaptee

§         it can also override the behavior of the adaptee, since its just subclassing

§         this cannot be used in Java since it involves multiple inheritance

 

­- Although Decorator and Adapter patterns looks similar, they are totally different in intent

o        Decorator wraps an object and adds new behavior

o        Adapter wraps an object and converts it into an interface the client expects

 

­- Following is an example of Adapter pattern. This example adapts an Enumerator to act as an Iterator

view plainprint?

1. public class EnumerationAdapter implements Iterator {  
2.   
3.     Enumeration enumeration;  
4.   
5.     public EnumerationAdapter(Enumeration enumeration) {  
6.   
7.         this.enumeration = enumeration;  
8.   
9.     }  
10.   
11.     public boolean hasNext() {  
12.   
13.         enumeration.hasMoreElements();  
14.   
15.     }  
16.   
17.     public Object next() {  
18.   
19.         enumeration.nextElement();  
20.   
21.     }  
22.   
23.     public void remove() {  
24.   
25.         throw new UnsupportedOperationException();  
26.   
27.     }  
28.   
29. }  

	public class EnumerationAdapter implements Iterator {

		Enumeration enumeration;

		public EnumerationAdapter(Enumeration enumeration) {

			this.enumeration = enumeration;

		}

		public boolean hasNext() {

			enumeration.hasMoreElements();

		}

		public Object next() {

			enumeration.nextElement();

		}

		public void remove() {

			throw new UnsupportedOperationException();

		}

	}