LinkedList
			      ==========
-> It is a part of collection framework which is present in "java.util" package.
-> LinkedList is a class which must be implements from "List" interface.
Syntax:
	class LinkedList<T> implements List<>(){
	}
-> LinkedList is a Data Structure which is linear data structure where the elements are stored in a non-contiguous memory locations.
and each element of LinkedList is a separate object with a data part and address part.
-> LinkedList is a collection of nodes.
	Each Node can define with two parts:
		1) Data part
		2) Address Part
-> If a LinkedList with a single node, then the address Part of that node represented with "next" as a pointer which points to "null".
-> If a LinkedList with multiple nodes, then first node of the given LinkedList is called as "Head". The "next" part of head points to the data part of next immediate node (next of head can store address of the data part of next immediate node). And in the last of node of the LinkedList have the next with "null".

Q:When we can use ArrayList and when we can use LinkedList?
============================================================
1) when we want to perform read operations as must faster than write operations, then we can use "ArrayList".
2) when we want to perform write operations as much faster than read operations, then we can use "LinkedList".

Features of LinkedList:
======================
1) Dynamic size
2) Efficient in write operations like:
	adding, insertion, update, delete etc.

Creation of LinkedList:
=======================
1) Create a Node:
=================
class Node{
}

2) Define LinkedList:
=====================
class LinkedList{
}

3) Test the Linked List:
=========================
create the object for the LinkedList
and start define an operations using "Nodes".


package pack.ll1;

// create a node
class Node{
	int data;
	Node next;
	
	// constructor
	public Node(int data) {
		this.data = data;
		this.next = null;
	}
}

// create a LinkedList Class

class LinkedList{
	Node head;
	
	public void insert(int data) {
		Node newNode = new Node(data);
		if(head == null) {
			head = newNode;
			return;
		}
		Node temp = head;
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode; // adding of new node
	}
	
	public void display() {
		if(head == null) {
			System.out.println("The Given LinkedList is Empty.");
			return;
		}
		Node temp = head;
		while(temp != null) {
			System.out.println(temp.data);
			temp = temp.next;
		}
	}
	
}

public class MainClass {

	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		
		list.insert(100);
		list.insert(111);
		list.insert(222);
		list.insert(444);
		list.insert(-127);
		list.insert(-9779);
		list.insert(0);
		
		list.display();
	}

}
======================================
Creation of LinkedList using LinkedList<>() constructor:
=========================================================

package pack.pack1;

import java.util.LinkedList;

public class MainClass {

	public static void main(String[] args) {
		// create a linkedlist using LinkedList<>() constructor
		LinkedList<String> train = new LinkedList<>();
		
		// Adding of ELements (Nodes)
		train.add("Engine");
		train.add("Coach-A");
		train.add("Coach-B");
		train.add("Coach-C");
		train.add("Caboose");
		
		// Displaying of LinkedList data
		System.out.println("Initial Train Composition = "+train);
		
		// Insert the data
		train.add(2,"Coach-X");
		System.out.println("The Train Composition after the Insert Operation = "+train);
		
		// Accessing of LinkedList data
		System.out.println("First:"+train.getFirst());
		System.out.println("Last:"+train.getLast());
		
		System.out.println("The Train:");
		for(String compart:train) {
			System.out.println(compart);
		}
	}

}

How LinkedList Internally Work?
===============================
1) LinkedList in java is "dynamic". At the time of creation, no need to specify the size.  The linked list size can be increased or decreased based on the requirement.
2) By default, the LinkedList internally work as doubly linked list.

Types of LinkedList:
====================
==> two types of LinkedList:
	1) Singly LinkedList
	2) Doubly LinkedList

1) In Singly LinkedList, Node always be with two parts: Data part and Address Part (next).
2) In Doubly LinkedList, the node is always with three parts:
	1) previous
	2) data
	3) next
==> here: previous can store the address of the previous node
	next can store the address of the next node.


LinkedList Operations:
======================
1) Adding elements into LinkedList:
===================================
	add(data) ==> can add at the last by default
	add(index, data) ==> can add at the specified index.
	addFirst(data) ==> can add at the beginning of LinkedList.
	addLast(data) ==> can add at the last of LinkedList. 

2) Removing Elements from LinkedList:
===================================== 
	remove(index) ==> can remove an element of LinkedList based on the index.
	remove(Node Data) ==> can remove an element of LinkedList based on the specified data.
	removeFirst() ==> can remove the first node from LinkedList
	removeLast() ==> can remove the last node from LinkedList
	clear()
	removeAll()

package pack.pack1;

import java.util.LinkedList;

public class MainClass {

	public static void main(String[] args) {
		// create a linkedlist using LinkedList<>() constructor
		LinkedList<String> train = new LinkedList<>();
		
		// Adding of ELements (Nodes)
		train.add("Engine");
		train.add("Coach-A");
		train.add("Coach-B");
		train.add("Coach-C");
		train.add("Caboose");
		
		// Displaying of LinkedList data
		System.out.println("Initial Train Composition = "+train);
		
		// Insert the data
		train.add(2,"Coach-X");
		System.out.println("The Train Composition after the Insert Operation = "+train);
		
		// Accessing of LinkedList data
		System.out.println("First:"+train.getFirst());
		System.out.println("Last:"+train.getLast());
		
		System.out.println("The Train:");
		for(String compart:train) {
			System.out.println(compart);
		}
		
		// adding of new element at the beginning
		train.add(0,"Coach-P");
		
		System.out.println(train);
		train.addFirst("Coach-R");
		System.out.println(train);
		
		// adding of new element at the end of the LinkedList
		train.addLast("Coach-Z");
		
		System.out.println(train);
		
		// removing of Elements from LinkedList
		train.remove(3); // remove based on index
		System.out.println(train);
		
		// remove based on value
		train.remove("Caboose");
		System.out.println(train);
		
		// removing of first node
		train.removeFirst();
		System.out.println(train);
		
		// removing of last node
		train.removeLast();
		System.out.println(train);
		
////		train.removeAll(train);
//		train.clear();
//		System.out.println(train);
		
		for(int i = 0;i < train.size();++i) {
			System.out.println(train.get(i));
		}
		
		// converting a LinkedList into an array
		String[] result = train.toArray(new String[0]);
		
		for(String i:result) {
			System.out.println(i);
		}
	}

}

Doubly LinkedList:
==================

package pack.p1;

class BrowserHistory{
	private class Node{
		String url; // data part
		Node prev; // previous part can store the address of previous URL
		Node next; // next part can store the address of next URL
		
		Node(String url){
			this.url = url;
		}
	}
	private Node head;
	private Node current;
	
	public BrowserHistory(){
		head = new Node("homePage");
		current = head;
	}
	
	// Visit a new URL
	public void visit(String url) {
		Node newNode = new Node(url);
		current.next = newNode;
		newNode.prev = current;
		current = newNode;
	}
	
	// Go back step wise
	public String back(int steps) {
		while(steps > 0 && current.prev != null) {
			current = current.prev;
			steps--;
		}
		return current.url;
	}
	
	// Go forward in steps
	public String forward(int steps) {
		while(steps > 0 && current.next != null) {
			current = current.next;
			steps--;
		}
		return current.url;
	}
	
	// print the current history
	public void printHistory() {
		Node temp = head;
		while(temp != null) {
			System.out.println(temp.url);
			temp = temp.next;
		}
	}
}

public class MainClass {

	public static void main(String[] args) {
		BrowserHistory bh = new BrowserHistory();
		
		bh.visit("google.com");
		bh.visit("ashokit.in");
		bh.visit("Linkedin.com");
		bh.visit("Youtue.com");
		bh.visit("Facebook.com");
		
		System.out.println("The Current URL = "+bh.back(1));
		System.out.println("The Current URL = "+bh.back(1));
		System.out.println("The Current URL = "+bh.forward(1));
		System.out.println("The Current URL = "+bh.forward(1));
		
		bh.printHistory();
	}

}



Assignment:
===========
1) WAP to create a linkedlist of any type, access the linkedlist data using:
	listIterator() 
	iterator().

2) WAP to create a linkedlist of any type, and perform the sorting using sort() with comparable and with comparator.