Day 1 - Linked lists

Linked lists: Linked list is a list data structure where each element basically holds data as well as the reference to the next element.

Each element in a Linked List has two parts - Data (can be an Intger, String, Object) and a reference to the next element. Element of a linked list is also known as a node, perhaps for these reasons.

To define an element in a linked list. 

//Linked list have two things: data and reference to the next node.
// Here 'next' is a reference to the next node and 'data' is the value the node holds.
// 'data' is not limited to being an int. It could be a String, Object, float or any other datatype

public class Node {
Node next;
int data;

public Node(int newData){
data = newData;
}

public Node(Node newNode, int newData){
next = newNode;
data = newData;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}
}

To create a linked list data structure - 
import java.util.Scanner;

// Add nodes
// Remove nodes
// IsNodesavailable
// Get data related to a node
public class LinkedList {
static Node head; //First node
static int count; // count - tracks the number of nodes in the linked list

public LinkedList(){
head = null;
count = 0;
}

public LinkedList(Node newNode){
head = newNode ;
count ++;
}

// Add method - Create a new node with the data value as data 
public static Node add(int data){
Node temp = new Node(data);
if(count==0){
head = temp;
}
Node current = head;
while(current.getNext()!=null){
current = current.getNext();
}
if(count>0){
current.setNext(temp);
}
count++;
return head;

}
// Get the data at node 
public int get(int index){
if(index<=0){
return -1;
}
Node current = head;
for(int i=1;i
current = current.getNext();
}
return current.getData();
}

public int size(){
return count;
}

public boolean isEmpty(){
return head==null;
}
// Remove the last node from the list
public void remove(){
Node current = head;
while(current.getNext().getNext()!=null){
current = current.getNext();
}
current.setNext(null);
count--;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node head = null;
int N = sc.nextInt();

while (N-- > 0) {
int ele = sc.nextInt();
head = add(ele);
}
display(head);
sc.close();
}

public static void display(Node head) {
Node start = head;
while (start != null) {
System.out.print(start.getData() + " ");
start = start.getNext();
}
}
}

Input 

4 (number of elements in list)

2

3

4

1

Output:

2 3 4 1 

Linked lists over Arrays - In arrays, the elements are indexed. For example, in an array of [2,4,1,5], the element at arr[3] can be easily retrieved. However, in linked list, we need to traverse from the beginning of the linked list. 

So, retrieval of an element in a linked list takes linear time - O(n) 

whereas in an array takes constant time - O(1)

The advantage lies in the fact that insertions  and deletions in a linked list are much quicker. 

Insertion/Deletion at beginning of the linked list or prepend to the linked list - O(1) -- constant time 

Insertion/Deletion at end of the linked list or append to the linked list - O(n) -- linear (as we need to traverse from the beginning till end of the linked list)

Doubly linked list have references to both the nodes/ 

i.e. 

class Node {

   Node prev;

   Node next;

   int data;

}

So, in a doubly linked list, the last node's 'next' reference will null and the first node's 'prev' reference will be null. All other elements in between have 'prev' and 'next' reference. 

In a singly linked list, the last node's 'next' reference will be null.

A brief tutorial is presented in: 

https://www.youtube.com/watch?v=njTh_OwMljA

Courtesy: Hackerrank site