Java Study Point (Java iQ): LinkedList


public class LinkedList<E>
 extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, Serializable

Type Parameters:
E - the type of elements held in this collection

All Implemented Interfaces:
Serializable, Cloneable, Iterable, Collection, Deque, List, Queue

LinkedList class is a part of Java’s collections framework and is present in java.util package.
LinkedList Class is implements List and Deque interfaces and extends AbstractList.It use Doubly-linked list to store data.So we can perform all operations of list and queue. ArrayList used Node internally.
As LinkedList doubly-linked list to store data, doubly-linked list consists of a collection of nodes, where each node have a pointer/reference to the next node and previous node in the list.

Iterating over a LinkedList:-

iterator()
listIterator()
simple for-each loop
Java 8 forEach() and lambda expression.
iterator() and Java 8 forEachRemaining() method
descendingIterator()

Summary of LinkedList:-

LinkedList class can contain duplicate elements and null values.
LinkedList maintains the insertion order i.e it is an ordered collection.
LinkedList can store only objects, not primitives that means if we store primitive types like int, char etc. it we be autoboxed to wrapper classes of same types like Integer, Character, Boolean etc.
LinkedList is non-synchronized i.e. LinkedList is not thread-safe
Manipulation i.e adding or removing elements with LinkedList() is faster as compared to ArrayList() becaues no shifting need to be occured.
LinkedList is slower than ArrayList if I randomly access its elements i.e. get() operation.Because it requires a sequential scan from the front or back of the list
Default Capacity : Constructs empty list. we can not define initial size of LinkedList like ArrayList. it create empty constructs list.
LinkedList can be use as list, skack or queue.
LinkedList consumes more memory than an ArrayList because it also stores the next and previous references along with the data.

Time complexity

Time complexity for add() – add an element to the end of the Linkedlist. It only updates a tail, and hence, it's O(1) constant-time complexity.
Time complexity add(index, element) – on average runs in O(n) time
Time complexity get() – search an element takes O(n) time.
Time complexity remove(element) – to remove an element from linkedlist, we first need to find it. This operation is O(n).
Time complexity remove(index) – to remove an element by index from linkedlist, we first need to travers the linklist from the beginning; hence, the overall complexity is O(n).
Time complexity contains() – also has O(n) time complexity

Methods Of LinkedList Class:-

boolean add(Object o)
void add(int index, Object o)
boolean addAll(Collection c):
boolean addAll(int index, Collection c):
void addFirst(Object o):
void addLast(Object o):
void clear(): Remove all elements from list.
Object clone(): returns the copy of the Linked List object.
boolean contains(Object o):
Object get(int index):
Object getFirst():
Object getLast():
int indexOf(Object o): return index of element.If element not present return -1
int lastIndexOf(Object o): if element not present return -1
ListIterator listIterator(int index): returns an object of Iterator class that contains the elements in proper sequence starting from the specified position as mentioned in the argument.
Object remove(int index): if index specified is out of range. It returns an IndexOutOfBoundsException exception.
boolean remove(Object o): This will deletes the first occurrence of given element in the list.
Object removeFirst(): removes the head element from this linked list.
Object removeLast(): removes the last element from this linked list.
boolean removeFirstOccurrence(Object o): It is used to remove the first occurrence of the specified element in a list (when traversing the list from head to tail).
boolean removeLastOccurrence(Object o): removes the last occurrence of the specified element in a list (when traversing the list from head to tail).
Object set(int index, Object element): replaces the content at index in argument list.
int size(): returns the size of the Linked List i.e. number of elements in the list.
Object[] toArray(): converts the list to array.
<T> T[] toArray(T[] a):
Iterator<E> descendingIterator(): return an iterator over the elements in a deque in reverse sequential order.
E element(): It is used to retrieve the first element of a list.
boolean offer(E e): It adds the element as the last element of a list.
boolean offerFirst(E e): It inserts the specified element at the front of a list.
boolean offerLast(E e): inserts the element at the end of a list.
E peek(): return the first element of a list.
E peekFirst(): return the first element of a list or returns null if a list is empty.
E peekLast(): return the last element of a list or returns null if a list is empty.
E poll(): return and removes the first element of a list.
E pollFirst():return and removes the first element of a list, or returns null if a list is empty.
E pollLast(): return and removes the last element of a list, or returns null if a list is empty.
E pop(): pops an element from the stack.
void push(E e): pushes an element onto the stack.

Related Tutorials

Pages

Search

Thursday, July 23, 2020

LinkedList

No comments:

Post a Comment