Table of Content

Understanding Linked List

1. Introduction to Linked Lists:
   • LinkedLists manage data and connections efficiently.
   • Comparable to a train where each carriage (node) is connected to the next.
2. Comparison with Dynamic Arrays:
   • Dynamic arrays are stored in contiguous memory, resizing can be costly.
   • LinkedLists store data in non-contiguous nodes, allowing for flexible memory usage.
3. Components of Linked Lists:
   • Head: First node in the LinkedList.
   • Tail: Last node in the LinkedList, pointing to null.
4. Operations on Linked Lists:
   • Traversal: Start at the head and follow links to the tail.
   • Insertion: Add a node by connecting it to the last node.
   • Deletion: Detach a node and link the previous node to the next one.
5. Advantages of Linked Lists:
   • Dynamic Size: Can grow or shrink as needed.
   • Efficient Insertions and Deletions: Especially at the beginning of the list, often O(1) time complexity.
6. Drawbacks of Linked Lists:
   • Slower Element Access: O(n) time complexity for accessing elements.
   • Memory Efficiency: Extra pointers increase memory overhead per element.
   • Memory Management: More complex code to handle node pointers.

Type of Linked List

1. Singly LinkedList:
   • Nodes contain data and a reference to the next node.
   • Traversal is one-way from head to tail.
   • Efficient for simple, one-way data flow.
2. Doubly LinkedList:
   • Nodes have two pointers: one to the next node and one to the previous node.
   • Allows traversal in both forward and backward directions.
   • Enhanced flexibility and accessibility.
3. Circular LinkedList:
   • Last node points back to the first node, forming a continuous loop.
   • Suitable for applications requiring cyclic data access.
   • Types: Singly Circular (one-way traversal) and Doubly Circular (two-way traversal).

Hands-on: LinkedList

1. Creating a Custom LinkedList:
   • Node Class: Represents a node with data and a reference to the next node.
   • LL Class: Manages the LinkedList with methods for adding, removing, and printing nodes.
2. Adding Nodes:
   • addFirst: Adds a node at the beginning.
   • addLast: Adds a node at the end.
   • printList: Prints the LinkedList.
3. Removing Nodes:
   • removeFirst: Removes the first node.
   • removeLast: Removes the last node.

Code Example:

class LL {

   Node head;
   private int size;

   public LL() {
       size = 0;
   }

   public class Node {
       String data;
       Node next;

       Node(String data) {
           this.data = data;
           this.next = null;
       }
   }

   public void addFirst(String data) {
       Node node = new Node(data);
       node.next = head;
       head = node;
       size++;
   }

   public void addLast(String data) {
       Node node = new Node(data);
       if(head==null) {
           head = node;
           size++;
           return;
       }
       Node lastNode = head;
       while (lastNode.next != null) {
           lastNode = lastNode.next;
       }
       lastNode.next = node;
       size++;
   }

   public void printlist() {
       Node currNode = head;
       while (currNode != null) {
           System.out.print(currNode.data + " -> ");
           currNode = currNode.next;
       }
       System.out.println("null");
   }

   public void removeFirst() {
       if(head == null) {
           System.out.println("Empty List, nothing to delete");
           return;
       }
       head = this.head.next;
       size ++;
   }

   public void removeLast() {
       if(head == null) {
           System.out.println("Empty List, nothing to delete");
           return;
       }
       if(head.next == null) {
           head = null;
           size--;
           return;
       }
       Node currNode = head;
       Node lastNode = head.next;
       while(lastNode.next != null) {
           currNode = currNode.next;
           lastNode = lastNode.next;
       }
       currNode.next = null;
       size --;
   }

   public int getSize() {
       return this.size;
   }
}

Using Java's LinkedList Class: