Understanding Java LinkedList for DSA

A LinkedList in Java is another implementation of the List interface, but unlike ArrayList, it is a doubly-linked list. This means each element in the list is a node that contains a reference to the next and previous nodes.

Key Characteristics

Doubly-Linked: Each element (node) in the list references the next and previous elements.
Ordered Collection: Maintains the insertion order of elements.
Null Elements: Allows the storage of null values.
Duplicates: Allows duplicate elements.
Not Synchronized: By default, LinkedList is not thread-safe. For concurrent access, use Collections.synchronizedList.
Efficient Insertions/Deletions: Efficient for inserting and deleting elements in the middle of the list because it only requires changing the links.

Constructors

LinkedList(): Constructs an empty list.

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

LinkedList(Collection<? extends E> c): Constructs a list containing the elements of the specified collection in the order they are returned by the collection's iterator.
```
 List<String> anotherList = Arrays.asList("A", "B", "C");
 LinkedList<String> list = new LinkedList<>(anotherList);
```

Common Methods

add(E e): Appends the specified element to the end of this list.
```
 list.add("Apple");
```
add(int index, E element): Inserts the specified element at the specified position in this list.
```
 list.add(1, "Banana");
```
get(int index): Returns the element at the specified position in this list.
```
 String fruit = list.get(0);
```
remove(int index): Removes the element at the specified position in this list.
```
 list.remove(1);
```
remove(Object o): Removes the first occurrence of the specified element from this list if it is present.
```
 list.remove("Apple");
```
contains(Object o): Returns true if this list contains the specified element.
```
 boolean hasApple = list.contains("Apple");
```
size(): Returns the number of elements in this list.
```
 int size = list.size();
```
isEmpty(): Returns true if this list contains no elements.
```
 boolean isEmpty = list.isEmpty();
```
clear(): Removes all of the elements from this list.
```
 list.clear();
```
set(int index, E element): Replaces the element with the specified element at the specified position in this list.
```
list.set(0, "Cherry");
```

Additional Methods

Since LinkedList also implements the Deque interface, it provides methods for double-ended queue operations:

addFirst(E e): Inserts the specified element at the front of this list.
```
 list.addFirst("First");
```
addLast(E e): Inserts the specified element at the end of this list.
```
 list.addLast("Last");
```
removeFirst(): Removes and returns the first element from this list.
```
 String first = list.removeFirst();
```
removeLast(): Removes and returns the last element from this list.
```
 String last = list.removeLast();
```
getFirst(): Returns the first element in this list.
```
 String first = list.getFirst();
```
getLast(): Returns the last element in this list.
```
 String last = list.getLast();
```

Iteration

LinkedList can be iterated using various methods such as for-each loop, iterators, and streams.

for (String item : list) {
    System.out.println(item);
}

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

list.forEach(System.out::println);

Performance Considerations

Random Access: O(n)
Insertion/Deletion at the beginning/end: O(1)
Insertion/Deletion at a specific index: O(n)
Search: O(n)

Thank you for reading!

You can support me by buying me a book.