Linked List in Java
Introduction to Linked List
The array data structure has some shortcoming. The size
of an array must be defined when the program is developed. Here we must define the size of data, but during the execution of a program, the size we
define might be unused and lots of space is wasted and if data is more then the array size then this could lead to an undesirable effect on the whole program. There is another problem with using Array is that of insertion and deletion. In case of insertion of data into an array, we must shift data one position right and in case of deletion, we should shift data to the left. If there is huge data in an array then insertion and deletion required a huge amount of time.
define might be unused and lots of space is wasted and if data is more then the array size then this could lead to an undesirable effect on the whole program. There is another problem with using Array is that of insertion and deletion. In case of insertion of data into an array, we must shift data one position right and in case of deletion, we should shift data to the left. If there is huge data in an array then insertion and deletion required a huge amount of time.
These problems will be overcome by the Linked List data
structure. In Linked list representation of data structure, each element stored
in a node and node has two part one is data and another is reference or address
of the second node.
Definition of LinkedList:
Linked List is a linear structure which has a node linearly. It implements List and Deque interfaces.
Picture of LinkedList
Advantages of
LinkedList:
- It is a dynamic data structure which allocates the memory as when required.
- It has no pre-allocated memory like an array.
- Insertion and Deletion easily be done and it is faster.
- It can contain duplicate data.
Disadvantages of
LinkedList:
- It is arranged sequentially that is why access time is more.
- Memory is wasted due to pointer/ reference part.
- To access of nth element of a Linked List is O(n).
Usage of Linked List
It is used to implement abstract data type such as Stack,
Queue, List, Graphs
Java Linked List
In Java, Linked List implementation is done in doubly linked
list and it has List and Dequeue interfaces.
LinkedList Constructors
LinkedList () : initializes an empty LinkedList
implementation.
LinkedList (Collection c) : initializes a LinkedList
containing the elements of the specified collection, in the order they are
returned by the collection’s iterator.
LinkedList Method
boolean add(Object
o): This method is used to appends the specified element to the end of a
list.
void add(int
index, E element): This method is used to inserts the specified element
at the specified position index in a list.
boolean addAll(Collection<?
extends E> c) This method is
used to append all of the elements in the specified collection to the end of
this list, in the order that they are returned by the specified collection's
iterator.
void addFirst(Object
o): It inserts the given element at the beginning of a list.
void addLast(Object
o): It appends the given element to the end of a list.
void clear() This method is used to eliminate /
delete all the elements from a list.
int size()
This method is used to returns the total number of elements in a list
Object clone() It is used to return a shallow copy of an
ArrayList.
boolean contains(Object
o): return true if the list contains a specified element,
else false.
boolean remove(Object
o): It removes the first occurrence of the specified element in a
list.
Object getFirst() This method is used to returns the first element in a list.
Object getLast() This the method is used to returns the last element in a list.
int indexOf(Object
o) This method is used to returns
the index in a list of the first occurrence of the specified element, or -1 if
the list does not contain specified element.
lastIndexOf(Object
o) It returns the index in a list of the last occurrence of the specified
element, or -1 if the list does not contain specified element.
Iterator iterator() It returns an iterator over the
elements in this list in a proper sequence.
Object[] toArray() This
method is used to returns an array containing all of the elements in this list
in a proper sequence.
boolean remove(Object
o) It removes the first occurrence of the specified element in a list.
boolean
removeFirstOccurrence(Object o) It removes the first occurrence of the
specified element in a list (when traversing the list from head to tail).
removeLast()
This method removes and returns the last element from this list.
boolean removeLastOccurrence(Object
o) It removes the last occurrence of the specified element in a list (when
traversing the list from head to tail).
Java LinkedList Example of Addition, removing, iteration
In this program add() method is used to add an element in LinkedList. Here LinkedList object lList is invoked add() method to add values into the list. Here remove() is used to remove an element from the specified placed or element. ListIterator class is used to display elements of the list.
import java.util.LinkedList;
import java.util.LinkedList;
import java.util.ListIterator;
public class LinkedListAddRemoveIterateExample
{
public static void
main(String[] args)
{
//Create
linked list
LinkedList<String> lList = new LinkedList<>();
//Add elements
to Linked List
lList.add("Ravi");
lList.add("Harry");
lList.add("Shami");
lList.add("Cindy");
lList.add("Sachin");
lList.add("Salim");
lList.add("Virat");
System.out.println("\nPrint the Linked list elements:");
System.out.println(lList);
//Add elements
at a specified position
lList.add(3,
"Alam");
lList.add(6,
"Binni");
System.out.println("\nAfter adding at specified
Postion:");
System.out.println(lList);
//Remove element
from the linked list
lList.remove("Cindy");
lList.remove(4);
System.out.println("\nPrint After removing the
elements:");
System.out.println(lList);
//Iterate
ListIterator<String> itrator = lList.listIterator();
System.out.println("\nPrint Using ListIterato:");
while
(itrator.hasNext()) {
System.out.println(itrator.next());
}
}
}
Output:
Print the Linked list elements:
[Ravi, Harry, Shami, Cindy, Sachin, Salim, Virat]
After adding at specified Position:
[Ravi, Harry, Shami, Alam, Cindy, Sachin, Binni, Salim,
Virat]
Print After removing the elements:
[Ravi, Harry, Shami, Alam, Binni, Salim, Virat]
Print Using ListIterato:
Ravi
Harry
Shami
Alam
Binni
Salim
Virat
Another Example of
Linked List
import java.util.*;
class Student {
// Instance
variables
int roll;
String
name,address,section;
// Constructor
public Student(int
roll, String name, String address, String section) {
this.roll =
roll;
this.name =
name;
this.address =
address;
this.section =
section;
}
}
public class LinkedListStudent {
public static void
main(String[] args) {
//Creating
LinkedList of Students
List<Student> linkedList=new LinkedList<Student>();
//Creating
Students Object
Student b1=new
Student(1,"Ravi Kumar","Delhi","A");
Student b2=new
Student(2,"Salim Anwar","Kolkata","B");
Student b3=new
Student(3,"Virat Kholi","London","C");
//Adding
Students to LinkedList
linkedList.add(b1);
linkedList.add(b2);
linkedList.add(b3);
//Traversing
LinkedList
System.out.println("Roll"+ "\t" + "Name" +
"\t\t" + "Address" + "\t\t" +
"Section");
System.out.println("===================================================");
for(Student
b:linkedList){
System.out.println(b.roll+"\t"+b.name+"\t"+b.address+"\t\t"+b.section);
}
}
}
Output:
Roll Name Address Section
==============================================
1 Ravi
Kumar Delhi A
2 Salim
Anwar Kolkata B
3 Virat
Kholi London C
Convert between Array and Linked List
In this program, a String array converted to LinkedList with LinkedList ll = new LinkedList(Arrays.asList(name));
import java.util.*;
import java.util.*;
public class ArrayToLinkedList {
public static void
main(String[] args) {
// Initialize
array with Names
String[] name
= new String[] { "Amar", "Vicky", "Kamal",
"Jamal", "Mahesh" };
// Convert
given array to LinkedList
LinkedList ll
= new LinkedList(Arrays.asList(name));
// Iterate
over each element in LinkedList.
Iterator iterator = ll.iterator();
while
(iterator.hasNext()) {
// Print
element to console
System.out.println((String) iterator.next());
}
}
}
Output
Amar
Vicky
Kamal
Jamal
MaheshMore Program
