Pages

▼

LinkedList Java Data Structure

LinkedList Java Data Structure - 1Different data structures are created for different purposes. You may know about ArrayList (if still not, we recommend you to read about it first). In this article, we are going to learn about LinkedList and to realize what this collection is good for. If you look into LinkedList Java 8 (or later version of the language) class code source (on Oracle website or in your IDE, in case of IDEA: crtl+B on the class name) you’ll see the next declaration: 
public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable
At the moment the most important information from the code is the fact that LinkedList implements List and Deque interfaces. LinkedList Java Data Structure - 2The List interface keeps the sequence of adding items and allows access to the item by index. The “ordinary” Queue supports adding elements to the end and extracting them from the beginning. Deque is a two-way queue, and it supports adding and removing elements from both sides. You may think of it as a combination of stack and queue. So, LinkedList is an implementation of these two, and it allows us to create a bidirectional queue consist of any objects including null. LinkedList is a collection of elements. We can see it in the code source of the class, this time pay attention to the fields: 
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
Every element, usually we called it Node, contains an object and references to two neighboring objects — the previous and the next. Hence, it is not very effective in terms of using memory. LinkedList Java Data Structure - 3As LinkedList actually is a bidirectional structure, we can easily add or remove elements from both sides.

LinkedList Constructors

Back to code source, we can find out that LinkedList has two constructors
  • LinkedList() without parameters is used to construct an empty list.
  • >LinkedList(Collection<? extends E> c) is for creating a list containing the elements of the specified collection, in order, they are returned by the collection's iterator.

LinkedList Declaration

In fact, a linked list (Java or in any other language) consists of a sequence of nodes. Every node is designed to store an object of a type defined when creating. So to create LinkedList, Java code is the next: 
LinkedList<Integer> myList = new LinkedList<>();
We’ve got an object to keep a sequence of integers and links to the neighbors. However, it is empty at the moment.

LinkedList Main Operations

As usual, in the case of Collections you may put elements into LinkedList (to the end of it or into the middle), remove from there, and get an element by index. So here they are:
  • add(E element) Appends the specified element to the end of this list;
  • add(int index, E element) Inserts the element at the specified position index;
  • get(int index) Returns the element at the specified position in this list;
  • remove(int index) Removes the element that is at position index;
  • remove(Object o) Removes the first occurrence of ?o element from this list if it is there.
  • remove() Retrieves and removes the first element of the list.

Linked list implementation in Java, adding and removing elements. Example

Let’s try these operations out on practice. First, Java LinkedList implementation: creating a LinkedList of Strings, adding there 3 elements. Then remove one, then add one in the middle. 
public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }
The result of running this program: 
my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]
A LinkedList is a part of the Collection framework, you may use Iterator to remove elements, as well as a special iterator for lists — ListIterator. Even more, operations with iterator provide the main benefits of LinkedList class: good performance of insert/delete operations. Using Iterator you may get a constant time for them. Later in this article, we’ll write a code example to compare ArrayList and LinkedList+Iterator
  • Iterator.remove() removes the last element returned by this iterator.
  • ListIterator.add(E element) inserts an element into the list

Java LinkedList Example: how Iterator works

Here we have a small Java LinkedList Example code, where we try adding and deleting via Iterator. 
public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);

       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);

   }
}
The result of running this program: 
linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]
More Java LinkedList Operations:
  • addFirst(), addLast() add an element to the beginning/end of a list
  • clear() removes all elements from the list
  • contains(Object o) returns true if the list contains the o element.
  • indexOf(Object o) returns the index of the first occurrence of the o element, or -1 if it isn’t in the list.
  • set(int index, E element) replaces the element at index position with the element
  • size()Returns the quantity of elements in the list.
  • toArray() returns an array containing all list’s elements from first to the last element.
BTW being a two-sized queue, LinkedList in Java has stack specific operations:
  • pop() that pops an element from the stack (represented by the list)
  • push(E e) that pushes an element onto the stack (represented by this list)

How to reverse LinkedList: example

Here is a small example, a popular, yet an easy task for beginners. We have a LinkedList and should reverse it. The easiest algorithm is to go through the LinkedList in reverse order and put every element into the new one. However, maybe you will find a better way? Here is the code of reverse linked list java program: 
public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}
The result: 
[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: when to use the first one

Both LinkedList and ArrayList are implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it using a dynamically resizing array. As you already know, every node of LinkedList contains Objects and two references to the neighbors. That means additional memory costs for storing references between elements in the case of Java LinkedList. ArrayList implements it with a dynamically resizing array. Some of LinkedList and ArrayList operations look the same, but they work in a different way. In the ArrayList case, you manipulate with internal arrays, in LinkedList — with references. ArrayList is the most popular List implementation. You definitely should use ArrayList when index access is a priority since these operations are performed in constant time. Adding to the end of the list on average is also done in constant time. Even more, ArrayList does not have additional costs for storing a bunch of elements. You may count as Cons the speed of insertion and removing operations when it is done not at the end of the list. LinkedList is more useful in case of the insert and delete operations performance in some ways: if you use iterators it occurs in constant time. Access operations by index are performed by searching from the beginning of the end (whichever is closer) to the desired element. However, don’t forget about additional costs for storing references between elements. So here standard LinkedList and ArrayList operations with algorithmic runtimes. N refers to the number of items that are already on the list. O(N) means that in the worst case we should “walk” through the whole list until the needed position is found, for example, for insertion of the new element into the list. O(1) means that the operation happens in constant time, independently on the number of items.

LinkedList Time Complexity

LinkedList Java OperationAlgorithmic effectiveness
get(int index)O(n), on average — n/4 steps, where n is a LinkedList size
add(E element)O(1)
add(int index, E element)O(n), on average — n/4 steps; if index = 0 then O(1), so if you need to add something in the beginning of the list, LinkedList<E> could be a good choice
remove(int index)O(n), on average — n/4 steps
Iterator.remove()O(1) This is the main reason to use LinkedList<E>

ArrayList Time Complexity

LinkedList OperationAlgorithmic effectiveness
get(int index)O(1), one of the main reasons to use ArrayList<E>
add(E element)O(n) is the worst case since the array must be resized and copied, however, in practice, it is not so bad
add(int index, E element)O(n), n/2 steps on average
remove(int index)O(n), n/2 steps on average
Iterator.remove()O(n), n/2 steps on average
ListIterator.add(E element)O(n), n/2 steps on average

When to use LinkedList: Example

Definitely, ArrayList is the most popular List implementation. However, you may meet the situations, when the add/remove operations are needed too often. In that case, LinkedList all together with Iterator could be beneficial. Here is an example. We’ve got a long list, and we should delete every element from this list. Let’s do this task with ArrayList and LinkedList + Iterator. We compare the time of every operation and print it out into console. Here the code: 
import java.util.*;
import java.util.function.BiPredicate;

public class ListTest2 {

   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());

       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }

   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);

           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }

   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }

   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}
Result for ArrayList: 
start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414
Result for LinkedList: 
start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458
As you can see in this case LinkedList is way more effective. Let's be honest. In real software development LinkedList usage is a kind of rare event. Nevertheless, a professional should know about this data structure existence and its advantages. If in real code LinkedList is a rare guest, on Java Junior interviews it is very popular. And yet, here is what Avtor Joshua Bloch wrote about LinkedList: LinkedList Java Data Structure - 4

AddOn: Singly Linked List Java

There is no Singly Linked List among classical Collection in Java, Singly Linked List is a structure where every node contains an Object and a reference to the next Node, but not for the previous one. Java LinkedList is two-linked, but nobody interferes with you to create your own Data Structure, such as a Singly ,code>Linked List. Here are some steps to solve these tasks:
  1. Create a Node class with two attributes, data and next. Next is a reference to the next node.
  2. Create FirstLast class with two attributes, head, and tail.
  3. Create an add() method to add a new node to the list. Check if the list is empty first (head == null). If so, head and tail refer to the new node. If the list is not empty, the new node will be added to the end, so the next attribute of the tail refers to the added node and the new node becomes the tail of the list.
at

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.