One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. In this article we take a look at another data structure called Linked Lists that addresses some of the limitations of arrays. We will see how to implement singly linked list in java, you can also watch the following video for better understanding of data structure
A linked list is a linear data structure where each element is a separate object.
It is one of the most used data structure. In singly linked list, Node has data and pointer to next node. It does not have pointer to the previous node. Last node ‘s next points to null, so you can iterate over linked list by using this condition. Node for linked list can be presented as below:
// A simple Java program to introduced single linked list
public class LinkedListexercise2
{
Node head; //the head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
static class Node {
// data members of the class.
char data;
Node next, prev;
// contructor will initializ data members
// with the values of passed arguments while
// object of this class is created.
Node(char d) { data = d; next = prev = null; }
}
/* Given a reference to the head of a list and a String,
inserts a new Node on the front of the list. */
public void add(char new_data)
{
/* 1. alloc the Node and put data*/
Node new_Node = new Node(new_data);
/* 2. Make next of new Node as head */
new_Node.next = head;
/* 3. Move the head to point to new Node */
head = new_Node;
}
/* Inserts a new node after the given prev_node. */
public void addAfter(Node prev_node, char new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println("The given previous node cannot be null");
return;
}
/* 2 & 3: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;
/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}
/* Appends a new node at the end.*/
public void addlast(char new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty, then make the
new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}
/* 4. This new node is going to be the last node, so
make next of it as null */
new_node.next = null;
/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
return;
}
/* Given a key, deletes the first occurrence of key in linked list */
void remove(char key)
{
// Store head node
Node temp = head, prev = null;
// If head node itself holds the key to be deleted
if (temp != null && temp.data == key)
{
head = temp.next; // Changed head
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change temp.next
while (temp != null && temp.data != key)
{
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null) return;
// Unlink the node from linked list
prev.next = temp.next;
}
/* Given a reference (pointer to pointer) to the head of a list
and a position, deletes the node at the given position */
void removeNode(int position)
{
// If linked list is empty
if (head == null)
return;
// Store head node
Node temp = head;
// If head needs to be removed
if (position == 0)
{
head = temp.next; // Change head
return;
}
// Find previous node of the node to be deleted
for (int i=0; temp!=null && i<position-1; i++)
temp = temp.next;
// If position is more than number of ndoes
if (temp == null || temp.next == null)
return;
// Node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
Node next = temp.next.next;
temp.next = next; // Unlink the deleted node from list
}
/* Takes position as argument and return data at position*/
void printpositionOf(int n)
{
int len = 0;
Node temp = head;
// 1) count the number of nodes in Linked List
while (temp != null)
{
temp = temp.next;
len++;
}
// check if value of n is not more than length of
// the linked list
if (len < n)
return;
temp = head;
// 2) get the (len-n+1)th node from the begining
for (int i = 1; i < len-n+1; i++)
temp = temp.next;
System.out.println(temp.data);
}
/* This function prints contents of linked list starting from head */
public void printList()
{
Node n = head;
while (n != null)
{
System.out.print(n.data+" ");
n = n.next;
}
}
/* Function to print reverse of linked list */
void printReverse(Node head)
{
if (head == null) return;
// print list of head node
printReverse(head.next);
// After everything else is printed
System.out.print(head.data+" ");
}
/* Main program to test above functions*/
public static void main(String[] args)
{
/* Start with empty list */
LinkedListexercise2 alflist = new LinkedListexercise2();
/* Use add() to construct below list
k->i->h->g->d... */
alflist.add('k');
alflist.add('i');
alflist.add('h');
alflist.add('g');
alflist.add('d');
alflist.add('c');
alflist.add('k');
alflist.add('b');
alflist.add('a');
System.out.println("Original alfabet list ");
alflist.printList();
System.out.println("");
alflist.addAfter(alflist.head.next.next.next.next, 'e');
alflist.add('0');
alflist.addlast('j');
System.out.println("Altered alfabet list added e,0,j ");
alflist.printList();
System.out.println("");
System.out.println("Element at position 12 is ");
alflist.printpositionOf(12);
alflist.remove('k');
alflist.removeNode(9);
alflist.remove('0');
alflist.addAfter(alflist.head.next.next.next.next, 'f');
System.out.println("After removing k,k,0 and add f ");
alflist.printList();
System.out.println("");
System.out.println("Reverse final list ");
alflist.printReverse(alflist.head);
}
}
Outpu will be like his;
Original alfabet list a b k c d g h i k Altered alfabet list added e,0,j 0 a b k c d e g h i k j Element at position 12 is 0 After removing k,k,0 and add f a b c d e f g h i j Reverse final list j i h g f e d c b a