Linked Lists

Linked List sample codebase with reversing the list in place (using Java):

There are two ways to reverse a linked list in place. One is to utilize recursion and the other is the iterative approach. Utilizing recursion is straight forward and intuitive but suffers from the drawback of performance issues et al. We will discuss benefits of recursion vis a vis the iterative approach and vice-versa in another blog entry.

In this blog entry, we will utilize the iterative approach. The logic of reversing a linked list (singly linked list) is simple and let me explain it using this example of a linked list:

A->B->C->D->E

Here node A has a next pointer to node B and so on. Node E has the next pointer set to NULL since it is the end of this list.

What we need to do: We need to pass the head of this list (node A) to the reverse method and it should return us node E with the list reversed as in:

E->D->C->B->A

The logic is to go one node at a time and changing the direction of the arrow. This is done by setting the next pointer of node B to be A and so on. This is demonstrated in the Java program below (please see the reverse operation in bold).

 public class Reverse {

    public static void main(String[] args) throws Exception
    {
        LinkedList l = new LinkedList();

        for (int i = 0; i < 11; i++)
        {
            Node n = new Node(new String("" + i), null);
            l.addToEnd(n);
        }

        Node n = l.getStartingNode();
        while (n != null)
        {
            System.out.println("\t" + n);
            n = n.next;
        }

        n = reverse(l.getStartingNode());
        while (n != null)
        {
            System.out.println("\t" + n);
            n = n.next;
        }

    }

    static Node reverse(Node startingNode) throws Exception
    {
        Node n = startingNode;
        Node n1 = n.next;
        n.next = null;

        while (true)
        {
            if (n1 == null)
            {
                return n;
            }

            Node n2 = n1.next;
            n1.next = n;

            if (n2 == null)
            {

                return n1;
            }
            n = n1;
            n1 = n2;

        }
    }

}

class LinkedList {
    Node begin = null;
    Node last = null;

    boolean addToEnd(Node a)
    {
        if (begin == null)
        {
            begin = a;
            last = a;
        }
        else
        {
            last.next = a;
            last = a;

        }
        return true;
    }

    Node getStartingNode()
    {
        return begin;
    }

    Node getLastNode()
    {
        return last;
    }

}

class Node implements Cloneable {
    Object value;
    Node next;

    Node() {

    }

    Node(Object v, Node n) {
        this.value = v;
        this.next = n;

    }

    @Override
    public String toString()
    {
        return value.toString();
    }

    @Override
    protected Object clone() throws CloneNotSupportedException
    {
        return super.clone();
    }

}

SOA and EAI

Enterprise Architectures such as Service Oriented Architecture (SOA) are conceptualized to solve problems of the enterprise domain and one of the most important is the issue of IT resources communicating with each other.

That brings the discussion to Enterprise Application Integration (EAI).

EAI

It provides the toolset and processes to allow the disparate and diverse applications to communicate with each other in order to achieve a business objective. SOA is one way of achieving EAI.

EAI provides for:

  1. Quality of Service: Authentication, Authorization, Store and Forward
  2. Message Translation
  3. Message Routing
  4. Usually implement the VETO Pattern that is:

 

  • Validate: validate the message
  • Enrich: add to the message header or payload with the results of the invocation of another service or database
  • Transform: translate the input message to the format that the ultimate receiver understands
  • Operate: invoke the receiver.

 

EAI is usually implemented either as a Hub and Spoke Architecture or as a Messaging Bus.

Hub and Spoke:

 As the name suggests, utilizes spokes (adapters) that connect to a centralized hub that is responsible of providing the functionality mentioned in the earlier section. A consumer would connect via an adapter (spoke) to an hub (the integration engine) and the hub after embellishing the message invokes the providing spoke. The consumer spoke connects and translates the input message to the hub format. The hub provides the services mentioned above and passes on the message to the subscriber spoke that translates and routes the message to the destination application.

The spokes could be collocated with the hub or could be part of the consumers or providers. 

Salient Points:

  1. Easy to manage if there is a singular hub and the spokes are collocated with the hub.
  2. Application (consumers and publishers) are loosely coupled with each other through the use of the hub.
  3. Although the hub is centralized, they can be federated or a load balancer can be used to front multiple hubs to provide for scalability and fault tolerance.
Messaging Bus

The bus architecture is similar to Hub and Spoke with respect to the adapters but:

  1. Use Messaging
  2. The core components of the Integration Engine (the hub in the previous case)  are themselves separately deployed in different containers. This includes components for authentication, authorization, etc.
SOA:

It can be defined as the process of identifying and exposing software artifacts on the network as well defined services. These software artifacts could perform a business objective or any other useful purpose. A service can be a consumer as well as a provider to other services.

Enterprise Service Bus (ESB) is an implementation of SOA.

ESB

ESB  is similar to the messaging bus – the difference being that standards are in place. Standards such as SOAP and HTTP for message format and transport, WSDL to describe services, UDDI to look up services etc.

Advantages of SOA:
  1. Integration – ease in integration since standards are in place and specialized adapters might not have to be constructed.
  2. Agility – following from the previous point, a business can have a faster turnaround if adapters do not have to be written
  3. Reuse  and ROI – reuse through the use of open environment and loose coupling.