LinkedList

As we were discussing Data structures earlier. So to continue the discussion on the same topic we will specific data structure in this post.

In this post we are planning to put some light on LinkedList. We will discuss various type of LinkedList and their implementation in Java. Lets get going to understand the simplest, but the most important data structure.

What is LinkedList?
LinkedList is list of objects linked with each other. It is collection of object which can be accesses only in sequential manner.
Sounds nice, but I did not know what you mean.

As shown in the figure 1, 2, 3, 4, 5, and 6 are the elements. These elements are stored in a linked list. So to reach to 6 is not possible starting from 1 and traversing throw each of the nodes. Only information about the linked list stored is head of the list. if Link two nodes are broken than  it is not possible to accessible another node.

As shown in the figure 1, 2, 3 are accessible from the header but rest link is lost as there is no link between 3 and 4.

LinkedList representation on Java
As shown above a Node contains data and reference to another node. So if we need to think about the fields of a linked list, then Java class for linked list must be as mentioned below.

class LinkedList{
    int data;
    LinkedList next;
}

As mentioned each node contains the data and reference of another instance of the same class.

Imp Note: None of the programs listed below checks boundary conditions. While writing any program make sure to take them in consideration.
Operations
Add a data object at head.
Add a data object at tail.
Traverse to X location.
Delete the element at X location.
Search a value.

Add a data object at head: Worst Case O(1)
Create a Node and change Node's next to head. Point to Head to latest Node.

Now set new node next to header, but before doing so change new node's next to null.

addAtFront =>
LInkedList node1 = new LinkedList(19);
node1.next = header
header = node1

Add a Data object at rear: Worst Case O(n)

Instead adding to 19 to 1, add 19 after 6.
addAtRear =>

LinkedList node1 = new LinkedList(19);
while(!header.next == null) header = header.next
header.next = node1

By maintaining another instance object(tail) provides faster addition at rear. In general adding at rear is not so much needed.

Traverse to Xth element Worst Case O(X)
It is simple. You just to maintain traverse through X-1 nodes to reach to Xth element.

for( int count = 0; count < X - 1; count ++ ){
    head = head.next;
}
return head.data

Delete Xth element Worst Case O(X)
To delete Xth element you need to traverse to X-1th element and changing the reference of X-1 element to X+1 element instead Xth element.

for( int count = 0; count < X - 1; count ++ ){
    head = head.next;
}

head.next = head.next.next

Now as you can see 4 was earlier pointing to 5, but in the diagram showed above it is now pointing to 6 instead 5. So any link to 5 has been lost, so it is considered as deleted node.

Search A Value: Worst Case O(n)
Iterate over the linkedlist until you reach to either Null or required value. If you encounter NULL, it means LinkedList does not contain the value. In this case return -1, else return the position.
while( header != null && header.value != VAL ){
  header = header.next;
  count = count + 1;
}
return (header == null)? -1: count;

Many different data structures are implemented using linked list. Keeping link list in mind we must look for answers for these questions.
1.    Reverse a LinkList with single pointer in o(n) time…
2.       Linked List implementation of Queue
3.       Linked List implementation of Stack
4.       Finding the location of the list where loop was started.
5.       Write a function to return Nth node from the end of the linked list
6.       Write a function to swap every second node. [ie - 1->2->3->4->5->| becomes 2->1->4->3->5->|]

Type of Linked List
Singly Linked List
Linked implemented above is singly linked list. In this list traversal is possible only in one direction.

Doubly Linked List
It maintains 2 references to point in 2 directions. One to move forward and another to move backward.

class DoublyLinkedList{
    int data;
    DoublyLinkedList next;
    DoublyLinkedList previous;
}

Circular Linked List
This is another variant of Singly linked list. In this list last element of the list points to the first element of the list.

Data Structures

Data structures are different ways of storing data. After various years of research many people have come up with the following different kind of DS. These different DS are used based on the requirement. DS is chosen based on the problem.

In this blog we will look at the different structures which are helpful to tackle various computing problem. I have tried to put little information about all DS available, In future I will try to explain each one of them with their various versions. Hope it will help me to understand DS more.

Data Structure	Fields	Operations	Time Complexity	Pros	Cons	Comments
Array	MAX_CAPACITY	add(index, value) – On the specified index add the value.	O(1)	Index based Retrieval	1. Fixed Size of Array.	Arrays are the oldest and most DS. It is used to implement most of the other datastructures.
	index	delete(index) – Delete at specified index.	O(1)		2. Complex position based insertion
	objects[]	search(value) – Search the value.	O(n)		3. One block Allocation. It is not possible to use scattered memory with arrays
Linked List	Node{ Data, nextNode}	Insert – Add value at head.	O(1)	1. Linear Access	1. Retrieval at any index is slower wrt to Arrays.
	head of Node type	Delete – Search and delete the value.	O(n)	2. Does not need continuous memory locations.	2. Complex to use.	Linked list are useful when user is concentrating on insert operation instead index based retrieval.
		Search – Search the value.	O(n)	3. Size of the list is not fixed.
Stacks	MAX_CAPACITY	IsEmpty – If CURRENT_INDEX = -1	O(1)			Stacks works on last in first out methodology... Stacks are widely used in computer programming.
	CURRENT_INDEX	isFull CURRENT_INDEX = MAX_CAPACITY	O(1)			Stacks are used to validate compile time programs.
	objects[]	Push – Insert a object in array.	O(1)			Infix/postfix/prefix evaluation is done using stacks.
		Pop – removes a object and returns its value.	O(1)
Queue	MAX_CAPACITY	isEmpty – If HEAD = TAIL	O(1)			Queue works on First In/First out methodology.
	HEAD	isFull |HEAD - TAIL| = MAX_CAPACITY	O(1)			Queue are used to maintain threads.
	TAIL	Enqueue – inserting the record at head.	O(1)
	objects[]	Dequeue – Deletng the record from tail.	O(1)
Tree	Node{ Data, Node1, Node2, Node3 ....}	add(value) – Based on property of the tree add the node accordinly.	O(log(n))	1. Insertion is faster than array but slower than linked list.	1. Difficult to maintain the balance of the tree.	Trees are used for solving lot of algorithmic problems. It is known as most important and efficient data structure to solve multiple issues.
	depth	Delete – Search and delete the value.	O(n)	2. Searching is faster.	2. Complex and confusion at times.
	Leaves – Nodes which do not have any children.	Search – Search the value.	O(log(n))	3. Used with lot of different data structures.
	Internal Nodes – Nodes having one or more children.			4. Solves lot of problems.
Graph	Map of vertices and it's accessible vertices.	adjacent(G, x, y): tests whether there is an edge from node x to node y.	O(K)			Graphs are generally used for greedy solutions.
		neighbors(G, x): lists all nodes y such that there is an edge from x to y.	O(K)			Shortest path algorithms.
		add(G, x, y): adds to G the edge from x to y, if it is not there.	O(K)
		delete(G, x, y): removes the edge from x to y, if it is there.	O(1)
HashTable	objects[]	add(value) – Adds the value to the array.	O(1)	Fast searching operations are performed.	Need efficient hashing algorithms, otherwise it can be painful to search objects.	It is widely used in Database Indexing and caching operations.
	MAX_SIZE	delete(value) – Removes the value from the array.	O(1)	Used when program deals with huge chunk of data.
		Search(value)	O(1)

English Grammar: Conjunction

This is another post about English Grammar. It was the time to understand conjunctions from Wren and Martin. In this blog we will try to understand and remember few fundamentals about conjunctions.

So let's start with the meaning for conjunction.

Conjunction is a word which merely joins either sentences or words.
It would be nice to see some example to support such a small statement.

God made the country and man made the town.
Here and connects between 2 sentences i.e. First is god made the country whereas second is man made the town.

Two and two make four.
Here and connects between 2 words i.e first word is Two and second is word is Two.

Ramsingh is 65 year old, but he still runs 5Km everyday.
But is connecting two statement.

Conjunction joins 2 statement and often make them more compact.
E.g. Raju is poor, but honest.
This statement can be restated as "Raju is poor, but he is honest."

To differentiate between relative Conjunctions, relative adverb, and proposition, we must put additional cares, as all of them are connecting words.

Conjunction classification

Coordinating Conjunction: Joins both the clauses of equal rank. These are divided in 4 forms.
A. Cumulative: and(Joins 2 sentences)
We are writing the message and watching the movie.
B. Adversative: But, Still, Only (express opposition and contrast between 2 statements)
Radha was Krishna's love, but not wife.
C. Alternative: Either or, Neither Nor.(Demonstrate the choice between 2 sentences)
Neither Ravan nor Ram was willing for a war.
D. Illative: For (Express an inference)
All precautions must have been neglected, for the plague spread rapidly.

Subordinating Conjunction: Joins a clause to another on which it depends on its full meaning. Subordinating conjunctions are classified further as follows:
A. Time: before, till, Since, after
I returned home after he has gone.
B. Cause or Reason: Because, Since, As
As he was not reading, I scolded him.
C. Purpose: So, Lest
We earn so that we can eat.
D. Result or Consequence: that
I was not so interested in book that I could read it.
E. Condition: if
Ram can write if Hari can dictate.
F. Concession: though/Although
I will not see him, though he comes.
G. Comparison: than
Sachin is better player than Kaif.

List of conjunction
But, either.. or, neither.. nor, whether... or, though... yet, that, before, how, as, unless, until, though, although, when, while, where, if, than, that, since, after, till, and, until, for, lest, still, only, yet, where, except, else, otherwise, whenever.

These are commonly used conjunctions in English language, if I find some more than I must add them to the list.

Let's discuss few important conjunctions are their uses.

Important Conjunctions and their uses

Since
A. From and after the time when; as
I have been praying for India since(I started praying when Sachin was out.) Sachin fell.

In such use of Since, it must be preceded by verb in present perfect form, and followed by verb in simple past tense.

B. Seeing that, in as much as; as
Since(Seeing that) you are tired, you must rest.

Or
A. To introduce an alternative.
You must work or starve.
B. To introduce an alternative name or synonym.
Ram or Shyam play today cricket game.
C. To mean otherwise.
We must hasten or night will overtake us.
D. As nearly equivalent to and.
The troops were not in wanting in strength or courage, but they were badly fed.

If
A. Condition/Supposition
If he is there, I shall see him.
B. Admitting
If I am blunt, I am atleast honest.
C. Whether
I asked him if he have a pen.
D. Whenever
If I feel any doubt I inquire.

That
A. Reason or Cause
He was annoyed that he lost the bet.
B. Express a purpose
We sow that we may reap.
C. Express a Consequence
He bled so profusely that he died.

Than
Follows adjectives and adverbs in the comparative degree.
Cricket is watched more than any other game in India.

Lest
Expresses a negative purpose, and is equivalent to 'In order that... not', 'for fear that'.
He fled lest he should be killed.

While
A. During the time that, as long as
While there is life there is hope.
B. At the same time that.
The girls sang while the boys played.
C. Whereas
While I have no money to spend, you have nothing to spend on.

Only
As a conjunction, means except that, but, were if not.
A very pretty woman, only she squints a little.

Because. for, Since

Rest other conjunctions are not discussed here, but if I find something else must be discussed I will surely add them to the list.