Linked List in java-Java Collection
The array data structure has some shortcomings. 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.
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 parts one is data and another is the reference or address of the second node.
Linked List is a linear structure which has a node linearly. It implements List and Deque interfaces.
Advantages of LinkedList:
- It is a dynamic data structure that 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 the pointer/ reference part.
- To access of nth element of a Linked List is O(n).
It is used to implement abstract data type such as Stack, Queue, List, Graphs
In Java, Linked List implementation is done in doubly linked list and it has List and Dequeue interfaces.
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.
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 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 a 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 a 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).
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.ListIterator;
public class LinkedListAddRemoveIterateExample
public static void main(String[] args)
LinkedList<String> lList = new LinkedList<>();
//Add elements to Linked List
System.out.println(“\nPrint the Linked list elements:”);
System.out.println(lList);
//Add elements at a specified position
System.out.println(“\nAfter adding at specified Postion:”);
System.out.println(lList);
//Remove element from the linked list
System.out.println(“\nPrint After removing the elements:”);
System.out.println(lList);
ListIterator<String> itrator = lList.listIterator();
System.out.println(“\nPrint Using ListIterato:”);
while (itrator.hasNext()) {
System.out.println(itrator.next());
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]
Another Example of Linked List
String name,address,section;
public Student(int roll, String name, String address, String 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
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);
Roll Name Address Section
==============================================
1 Ravi Kumar Delhi A
2 Salim Anwar Kolkata B
3 Virat Kholi London C
In this program, a String array converted to LinkedList with LinkedList ll = new LinkedList(Arrays.asList(name));
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());
Mahesh
More Program
Originally published at https://javaknowhow.blogspot.com.