LinkedList in Java
Linked List is almost similar ArrayList features. It is a part of the collection framework present in java.util package. The class is an implementation of the linear LinkedList data structure. Here the elements are not stored in adjoining locations and every element is an isolated object with a data part and address part. Here the elements are linked or connected using pointers and addresses. Each element is known as a node but these nodes are not directly used. In case the dynamicity and ease of insertions and deletions, they are preferred over the arrays.
Example: The following implementation demonstrates how to create and use a linked list. The LinkedList class is almost identical to the ArrayList:
Example 1
import java.util.LinkedList; // Import the LinkedList class
public class Main {
public static void main(String[] args) {
LinkedList<String> letters= new LinkedList<String>();
letters.add("A");
letters.add("B");
letters.add("C");
letters.add("D");
System.out.println(letters);
// Adding elements to the linked list
letters.add("AA");
letters.add("BB");
letters.addLast("CC");
letters.addFirst("DD");
letters.add(2, "EE");
System.out.println(letters);
letters.remove("B");
letters.remove(3);
letters.removeFirst();
letters.removeLast();
System.out.println(letters);
}
}
OUTPUT
A,B,C,D
[DD, AA, EE, BB, CC]
[AA]
In the example 1 java code we use Add, Remove etc. Operations on the code and these operation details given below: linkedList
- Add Elements: In order to add an element to an ArrayList, we can use the add() method. This method is overloaded to perform multiple operations based on different parameters.
- addFirst():Adds an item to the beginning of the list.
- addLast():Add an item to the end of the list.
- removeFirst():Remove an item from the beginning of the list.
- removeLast():Remove an item from the end of the list.
- getFirst():Get the item at the beginning of the list.
- getLast():Get the item at the end of the list.
- add(Object): It is used to add an element at the end of the LinkedList.
- add(int index, Object): This method is used to add an element at a definite index in the LinkedList.
- Changing Elements: After adding the elements, if we wish to change the element, it can be done by the set() method. Since a LinkedList is indexed, the element which we wish to change is referenced by the index of the element. Therefore, this method takes an index and the updated element needs to be inserted at that index.
- Removing Elements: In order to remove an element from a LinkedList, we can use the remove() method. This method is overloaded to perform multiple operations based on different parameters. They are:
- remove(Object): This method is used to remove an object from the LinkedList. If there are multiple such objects, then the first incidence of the object is removed.
- remove(int index): LinkedList is indexed, the method takes an integer value simply removes the element present at that specific index in the LinkedList. After removing the element, all the elements are moved to the left to fill the space and the indices of the objects are updated.
- Iterating the LinkedList: There are multiple ways to iterate through the LinkedList. The most famous ways are by using the basic for loop in combination with a get() method to get the element at a specific index and the advanced for loop.
A Java program to iterate the elements in an LinkedList given below:
import java.util.*;
public class ExMain {
public static void main(String args[])
{
LinkedList<String> letters = new LinkedList<>();
letters.add("Md");
letters.add("Harun");
letters.add(1, "is");
// Using the Get method and the for loop
for (int i = 0; i < letters.size(); i++) {
System.out.print(letters.get(i) + " ");
}
System.out.println();
// Using the for each loop
for (String str : letters)
System.out.print(str + " ");
}
}
Output:
Md is Harun
Md is Harun
How LinkedList work?
LinkedList pretend as a dynamic array and no need to specify the size while creating it, the size of the list auto increases when dynamically add and remove the items. In addition to, the elements are not stored in a constantly. So, there is no need to increase the size. Internally, the LinkedList is implemented using the doubly linked list data structure. The main difference between a normal linked list and a doubly LinkedList is that a doubly linked list contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list.
LinkedList Constructors :
To create a LinkedList create an object of the LinkedList class. The LinkedList class consists of various constructors that allow the possible creation of the list. The following are the constructors available in this class:
LinkedList(): This is for creating an empty linked list. If create an empty LinkedList with the name letters, then, it can be created as:
LinkedList letters = new LinkedList();
LinkedList(Collection C): This constructor is used to create an ordered list which contains all the elements of a specified collection, as returned by the collection’s iterator. If we wish to create a linkedlist with the name letters, then, it can be created as:
LinkedList letters = new LinkedList(C);
Java LinkedList class hierarchy:
The Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.
The important points about Java LinkedList are:
- It can contain duplicate elements.
- LinkedList class maintains insertion order.
- The clss is non synchronized.
- The class manipulation is fast because no shifting needs to occur.
- This class can be used as a list, stack or queue.
Hierarchy of LinkedList class:
Doubly Linked List: In the case of a doubly linked list, we can add or remove elements from both sides. java LinkedList class using doubly linked list
LinkedList class declaration with java.util.LinkedList class.
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable
Constructors of Java LinkedList
LinkedList(): It is used to construct an empty list.
LinkedList(Collection<? extends E> c): It is used to construct a list containing the elements of the specified collection, in the order, they are returned by the collection’s iterator.
Methods of Java LinkedList
boolean add(E e):This method is used to append the specified element to the end of a list.
void add(int index, E element):This methodis used to insert 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.
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.
boolean addAll(int index, Collection<? extends E> c):This method is used to append all the elements in the specified collection, starting at the specified position of the list.
void addFirst(E e):This method is used to insert the given element at the beginning of a list.
void addLast(E e):This method is used to append the given element to the end of a list.
void clear():This methodis used to remove all the elements from a list.
Object clone():This method is used to return a shallow copy of an ArrayList.
boolean contains(Object o):This method is used to return true if a list contains a specified element.
Iterator<E> descendingIterator():This method is used to return an iterator over the elements in a deque in reverse sequential order.
E element():This method is used to retrieve the first element of a list.
E get(int index): This method is used to return the element at the specified position in a list.
E getFirst(): This method is used to return the first element in a list.
E getLast(): This method is used to return the last element in a list.
int indexOf(Object o): This method is used to return the index in a list of the first occurrence of the specified element, or -1 if the list does not contain any element.
int lastIndexOf(Object o):This method is used to return the index in a list of the last occurrence of the specified element, or -1 if the list does not contain any element.
ListIterator<E> listIterator(int index):This method is used to return a list-iterator of the elements in proper sequence, starting at the specified position in the list.
boolean offerFirst(E e): This method inserts the specified element at the front of a list.
boolean offerLast(E e): This method inserts the specified element at the end of a list.
E peek(): This method is retrieves the first element of a list
E peekFirst(): It retrieves the first element of a list or returns null if a list is empty.
E peekLast(): It retrieves the last element of a list or returns null if a list is empty.
int size(): This method is used to return the number of elements in a list.
A common topic on ArrayList vs. LinkedList
- The LinkedList class is a collection which can contain many objects of the same type, just like the ArrayList.
- The LinkedList class has all of the same methods as the ArrayList class because they both implement the List interface. This means that you can add items, change items, remove items and clear the list in the same way. While, the ArrayList class and the LinkedList class can be used in the same way, they are built very differently.
How the ArrayList AND LinkedListworks:
The ArrayList class has a regular array inside it. When an element is added, it is placed into the array. If the array is not big enough, a new, larger array is created to replace the old one and the old one is removed. on the other hand, how the LinkedList works: Previously we have discussed about it. The LinkedList stores its items in “containers.” The list has a link to the first container and each container has a link to the next container in the list. To add an element to the list, the element is placed into a new container and that container is linked to one of the other containers in the list.
When To Use
When you want to access random items frequently use an ArrayList. You only need to add or remove elements at the end of the list. Besides, It is best to use a LinkedList when only use the list by looping through it instead of accessing random items. when frequently need to add and remove items from the beginning, middle or end of the list.