JAVA / JAVA COLLECTIONS FRAMEWORK /
LINKEDLIST

Implements List, Queue and Deque.

Linked list data structure.

An element is a node, contains 3 fields:

• prev: address of the previous element, null if the node is the first element

• next: address of the next element, null if the node is the last element

• data: the element data

The elements are not stored in order, instead, the order can be followed be using prev and next addresses.

EXAMPLE FOR CREATING LINKEDLIST INSTANCES:

In case Queue and Deque, only methods of those interfaces will be available.

Methods of LinkedList are the following in the example below.

EXAMPLE FOR LINKEDLIST METHODS:

The addAll() method can add elements of any Collection type to the LinkedList.

To add to, remove from, set and reach elements of a LinkedList, also can use the Iterator and the ListIterator classes:

• ll2.iterator() -> Iterator<elementType>

• ll2.listIterator() -> ListIterator<elementType>

Since LinkedList implements Queue and Deque, can be used as a queue or as a deque, it has the next methods as well (see their usage there):

• addFirst()

• addLast()

• getFirst()

• getLast()

• removeFirst()

• removeLast()

• peek()

• poll()

• offer()

Differences between ArrayList and LinkedList:

• ArrayList implements List, LinkedList implements List, Queue and Deque

• ArrayList stores a simple value, LinkedList stores the element, previous and next addresses

• ArrayList provides a resizeable array, LinkedList provides a doubly-linked list

• For inserting element, ArrayList shifts all elements after, LinkedList modifies prev and next fields in the surrounding nodes

• To access data, in ArrayList elements can be accessed randomly, in LinkedList sequentially

Differences between ArrayDeque and LinkedList:

• Both implements Deque

• LinkedList supports null elements, ArrayDeque does not

• LinkedList nodes contain data plus addresses of next and prev therefore needs more memory than ArrayDeque

• ArrayDeque is faster than LinkedList

JUMP TO TOP