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
