Understanding LinkedLists in Java
Linked Lists are an implementation of the AbstractList class in which we have an linear ordering of objects where each node has 32 components: the object, and a pointer to the next object in the list. The Linked List Object itself generally references a “head” node, or the first node in the linked list.
Use Cases
Linked Lists are extremely useful for constant time addition and deletion of elements. To add an element, all we have to do is change the pointer of the last object in the List to the new object. We can also treat the list as a first in — first out data structure, aka a “queue”.
Linked Lists may not be as useful when we need to grab a specific element of the index, as we don’t know where it is located at. When we want to grab a specific index, we have to iterate through the array up to that index which is a O(n) time operation compared to the constant time getIndex operation of a normal array.
LinkedLists can either be singular or doubly linked. A single linked list is one where each object only points to the next one in the List, not allowing us the ability to iterate backwards. Doubly linked lists have pointers to the previous and next node, allowing us to move freely in either direction till we hit the head or the tail.
Class Methods
The class holds various methods for both construction and utilizing the data structure
- add(E e) — adds an element e to the end of the List
- clear() — removes all elements
- contains(Object o) — returns true if the list contains o
- get(int index) — gets the object at the index
- indexOf(Object o) — returns index of object
- peek() — Returns the object at the end of the list
- pop() — removes the object at the end
- remove(Object O) — removes specified object
