LinkedList in java

People who write code use LinkedList in Java but they do not really know how it works on the inside. In this article I will tell you about the working of LinkedList the common methods people use with it when to use it and how long it takes to do things.

What is LinkedList?

LinkedList is a way to store data in Java that can change size. It stores things in nodes. Each node has:

The information

A link to the node that comes before it

A link to the node that comes after it

Javas LinkedList class uses something called a Doubly Linked List inside. This means every node knows about the nodes that come before and after it.

LinkedList<String> list = new LinkedList<>();

Types of Linked Lists

There are three common types of linked lists:

1. Singly Linked List

• Each node points only to the next node.

2. Doubly Linked List

• Each node points to both the previous and next nodes.

3. Circular Linked List

• The last node points back to the first node.

Why Use LinkedList?

Although you can use ArrayList to add and remove things LinkedList is better when you need to add or remove things at the start or in the middle of the list. This is because the other things in the list do not need to be moved.

Common use cases include:

• Music playlists, where you want to go to the previous song
• Browser history, where you want to go back or forward
• Undo and Redo functions

However if your program needs to get things from the list using their position ArrayList is usually a better choice. This is because it can get things faster.

Get Sonu Diwse’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Adding Elements

LinkedList<String> list = new LinkedList<>();

list.add("Java");
list.addFirst("Spring");
list.addLast("AWS");

Methods:

• add(E e)
• add(int index, E element)
• addFirst(E e)
• addLast(E e)
• offer(E e)
• offerFirst(E e)
• offerLast(E e)

Retrieving Elements

list.get(0);
list.getFirst();
list.getLast();

Methods:

• get(int index)
• getFirst()
• getLast()
• peek()
• peekFirst()
• peekLast()

Removing Elements

list.remove();
list.removeFirst();
list.removeLast();

Methods:

• remove()
• remove(int index)
• remove(Object o)
• removeFirst()
• removeLast()
• poll()
• pollFirst()
• pollLast()

Searching Elements

list.contains("Java");
list.indexOf("Java");
list.lastIndexOf("Java");

Methods:

• contains(Object o)
• indexOf(Object o)
• lastIndexOf(Object o)

Updating Elements

list.set(0, "React");

Methods:

• set(int index, E element)

Size and Utility Methods

list.size();
list.isEmpty();
list.clear();

Stack Operations

list.push("Java");
list.pop();

Queue Operations

list.offer("Java");
list.poll();
list.peek();

Time Complexity

Operation

addFirst()O(1)

addLast()O(1)

removeFirst()O(1)

removeLast()O(1)

get(index)O(n)

add(index)O(n)

remove(index)O(n)

searchO(n)

Conclusion

LinkedList is a good way to store data in Java when you need to add or remove things often. If you need to get things from the list using their position ArrayList is usually a better choice. This is because ArrayList can get things faster.