Blog Detail

  • 1b76d10_322.png

    Singly Linked List - Data Structure

    A linked list is a data structure used for storing collections of data. The linked list has the following properties.

      Successive elements are connected by pointers

      The last element points to null

      Can grow and shrink in size during the execution of a program

      Can be made just as long as required (until system memory exhausts)

      It does not waste memory space (but takes some extra memory for pointers)




    Linked Lists Abstract Data Type(ADT)

    The following operations make linked lists an ADT:


    Main Linked lists operations


    Insert: inserts an element into the list

    Delete: removes and returns the specified position element from the list


    Auxiliary Linked lists operation


    Delete list: emoves all elements of the list (disposes of the list)

    Count: Returns the number of elements in the list

    Find nth  node from the end of the list



    Why Linked Lists

    There are many other data structures that do the same thing as that of linked lists. Before discussing linked lists it is important to understand the difference between linked lists and arrays.

    Both the linked lists and arrays are used to store collections of data. Since both are used for the same purpose, we need to differentiate arrays and linked lists.

    The advantage of linked lists is that they can be expanded in constant time. To create an array we must allocate memory for a certain number of elements.

    To add more elements to the array then we must create a new array and copy the old array into the new array. This can take a lot of time.

    In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.

    In a linked list though, you have to start from the head and work your way through until you get to the fourth element.

    Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.



    Singly Linked Lists Or One-way chain

    A generally linked list means a singly linked list. This list consists of a number of nodes in which each node has a next pointer to the following element. The link of the last node in the list is

    NULL, which indicates the end of the list.

    Operations on Singly Linked List


    There are various operations that can be performed on a singly linked list. A list of all such operations is given below.

    • Node Creation
            class Node{
                int data;
                Node next;
                public Node(int data) {
                    this.data = data;
                    this.next = null;
                }
            }  
    • Inserting an item in the list

              Inserting a new node before the head (at the beginning)

              Inserting a new node after the tail (at the end of the list)

              Inserting a new node at the middle of the list (random location)

    • Deleting an item from the list

                Deleting the first node

                Deleting the last node

                Deleting an intermediate node


    Example:


    import java.util.*;
    public class LinkedList1{
    public static void main(String args[]){

          LinkedList<String> al=new LinkedList<String>();
          al.add("Ravi");
          al.add("Vijay");
          al.add("Ravi");
          al.add("Ajay");

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