Linked List

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a link to the next node in the sequence.

                     
 
Linked lists are one of the most common and simple data structure. It is used i creating lists, stacks, queues, dictionaries and many other abstract data types.

Pros:
  1. It is a dynamic data structure. The memory is created at run time while running a program.
  2. Insertion and deletion nodes operations are very easy in linked list. We can insert node and delete node easily.
  3. Linear data structures such as stacks and queues can be easily implemented using linked list.
  4. The access time is faster in linked list and it can be expanded in constant time without memory overhead.

Cons:
  1. Wastage of memory takes place in linked list as pointers requires extra memory for storage.
  2. In Linked list no random access is given to user, we have to access each node sequentially.
  3. In linked list, it takes a lot of time to access an element as individual nodes are not stored in contiguous memory allocations.
  4. Reverse traversing is very difficult in linked list.

 We can discuss about various simple operations applicable to linked list.

1. Traverse:

We keep on traversing the each and every node till we find the next link to point to null.

                                           while(node.next!=null)
                                           {
                                                 System.out.print(node.data);
                                                 node = node.next;
                                           }
                                           System.out.print(node.data);

2. Append node:

We keep on traversing till the end and then create a new node and provide the link of the lst node to the newly created node and point the link of newly created node to null.

                                       while(node.next!=null){
                                             node= node.next;
                                       }
                                       node.next = new Node(data);



3. Add a node after a specific node:

Keep on traversing till you find the node, then create a node and assign the next link to the current nodes next and then current nodes next to newly created node.

Adding 60 after 15

                                    while(node.next!=null){
                                          if(node.data==afterData){
                                                  Node temp = new Node(data,node.next);
                                                  node.next = temp;
                                                  break;
                                          }
                                          node = node.next;
                                   }

4. Remove node at the end:

This is a bit tricky, we can not traverse by checking for node's next to be null as to remove a node we need a reference to the node previous of the node to be deleted. So we check node.next.next!=null while traversing as there is no way to reach the previous node from the last node.

                                        if(node.next==null){
                                             head = null;
                                         }
                                        while(node.next.next!=null){
                                             node=node.next;
                                         }
                                        node.next=null;