LinkedList in java

As we have seen earlier, ArrayList is not so good when it comes to adding/removing elements using index. This is solved using the LinkedList in java.

Few points about LinkedList to remember

1. It implements the List and Dequeue interfaces
2. It is a non synchronized collection
3. It maintains the insertion order of elements
4. It allows duplicate values
5. It internally uses Doubly LinkedList data structure
6. You can synchronize LinkedList using Collections.synchronizedList() method

How LinkedList in java internally works

LinkedList stores the elements in form of Nodes and internally uses Doubly linked list data structure. This means each Node has a reference to its previous and next Node.
LinkedList in Java

How add works

When an element is added in LinkedList only the nodes of the before and after elements get changed.
For example. If you have an LinkedList with 5 elements and you add a new element at the 4th index. In this case, the element is added in 4th index . Reference of 3rd node now points to new 4th node, and reference of new 4th node now points to the old 4th node (new 5th node). Since only 2 nodes get changed, adding elements at a particular index is very fast in LinkedList as compared to ArrayList.
LinkedList in java how add works

Similar to ArrayList, LinkedList has 2 versions of add() for adding individual elements.
1. public boolean add(E e)
Adding an elements without providing an index, will add the element at the last.
the linkLast() method is called which does the operation.

public boolean add(E e) {
	linkLast(e);
	return true;
}

void linkLast(E e) {
	final Node<E> l = last;
	final Node<E> newNode = new Node<>(l, e, null);
	last = newNode;
	if (l == null)
		first = newNode;
	else
		l.next = newNode;
	size++;
	modCount++;
}

public boolean add(E e) {

linkLast(e);

return true;

}

void linkLast(E e) {

final Node<E> l = last;

final Node<E> newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

modCount++;

}

2. public void add(int index, E element)
When you give an index for adding the element, either linkLast or linkBefore method is called depending on the index provided. If the index prodvided is equal to the size of the list, then linkLast is called, else linkBefore is called.

public void add(int index, E element) {
	checkPositionIndex(index);

	if (index == size)
		linkLast(element);
	else
		linkBefore(element, node(index));
}

void linkLast(E e) {
	final Node<E> l = last;
	final Node<E> newNode = new Node<>(l, e, null);
	last = newNode;
	if (l == null)
		first = newNode;
	else
		l.next = newNode;
	size++;
	modCount++;
}

void linkBefore(E e, Node<E> succ) {
	// assert succ != null;
	final Node<E> pred = succ.prev;
	final Node<E> newNode = new Node<>(pred, e, succ);
	succ.prev = newNode;
	if (pred == null)
		first = newNode;
	else
		pred.next = newNode;
	size++;
	modCount++;
}

public void add(int index, E element) {

checkPositionIndex(index);

if (index == size)

linkLast(element);

else

linkBefore(element, node(index));

}

void linkLast(E e) {

final Node<E> l = last;

final Node<E> newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

modCount++;

}

void linkBefore(E e, Node<E> succ) {

// assert succ != null;

final Node<E> pred = succ.prev;

final Node<E> newNode = new Node<>(pred, e, succ);

succ.prev = newNode;

if (pred == null)

first = newNode;

else

pred.next = newNode;

size++;

modCount++;

}

How remove works

Removing an element from a particular index is also similar to how add works.
or example. If you have an LinkedList with 5 elements and you remove element from the 4th index. In this case reference of 3rd node now points to 5th node, and 4th node is made null or removed.
Since only 2 nodes get changed, removing elements at a particular index is very fast in LinkedList as compared to ArrayList.
LinkedList in java how remove works

public E remove(int index) {
	checkElementIndex(index);
	return unlink(node(index));
}

E unlink(Node<E> x) {
	// assert x != null;
	final E element = x.item;
	final Node<E> next = x.next;
	final Node<E> prev = x.prev;

	if (prev == null) {
		first = next;
	} else {
		prev.next = next;
		x.prev = null;
	}

	if (next == null) {
		last = prev;
	} else {
		next.prev = prev;
		x.next = null;
	}

	x.item = null;
	size--;
	modCount++;
	return element;
}

public E remove(int index) {

checkElementIndex(index);

return unlink(node(index));

}

E unlink(Node<E> x) {

// assert x != null;

final E element = x.item;

final Node<E> next = x.next;

final Node<E> prev = x.prev;

if (prev == null) {

first = next;

} else {

prev.next = next;

x.prev = null;

}

if (next == null) {

last = prev;

} else {

next.prev = prev;

x.next = null;

}

x.item = null;

size--;

modCount++;

return element;

}

Constructors

LinkedList()
Constructs an empty list.

LinkedList(Collection c)
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.

When to use LinkedList

LinkedList can be used in below scenarios
1. If you are not sure on the size of the list and if the size is going to increase
2. If you want to add/remove elements in between the list using index.
3. If you do not need to iterate over the list
4. If memory is not a constraint, as LinkedList in java takes more memory than ArrayList, due to the references of each node pointing to other node.

Methods used

1. boolean add(E e)
Appends the specified element to the end of this list.

2. void add(int index, E element)
Inserts the specified element at the specified position in this list.

3. boolean addAll(Collection c)
Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator.

4. boolean addAll(int index, Collection c)
Inserts all of the elements in the specified collection into this list, starting at the specified position.

5. void addFirst(E e)
Inserts the specified element at the beginning of this list.

6. void addLast(E e)
Appends the specified element to the end of this list.

7. void clear()
Removes all of the elements from this list.

8. boolean contains(Object o)
Returns true if this list contains the specified element.

9. Iterator descendingIterator()
Returns an iterator over the elements in this deque in reverse sequential order.

10. E peek()
Retrieves, but does not remove, the head (first element) of this list.

11. E peekFirst()
Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.

12.E peekLast()
Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

13. E poll()
Retrieves and removes the head (first element) of this list.

14. E pollFirst()
Retrieves and removes the first element of this list, or returns null if this list is empty.

15. E pollLast()
Retrieves and removes the last element of this list, or returns null if this list is empty.

16. E pop()
Pops an element from the stack represented by this list.

17. void push(E e)
Pushes an element onto the stack represented by this list.

18. E remove()
Retrieves and removes the head (first element) of this list.

19. E remove(int index)
Removes the element at the specified position in this list.

20. boolean remove(Object o)
Removes the first occurrence of the specified element from this list, if it is present.

21. E removeFirst()
Removes and returns the first element from this list.

22. E removeLast()
Removes and returns the last element from this list.

References

1. LinkedList java docs