Which primitive data structure is suitable to implement a linked list in Java

Data Structure — Linked List

Heba Tarek
Follow
Sep 9, 2019 · 5 min read

In this article, We will talk about Linked List as a data structure.

I will try to make it as a question and answer, Let’s start.

Linked List

  • Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
  • A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
  • The last node of the list contains pointer to the null.

Implementing a Linked List in Java using Class

Pre-requisite: Linked List Data Structure

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at the contiguous location, the elements are linked using pointers as shown below.

In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

Java





class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d) { data = d; }
}
}

Creation and Insertion

In this article, insertion in the list is done at the end, that is the new node is added after the last node of the given Linked List. For example, if the given Linked List is 5->10->15->20->25 and 30 is to be inserted, then the Linked List becomes 5->10->15->20->25->30.
Since a Linked List is typically represented by the head pointer of it, it is required to traverse the list till the last node and then change the next to last node to the new node.


Java




import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// This inner class is made static
// so that main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list, int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
}
// Driver code
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
}
}
Output LinkedList: 1 2 3 4 5 6 7 8

Traversal

For traversal, below is a general-purpose function printList() that prints any given list by traversing the list from head node to the last.

Java




import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// Node is a static nested class
// so main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list,
int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
}
// **************MAIN METHOD**************
// method to create a Singly linked list with n nodes
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
}
}
Output LinkedList: 1 2 3 4 5 6 7 8

Deletion By KEY

The deletion process can be understood as follows:

To be done:

Given a ‘key’, delete the first occurrence of this key in the linked list.

How to do it:

To delete a node from the linked list, do following steps.

  1. Search the key for its first occurrence in the list
  2. Now, Any of the 3 conditions can be there:
    • Case 1: The key is found at the head
      1. In this case, Change the head of the node to the next node of the current head.
      2. Free the memory of the replaced head node.
    • Case 2: The key is found in the middle or last, except at the head
      1. In this case, Find the previous node of the node to be deleted.
      2. Change the next the previous node to the next node of the current node.
      3. Free the memory of the replaced node.
    • Case 3: The key is not found in the list
      1. In this case, No operation needs to be done.

Java




import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// Node is a static nested class
// so main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list,
int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
System.out.println();
}
// **************DELETION BY KEY**************
// Method to delete a node in the LinkedList by KEY
public static LinkedList deleteByKey(LinkedList list,
int key)
{
// Store head node
Node currNode = list.head, prev = null;
//
// CASE 1:
// If head node itself holds the key to be deleted
if (currNode != null && currNode.data == key) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(key + " found and deleted");
// Return the updated List
return list;
}
//
// CASE 2:
// If the key is somewhere other than at head
//
// Search for the key to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null && currNode.data != key) {
// If currNode does not hold key
// continue to next node
prev = currNode;
currNode = currNode.next;
}
// If the key was present, it should be at currNode
// Therefore the currNode shall not be null
if (currNode != null) {
// Since the key is at currNode
// Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(key + " found and deleted");
}
//
// CASE 3: The key is not present
//
// If key was not present in linked list
// currNode should be null
if (currNode == null) {
// Display the message
System.out.println(key + " not found");
}
// return the List
return list;
}
// **************MAIN METHOD**************
// method to create a Singly linked list with n nodes
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
//
// ******DELETION BY KEY******
//
// Delete node with value 1
// In this case the key is ***at head***
deleteByKey(list, 1);
// Print the LinkedList
printList(list);
// Delete node with value 4
// In this case the key is present ***in the
// middle***
deleteByKey(list, 4);
// Print the LinkedList
printList(list);
// Delete node with value 10
// In this case the key is ***not present***
deleteByKey(list, 10);
// Print the LinkedList
printList(list);
}
}
Output LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8

Deletion At Position

This deletion process can be understood as follows:
To be done:
Given a ‘position’, delete the node at this position from the linked list.
How to do it:
The steps to do it are as follows:

  1. Traverse the list by counting the index of the nodes
  2. For each index, match the index to be same as position
  3. Now, Any of the 3 conditions can be there:
    • Case 1: The position is 0, i.e. the head is to be deleted
      1. In this case, Change the head of the node to the next node of current head.
      2. Free the memory of replaced head node.
    • Case 2: The position is greater than 0 but less than the size of the list, i.e. in the middle or last, except at head
      1. In this case, Find previous node of the node to be deleted.
      2. Change the next of previous node to the next node of current node.
      3. Free the memory of replaced node.
    • Case 3: The position is greater than the size of the list, i.e. position not found in the list
      1. In this case, No operation needs to be done.

Java




import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// Node is a static nested class
// so main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list,
int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
System.out.println();
}
// Method to delete a node in the LinkedList by POSITION
public static LinkedList
deleteAtPosition(LinkedList list, int index)
{
// Store head node
Node currNode = list.head, prev = null;
//
// CASE 1:
// If index is 0, then head node itself is to be
// deleted
if (index == 0 && currNode != null) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(
index + " position element deleted");
// Return the updated List
return list;
}
//
// CASE 2:
// If the index is greater than 0 but less than the
// size of LinkedList
//
// The counter
int counter = 0;
// Count for the index to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null) {
if (counter == index) {
// Since the currNode is the required
// position Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(
index + " position element deleted");
break;
}
else {
// If current position is not the index
// continue to next node
prev = currNode;
currNode = currNode.next;
counter++;
}
}
// If the position element was found, it should be
// at currNode Therefore the currNode shall not be
// null
//
// CASE 3: The index is greater than the size of the
// LinkedList
//
// In this case, the currNode should be null
if (currNode == null) {
// Display the message
System.out.println(
index + " position element not found");
}
// return the List
return list;
}
// **************MAIN METHOD**************
// method to create a Singly linked list with n nodes
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
//
// ******DELETION AT POSITION******
//
// Delete node at position 0
// In this case the key is ***at head***
deleteAtPosition(list, 0);
// Print the LinkedList
printList(list);
// Delete node at position 2
// In this case the key is present ***in the
// middle***
deleteAtPosition(list, 2);
// Print the LinkedList
printList(list);
// Delete node at position 10
// In this case the key is ***not present***
deleteAtPosition(list, 10);
// Print the LinkedList
printList(list);
}
}
Output LinkedList: 1 2 3 4 5 6 7 8 0 position element deleted LinkedList: 2 3 4 5 6 7 8 2 position element deleted LinkedList: 2 3 5 6 7 8 10 position element not found LinkedList: 2 3 5 6 7 8

All Operations

Below is the complete program that applies each operation together:

Java




import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// Node is a static nested class
// so main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// **************INSERTION**************
// Method to insert a new node
public static LinkedList insert(LinkedList list,
int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// **************TRAVERSAL**************
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("\nLinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
System.out.println("\n");
}
// **************DELETION BY KEY**************
// Method to delete a node in the LinkedList by KEY
public static LinkedList deleteByKey(LinkedList list,
int key)
{
// Store head node
Node currNode = list.head, prev = null;
//
// CASE 1:
// If head node itself holds the key to be deleted
if (currNode != null && currNode.data == key) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(key + " found and deleted");
// Return the updated List
return list;
}
//
// CASE 2:
// If the key is somewhere other than at head
//
// Search for the key to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null && currNode.data != key) {
// If currNode does not hold key
// continue to next node
prev = currNode;
currNode = currNode.next;
}
// If the key was present, it should be at currNode
// Therefore the currNode shall not be null
if (currNode != null) {
// Since the key is at currNode
// Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(key + " found and deleted");
}
//
// CASE 3: The key is not present
//
// If key was not present in linked list
// currNode should be null
if (currNode == null) {
// Display the message
System.out.println(key + " not found");
}
// return the List
return list;
}
// **************DELETION AT A POSITION**************
// Method to delete a node in the LinkedList by POSITION
public static LinkedList
deleteAtPosition(LinkedList list, int index)
{
// Store head node
Node currNode = list.head, prev = null;
//
// CASE 1:
// If index is 0, then head node itself is to be
// deleted
if (index == 0 && currNode != null) {
list.head = currNode.next; // Changed head
// Display the message
System.out.println(
index + " position element deleted");
// Return the updated List
return list;
}
//
// CASE 2:
// If the index is greater than 0 but less than the
// size of LinkedList
//
// The counter
int counter = 0;
// Count for the index to be deleted,
// keep track of the previous node
// as it is needed to change currNode.next
while (currNode != null) {
if (counter == index) {
// Since the currNode is the required
// position Unlink currNode from linked list
prev.next = currNode.next;
// Display the message
System.out.println(
index + " position element deleted");
break;
}
else {
// If current position is not the index
// continue to next node
prev = currNode;
currNode = currNode.next;
counter++;
}
}
// If the position element was found, it should be
// at currNode Therefore the currNode shall not be
// null
//
// CASE 3: The index is greater than the size of the
// LinkedList
//
// In this case, the currNode should be null
if (currNode == null) {
// Display the message
System.out.println(
index + " position element not found");
}
// return the List
return list;
}
// **************MAIN METHOD**************
// method to create a Singly linked list with n nodes
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
//
// ******DELETION BY KEY******
//
// Delete node with value 1
// In this case the key is ***at head***
deleteByKey(list, 1);
// Print the LinkedList
printList(list);
// Delete node with value 4
// In this case the key is present ***in the
// middle***
deleteByKey(list, 4);
// Print the LinkedList
printList(list);
// Delete node with value 10
// In this case the key is ***not present***
deleteByKey(list, 10);
// Print the LinkedList
printList(list);
//
// ******DELETION AT POSITION******
//
// Delete node at position 0
// In this case the key is ***at head***
deleteAtPosition(list, 0);
// Print the LinkedList
printList(list);
// Delete node at position 2
// In this case the key is present ***in the
// middle***
deleteAtPosition(list, 2);
// Print the LinkedList
printList(list);
// Delete node at position 10
// In this case the key is ***not present***
deleteAtPosition(list, 10);
// Print the LinkedList
printList(list);
}
}
Output LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 0 position element deleted LinkedList: 3 5 6 7 8 2 position element deleted LinkedList: 3 5 7 8 10 position element not found LinkedList: 3 5 7 8




Article Tags :
Data Structures
Java
Java Programs
Linked List
Java-Class and Object
Java-List-Programs
Practice Tags :
Data Structures
Java-Class and Object
Linked List
Java
Read Full Article

Linked List vs Array

Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tagsgiving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation.

Data storage scheme of an array

Data storage scheme of a linked list

Major differences are listed below:

  • Size: Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to the risk of overwriting other data. However, in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size that can change at runtime.
  • Memory allocation: For arrays at compile time and at runtime for linked lists. but, a dynamically allocated array also allocates memory at runtime.
  • Memory efficiency: For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.
  • Execution time: Any element in an array can be directly accessed with its index; however in the case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while some others (such as inserting/deleting an element in the data) are faster in linked lists.

Following are the points in favor of Linked Lists.
(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.



(2) Inserting a new element in an array of elements is expensive because room has to be created for the new elements and to create room existing elements have to be shifted.

For example, suppose we maintain a sorted list of IDs in an array id[ ].

id[ ] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides the following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Linked lists have the following drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

4) It takes a lot of time in traversing and changing the pointers.

5) It will be confusing when we work with pointers.

References:
//cslibrary.stanford.edu/103/LinkedListBasics.pdf

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :
Arrays
Linked List
Practice Tags :
Linked List
Arrays
Read Full Article

Array

Array is linear data structure which stores fixed number of similar elements. Array can store primitive data types as well as object but it should be of same kind. This is one of most used data structures in java.

Declare and initialize array in java

You can declare a String array as below:

1
2
3
String[] strArr=new String[10];

Here,
String is data type
strArr is variable name
10 is size of the array

You can also initialize array as below:

1
2
3
String[] strArr={"One","Two","Three"};

Advantages of array

  • You can randomly access array elements using index
  • It can represent multiple elements of same type with single name
  • You can implement various data strucures such as LinkedList, Stack and Queue using Array

Disadvantages of array

  • You need to know number of elements in advance.
  • You can not modify array once its size is defined
  • Insertion and deletion are quite costly operation in array as you need to shift elements.

Example

Here is an example program of an array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package org.arpit.java2blog;
import java.util.Arrays;
public class StringArrayMain {
public static void main(String[] args) {
String[] strArr = {"One","Two","Three"};
System.out.println("Array elements are:");
// Iterate over array
for (int i=0;i<strArr.length;i++)
{
System.out.println(strArr[i]);
}
System.out.println("====================");
System.out.println("Printing array elements using Arrays.toString():");
System.out.println("====================");
// You can also use Arrays.toString() to print an array
System.out.println(Arrays.toString(strArr));
}
}

Output:

Array elements are:
One
Two
Three
====================
Printing array elements using Arrays.toString():
====================
[One, Two, Three]

import_contacts

Array practice programs

There are many java tricky interview programs that can be asked in interview.

You should practice these java interview programs on array.

  • Find smallest and largest element in array
  • Find second largest number in array
  • Find missing number in an array
  • Separate 0’s and 1’s in array
  • Separate odd even numbers in java
  • Sort array of 0’s, 1’s and 2’s in java
  • Find number occurring odd number of times in array
  • Minimum numbers of platforms required for railway station in java
  • Find pair whose sum is closest to zero in array in java
  • Find pair whose sum is closest to X in array in java
  • Find all pairs of elements whose sum is equal to given number
  • Search element in row wise and column wise sorted matrix
  • Stock buy and sell to maximize profit.
  • Find local minima in array
  • Find leader in array
  • Find subarray with given sum
  • Sliding window maximum
  • Find peak element in array
  • Permutations of array in java
  • Subsets of set
  • Rotate array by K positions
  • Largest sum contiguous subarray
  • search an element in a sorted and rotated arraybinary in java
  • Minimum element in a sorted and ratated array in java
  • Minimum jumps required to reach end of array

5 Minute Beginner’s Guide to Java’s Linked List Data Structure

Jill Platts

Apr 16, 2018·5 min read

Video liên quan

Postingan terbaru

LIHAT SEMUA