Linked List

A linked list is a data structure used for organizing and storing a collection of elements. It consists of a sequence of nodes where each node contains data and references to the next node.

The last node has a reference to null. This indicates the end of the list.

STRUCTURE OF LINKED LIST

The structure of a linked list consists of nodes linked together to form a sequence. Each node has two main components.

1. Data

   It holds the actual value or data that the node represents.

2. Reference/Next pointer

   It is a reference to the next node in the sequence. It stores the memory address of the next node.

OPERATIONS

The operations that can be performed on linked lists:

1. Adding a new node at the start

   

ALGORITHM:

1. Create a new node with the desired value.

2. Set the next reference of the new node to point to the current head of the linked list.

3. Update the head of the linked list to point to the newly created node.

CODE:

public class linkedlist{
   Node head;

   class Node{
      String data;
      Node next;

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


   public void addfirst(String data){
      Node newnode=new Node(data);
      if(head==null){
         head=newnode;
         return;
      }
      newnode.next=head;
      head=newnode;
  }

  public void printlist(){
    if(head==null){
       System.out.print("List is Empty");
       return;
    }

    Node currnode=head;
    while(currnode!=null){
       System.out.print(currnode.data + "-->");
       currnode=currnode.next;
    }
    System.out.print("null");
  }


  public static void main(String[] args){
    linkedlist list=new linkedlist();
    list.addfirst("Amazing");
    list.addfirst("Awesome");
    list.printlist()
  }
}

1. Adding a new node at the end of the list

ALGORITHM:

1. Create a new node with the desired value.

2. Traverse the linked list starting from the head till you reach the last node.

3. The next reference of the last node should point to the new node.

CODE:

public class linkedlist{
  Node head;

  class Node{
    String data;
    Node next;

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

  public void addlast(String data){
    Node newnode=new Node(data);
    if(head==null){
      head=newnode;
      return;
    }
    Node currnode=head;
    while(currnode.next!=null){
      currnode=currnode.next;
    }
    currnode.next=newnode;
  }

  public void printlist(){
    if(head==null){
       System.out.print("List is Empty");
       return;
    }

    Node currnode=head;
    while(currnode!=null){
       System.out.print(currnode.data + "-->");
       currnode=currnode.next;
    }
    System.out.print("null");
  }


  public static void main(String[] args){
     linkedlist list=new linkedlist();
     list.addlast("Amazing");
     list.addlast("Cool");
     list.printlist();
  }
}

1. Deleting the first node

ALGORITHM

1. Check if the linked list is empty.

2. If the list is not empty assign the second node as the new head of the linked list.

3. Update the next pointer of the head to null to delete the first node.

CODE:

class linkedlist{
  Node head;

  class Node{
    String data;
    Node next;

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

  public void deletefirst(){
    if(head==null){
       System.out.print("List is empty");
       return;
    }
    head=head.next;
  }

  public void printlist(){
    if(head==null){
       System.out.print("List is Empty");
       return;
    }

    Node currnode=head;
    while(currnode!=null){
       System.out.print(currnode.data + "-->");
       currnode=currnode.next;
    }
    System.out.print("null");
  }

  public static void main(String[] args){
    linkedlist list=new linkedlist();
    list.deletefirst()
    list.printlist()
  }

}

1. Delete the last node from the linked list

ALGORITHM:

1. Traverse the list until you reach the second-to-last node.

2. Then update the next pointer of the second-to-last node to null.

3. Then you can remove the last node effectively.

CODE:

class linkedlist{
  Node head;

  class Node{
    String data;
    Node next;

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

  public void deletelast(){
    if(head==null){
      System.out.println("List is empty");
      return;
    }

    if(head.next==null){
      head=null;
      return;
    }

    Node secondlast=head;
    Node lastnode=head.next;
    while(lastnode.next!=null){
      lastnode=lastnode.next;
      secondlast=secondlast.next;
    }

    secondlast.next=null;
  }

  public void printlist(){
    if(head==null){
       System.out.print("List is Empty");
       return;
    }

    Node currnode=head;
    while(currnode!=null){
       System.out.print(currnode.data + "-->");
       currnode=currnode.next;
    }
    System.out.print("null");
  }

  public static void main(String[] args){
    linkedlist list=new linkedlist();
    list.deletelast()
    list.printlist()
  }

}

1. Calculating the length of the linked list

1.   public int getcount(Node head){
       int count=0;
   
       while(head != null){
         head=head.next;
         count++;
       }
       return count;
     }
   

   Here we have initialized a counter variable count=0.

   As we traverse through each node of the linked list count is incremented.

1. Searching for a value in a linked list

1.  boolean searchkey(String key){
      Node temp=head;
   
      while(temp!=null){
        if(temp.data==key){
          return True;
        }
        temp=temp.next;
      }
      return False;
    }