LinkedList contains group of elements in the form of nodes. The linked lists are used to store array of data. It is a linear data structure in which each element is separate object.
- LinkedList contains set of nodes.
- Each node contains some of the data and link to the next node.
- When link of next node is empty then it’s come to the end of the list.
- In LinkedList the number of nodes is not fixed it can changed by users demand.
- Linked List is as same as array list but difference is that an array is of fixed type and a linked list can grow in size when there is a need to add more elements in the list.
- Linked list is an implementation of the list interface.
also read:
Collection Diagram of LinkedList
LinkedList Features
- Linked list contain duplicate element.
- Linked list maintain insertion order, means first element will be added in first position.
- Linked list doesn’t support random access for retrieving values.
- Linked list is not synchronized, means it cannot be shared between multiple threads without external synchronization.
Linked List Advantages
- In a linked list it easy to insert and delete an element from the list.
- Linked list is a dynamic data structure.
- Linked list can grow in size when there is a need to add more elements in the list.
- Linear data structure like Stack, Queue can be easily implemented using linked list.
Linked List Disadvantages
- Random access is not allowed in the linked list.
- There is a need of extra storage space for pointer is required in linked list.
- Reverse traversing is difficult in linked list.
LinkedList Syntax
LinkedList< String> myList = new LinkedList< String>();
In the above syntax, the LinkedList contains parameters of type String and creates a new LinkedList object using new operator.
Types of LinkedList
The LinkedList contains the following types.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Singly LinkedList
Singly Linked Lists are the type of data structure. In this type of linked list each node points to the next node and tail node or end node points to nothing. This list does not store any reference to the previous node.
Each element in this list is made up of two items the data and the reference to the next node last node points to null. Above figure shows the working of singly Linked list. In this each node that are A, B, and C points to the next node and the end node points to nothing or null.
Doubly LinkedList
In this type of linked list each node points to next node as well as previous node. In doubly linked list both head node and end node points to nothing. This is useful to move back node that we want not from the beginning. A doubly linked list allows list to traversed from tail to head.
In this list each node has two references one for the next node and another for its previous node. In the above figure each node A, B, and C points to their next node and its previous node. The end node or tail node points to nothing.
Circular LinkedList
In this type of Linked list is made circular by linking first and last node. In this type head elements previous pointer points to the tail element and the tail element’s next pointer points to the head element.
In this list last node of the list points back to the first node of the list. In the above figure each node points out to the one another and the tail node points to the head node.
LinkedList Constructors
- LinkedList( ): This constructor creates an empty Linked List
- LinkedList( Collection C): This constructor is used to construct the list that contains the elements of specified collection.
LinkedList Methods
Methods | Description |
---|---|
Boolean addAll(Collection c) | This method is used to add the elements in the specified collection to the end of the list, in the order that they are returned by the specified collection’s iterator. |
Boolean add(object o) | This method is used to add all the elements in the specified collection to the end of the list. |
boolean addAll(int index, Collection c) | It inserts all the elements of the collection into the LinkedList, starting at the specified position. |
void add(int index, Object element) | This method can insert specified element at the specified position in the linked list. |
boolean remove(object o) | It removes first occurrence of specified element from the list. |
element remove(object o) | This method can remove specified element at the specified position in the linked list. |
void clear() | This method can remove all the elements from the linked list. |
boolean contains(Object o) | It returns true if the linked list contains specified element. |
void addFirst(Object o) | This method is used to insert the element at the first position of the linked list. |
void addLast(Object o) | This method adds the specified element to the end of the linked list. |
Object get(int index) | This method returns the element at the specified position in the LinkedList. |
Object getFirst() | This method returns first element in the linked list. |
Object getLast() | This method returns last element in the list. |
int indexOf(Object o) | >It returns first occurrence of the specified element in the list or -1 if element not found in the list. |
int lastIndexOf(Object o) | It returns last occurrence of the specified element in the list or -1 if element not found in the list. |
ListIterator listiterator(int index) | It returns a list iterator of the element in the list starting at specified position in the list. |
int size | It returns the number of element in the linked list. |
Object remove(int index) | It removes the element in the list at the specified position. |
Object removeFirst() | It removes the first element from the linked list. |
Object removeLast() | It removes the last element from the linked list. |
Object[] to Array() | It coverts linked list into an array of Object class type. All the elements in the list are stored in correct order. |
Object[] toArray(Object [] a) | It returns all the elements in the list are stored in correct order; the run type of returned array is that of the specified array. |
Object set(int index, Object element) | It replaces the element at specified position in the list with specified element . |
Simple Example of LinkedList
package mypackage; import java.util.LinkedList; public class LinkedlistExample { public static void main(String a[]){ LinkedList<String> ll = new LinkedList<String>(); ll.add("Sachin"); ll.add("Ganguly"); ll.add("Raina"); ll.add("Dhoni"); System.out.println(ll); System.out.println("Size of the linked list: "+ll.size()); System.out.println("Is LinkedList empty? "+ll.isEmpty()); System.out.println("Does LinkedList contains 'Raina'? "+ll.contains("Raina")); } }
- LinkedList ll = new LinkedList(); this line defines the linked list interface which is used create a new LinkedList object using new operator.
- We can use ll.add() method to add the elements in the linked list where ll is the object.
- System.out.println(ll); this line displays the elements in the linked list.
- We can display the total size of the list by using ll.size() method; to check the linked list is empty or not we use ll.isEmpty() method and to check the specified content in the list we use ll.contains() method.
When you run the above example, you would get the following output:
Example using LinkedList Methods
package mypackage; import java.util.LinkedList; public class LinkedlistMethod { public static void main(String args[]) { LinkedList ll = new LinkedList(); ll.add("F"); ll.add("B"); ll.add("D"); ll.add("E"); ll.add("C"); ll.addLast("Z"); ll.addFirst("A"); ll.add(1, "A2"); System.out.println("Original contents of ll: " + ll); ll.remove("F"); ll.remove(6); System.out.println("Contents of ll after deletion: " + ll); ll.removeFirst(); ll.removeLast(); System.out.println("ll after deleting first and last: " + ll); Object val = ll.get(2); ll.set(2, (String) val + " Changed"); System.out.println("ll after change: " + ll); ll.clear(); System.out.println("LinkedList now contains : " + ll); } }
- import java.util.LinkedList; It defines a number of useful classes.
- LinkedList ll = new LinkedList(); this line defines the linked list interface which is used create a new LinkedList object using new operator.
- We can use ‘ll.add()’ method to add the elements in the linked list where ‘ll’ is the object.
- In the above example we have used the ‘ll.remove’ method for removing a specified element from the linked list.
- To remove first element from the list, we have used ‘ll.removeFirst()’ method and to remove last element from the list, use ‘ll.removeLast()’ method.
- We have used ‘ll.clear()’ method for removing all the elements from the list.
When you run the above example, you would get the following output: