Java LinkedList

java linkedlist

class LinkedList<E>

java.lang.object

       java.util.Abstractcollection

                 java.util.AbstractList

                         java.util.AbstractSequentialList

                                      java.util.LinkedList<E>

<E> –> The type of elements held in this collection

All known implemented interfaces

Serializable , Cloneable , Iterable<E> , Collection<E> , Deque<E> , List <E> , Queue<E>

Java LinkedList is one of the general purpose implementation class to List interface. Like ArrayList , Java LinkedList also permits null and duplicate elements. Insertion order is preserved (in what order we inserts the data , the same order will be maintained). Java LinkedList will automatically increases it’s capacity when the user inserts the elements more than the actual capacity. Now let’s take a deeper look on what data structure Java LinkedList is based on.

Java LinkedList

The underlying data structure of the Java LinkedList is “Doubly-linkedList” implementation. In computer science a doubly linked list is the linked data structure with one another that consists of a set of sequentially linked records called “nodes“. Each node will have three compartments. The first and the last compartments are called ‘links’ that are references to previous node and to the next node in the sequential manner. Every node is identified by the index number.

java linkedlist inside diagram

Java LinkedList supports all the operations provided by Collection interface and List interface and also LinkedList has it’s own methods for reliable programming. The operations which are performed based on the index value like get(4) [gets the element at 4th index] , the list will traverse from the beginning or the end which ever is closer to the specified index. 

For Example , there is a LinkedList of size 10 , if we try to get the value at index 7 , then the list will start searching from the end because the index number 7 is closer to the size of the array which is  10. In the same way , if the search is on index value 3 , then the list will search from beginning ( index value 0 is close index value 3).

Bullet Points on Java LinkedList 

  • LinkedList implementation allows duplicated and null elements and it is an ordered list .
  • It is not Synchronized , to make it synchronized use the Collection’s synchronization wrappers.
  • When the frequent program requirements are adding and removing then Java LinkedList is the best implementation class, but when the frequent operations are retrieving then ArrayList is the best choice.
  • The retrieval time is not constant like ArrayList.
  • When any iterator iterates over the elements in the list , then the returned iterator is fail-fast.

Unlike ArrayList  when the add and remove operations were done on LinkedList , the elements will not shift to right or left to the indexes like in ArrayList. Because LinkedList consists of individual nodes so when an element is added only the address will change. That is the reason LinkedList is the best choice for add and remove operations , Whereas ArrayList is recommended for retrieval operations. 

Java LinkedList Constructors

  1. public LinkedList()

Creates an empty list with default capacity 10

2. public LinkedList(Collection c)

Creates a list containing the elements specified in the Collection ‘c’. The elements were inserted in the order they are returned by the collection’s iterator.

Exceptions

Throws

NullPointerException : If the specified collection is null.

Java LinkedList Methods

Index Methods
1 addFirst()

public void addFirst(Element e)

Inserts the specified element at the beginning of the list. This method is taken from Deque interface

2  addLast()

public void addLast(Element e)

Appends the specified element at the end of the list. This method is same as add(object e) in Collection interface. addlLast() method is taken from Deque interface. 

 4  getFirst()

public E getFirst()

This method will return the first element in the list. And this method is taken from Deque interface.

Specified by

Deque Interface

Returned type = E ( returns the element)

Exceptions 

NoSuchElementException : If the list is empty.

 5 getLast()

public E getLast()

This method returns the last element in the list.

Returned type = E ( returns the element type)

Specified by 

Deque Interface

Exceptions

NoSuchElementException : If the list is empty.

 6 removeFirst()

public  E removeFirst()

This method removes the first element from the list and it returns th removed element.

Specified by 

Deque Interface

Return type = E ( returns the element type)

Exceptions

NoSuchElementException : If the list is empty

 7  removeLast()

public E removeLast()

Removes the last element in the list and returns the removed element

Specified by Deque Interface

Exceptions 

NoSuchElementException : If the list is empty

8  removeFirstOccurrence

public boolean removeFirstOccurrence(Object o)

  • Since LinkedList allows duplicate elements , If the specified element in the method occurs more than once in the list , than this method will remove the first occurrence of the specified object or element.
    • If the list does not contain the specified element , than the list will be unchanged.
  • Returns ‘true’ if the list has specified element or object

Version : 1.6 

 9  removeLastOccurrence

public boolean removeLastOccurrence(Object o)

  • Since LinkedList allows duplicate elements , If the specified element in the method occurs more than once in the list , than this method will remove the last occurrence of the specified object or element.
    • If the list does not contain the specified element , than the list will be unchanged.
  • Returns ‘true’ if the list has specified element or object

Version : 1.6 

   

 

 

 

 

 

 

One thought on “Java LinkedList

Leave a Reply

Your email address will not be published. Required fields are marked *