Linkedlist

It is a linear data structure, unlike arrays it is not stored at contiguous location, the elements called nodes are linked using pointers, each pointer pointing to the next node.

Each node consists of mainly two part:

• Data
• Reference Link or address of next node and previous node

In java internally linkedlist is implemented using doubly linked list, in which we can add & remove elements from both sides of the list.

Features of LinkedList

• Java LinkedList is an implementation of the List and Deque interfaces. It extends AbstractSequentialList and implements List and Deque interfaces.
• It maintains the insertion order of the elements and also allow null elements.
• In Java applications, we can use it as a List, stack or queue.
• It does not support random access as it doesn’t implement RandomAccess Interface, so you cannot access elements randomly you have to access it sequentially(whereas Stack & ArrayList do implement this interface).
• You can use ListIterator/Iterator to iterate LinkedList elements.

Different Ways to iterate over LinkedList

      
import java.util.LinkedList;
import java.util.Iterator;
public class ProgrammerTodayLinkedListExample{

  public static void main(String[] args) {

   LinkedList<String> list = new LinkedList<String>();
   list.add("welcome");
   list.add("to");
   list.add("LinkedList");
      
   System.out.println("*****Iterate Using Iterator*****");
   for (Iterator i = list.iterator(); i.hasNext();) {
     System.out.println(i.next());
   }
   
   System.out.println("*****Iterate Using ListIterator*****");
   ListIterator<String> listIterator = linkedList.listIterator();
   while (listIterator.hasNext()) {
     System.out.println(listIterator.next());
   }
   
   System.out.println("*****Iterate Using Traditional for loop*****");
   for (int i = 0; i < list .size(); i++) {
     System.out.println(list .get(i));
   }
    
   System.out.println("*****Iterate using Java8 forEach loop*****");
   // forEach Performs the given action for each element of the Iterable until 
   // all elements have been processed or the action throws an exception.
   linkedList.forEach(System.out::println); 
  }
}

OUTPUT

    
*****Iterate Using Iterator*****
welcome
to
LinkedList
*****Iterate Using ListIterator*****
welcome
to
LinkedList
*****Iterate Using Traditional for loop*****
welcome
to
LinkedList
*****Iterate using Java8 forEach loop*****
welcome
to
LinkedList    
    

LinkedList as Deque

Observe below in code block that on the left is the Deque Interface reference which creates a LinkedList object on the right. By this way linkedList can inherit Deque methods like addFirst(), addLast(), removeFirst(), removeLast(), etc methods.

    
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeExample 
{
  public static void main(String[] args) 
  {
  Deque<String> listDeque= new LinkedList<String>();
  listDeque.add(2);
  listDeque.addFirst(1);
  listDeque.addLast(3);
  listDeque.addFirst(0);
  listDeque.addLast(4);
      
  System.out.println("LinkedList contents : " + listDeque);
  System.out.println("LinkedList size : " + listDeque.size());
  listDeque.removeFirst();
  listDeque.removeLast();
  
  System.out.println("LinkedList contents : " + listDeque);
  System.out.println("LinkedList size : " + listDeque.size());	
  }
}

OUTPUT

      
  LinkedList contents : [0, 1, 2, 3, 4]
  LinkedList size : 5
  LinkedList contents : [1, 2, 3]
  LinkedList size : 3
  

LinkedList to Streams in Java 8

In java 8 use streams with forEach loop to iterate over the linkedlist.

    
List<Integer> ptlist= new LinkedList<>();
ptlist.add(11);
ptlist.add(22);
ptlist.add(33);
  
//Using stream to iterate through the List
ptlist.stream().forEach(System.out::println);
  

OUTPUT

    
11
22
33 
  

Difference between ArrayList and LinkedList | Usage

S.No	ArrayList	LinkedList
1	Insertions & deletions are slower	Insertions & deletions are easy and fast in LinkedList because there is no resizing like arrays and then copying to another array if it gets full.
2	Memory overhead is less as compared to LL as it stores only the data	Memory overhead is more as it stores both address and data
3	Accessing an element in an array is fast	while Linked list takes linear time(i.e have to start from the head), so it is quite a bit slower
4	Arrays are of fixed size	Linked lists are dynamic and flexible and can expand and contract its size
5	In an array, memory is assigned during compile time	while in a Linked list it is allocated during execution or runtime
4	Arrays are of fixed size	Linked lists are dynamic and flexible and can expand and contract its size

Example : Reverse a LinkedList without creating another one(without using additional space)

Algorithm:

1. Create a linked list with n elements.
2. Run the loop for n/2 times where ‘n’ is the number of elements in the linkedlist.
3. In the first pass, Swap the first and nth element.
4. In the second pass, Swap the second and (n-1)th element and so on till you reach the mid of the linked list.
5. Return the linked list after loop termination.

      
import java.util.*; 

public class LinkedListTest2 { 
public static void main(String[] args) 
{ 
    // Declaring linkedlist without any initial size 
    LinkedList<Integer> linkedli = new LinkedList<Integer>(); 

    // Appending elements at the end of the list 
    linkedli.add(new Integer(1)); 
    linkedli.add(new Integer(2)); 
    linkedli.add(new Integer(3)); 
    linkedli.add(new Integer(4)); 
    linkedli.add(new Integer(5)); 
    System.out.print("Elements before reversing: " + linkedli); 

    // Calling user defined function for reversing 
    linkedli = reverseLinkedList(linkedli); // or use Collections.reverse(linkedli); 
    System.out.print("\nElements after reversing: " + linkedli); 
} 

// Takes a linkedlist as a parameter and returns a reversed linkedlist 
public static LinkedList<Integer> reverseLinkedList(LinkedList<Integer> llist) 
{ 
    for (int i = 0; i < llist.size() / 2; i++) { 
        Integer temp = llist.get(i); 
        llist.set(i, llist.get(llist.size() - i - 1)); 
        llist.set(llist.size() - i - 1, temp); 
    } 

    // Return the reversed arraylist 
    return llist; 
} 
} 

Time Complexity: O(n/2)
Space Complexity: O(1)

Output:

Elements before reversing: [1, 2, 3, 4, 5]
Elements after reversing: [5, 4, 3, 2, 1]

Good To Know – Internal working of LinkedList

Click “Internals of LinkedList” to Read More …

---