- LinkedList Constructors
- LinkedList Declaration
- LinkedList Main Operations
- Linked list implementation in Java, adding and removing elements. Example
- Java LinkedList Example: how Iterator works
- How to reverse LinkedList: example
- LinkedList vs ArrayList: when to use the first one
- When to use LinkedList: Example
- AddOn: Singly Linked List Java
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:
At the moment the most important information from the code is the fact that LinkedList implements
List
and Deque
interfaces.
The 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:
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.
As 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 thatLinkedList
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 createLinkedList
, Java code is the next:
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 intoLinkedList
(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 theelement
at the specified positionindex
;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.The result of running this program:
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 JavaLinkedList
Example code, where we try adding and deleting via Iterator.
The result of running this program:
More Java
LinkedList
Operations:
addFirst()
, addLast() add an element to the beginning/end of a listclear()
removes all elements from the listcontains(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 elementsize()Returns
the quantity of elements in the list.toArray()
returns an array containing all list’s elements from first to the last element.
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 aLinkedList
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:
The result:
LinkedList vs ArrayList: when to use the first one
BothLinkedList
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 Operation | Algorithmic 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 Operation | Algorithmic 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:
Result for ArrayList:
Result for LinkedList:
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
:
AddOn: Singly Linked List Java
There is no SinglyLinked 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:
- Create a
Node
class with two attributes, data and next. Next is a reference to the next node. - Create
FirstLast
class with two attributes, head, and tail. - 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.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.