3. LinkedList

[Dhanrajpatil123]

LinkedList

• LinkedList is a implementation class of List Interface

                             List
                 -------------------------------
          1. ArrayList                2. LinkedList

• Inside a linked list we can store data in the form of Node like that -> | data | address | .

• Node --> It is nothing but data + pointer

• data -> here we can store actual data or we can say that value

• address -> here we can store address of next value

Types of LinkedList

---

1. Single LinkedList
2. Doubly LinkedList
3. Circular LinkedList

---

Now we talks about Java LinkedList

• The LinkedList class in Java is a part of Collection Framework and implements the List Interface.
• Unlike an ArrayList, which uses a dynamic array to store the elements, a LinkedList stores its elements as nodes in a doubly LinkedList.
• This provides different performance characteristics and usage scenarios compared to ArrayList.

class Node{

    public int value;   // value

    public Node next;   // reference to the next node
}

public class VariableDataTypeEx {

    public static void main(String[] args) {

        Node node1 = new Node();
        node1.value = 1;
        node1.next = null;

        Node node2 = new Node();
        node2.value = 2;
        node1.next = node2;
        node2.next = null;

    }
}

• A LinkedList is a linear data structure where each element is a separate object called a node.
• Each node contains two parts :
• Data : The value stored in the node.
• Pointers : Two pointers, one pointing to the next node ( next ) and the other pointing to the previous node ( previous ).

---

Performance Considerations

---

LinkedList has different performance characteristics compared to LinkedList :

1. Insertaion and Deletion : LinkedList is better for frequent insertion and deletions in the middle of the list because it does not require shifting elements, as in ArrayList.
2. Random Access : LinkedList has slower random access (get(int index)) compared to ArrayList because it has to traverse the list from the beginning to reach the desired index.
3. Memory Overhead : LinkedList requires more memory than ArrayList because each node in a linked list requires extra memory to store reference to the next and previous nodes.

[Dhanrajpatil123]

public class VariableDataTypeEx {

    public static void main(String[] args) {

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);

        System.out.println(linkedList.get(2));  // to search the value --> O(n)

        linkedList.addFirst(10);  // insertion --> O(1)

        linkedList.getLast();   // get last --> O(1)

        linkedList.remove(1);

        linkedList.removeFirst();

        linkedList.removeLast();

        linkedList.removeIf(x -> x % 2 == 0);   // output --> [1, 3, 5]

        System.out.println(linkedList);

        LinkedList<String> animals = new LinkedList<>(Arrays.asList("Cat", "Dog", "Tiger", "Elephant"));

        LinkedList<String> animalsToRemove = new LinkedList<>(Arrays.asList("Dog", "Tiger", "Lion"));

        animals.removeAll(animalsToRemove);

        System.out.println(animals);      //  [Cat, Elephant]

}