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.